News for hackers. Stuff that matters.
Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @11:50AM (#432235)
I do not want to prove it, because I'm lazy, but I know it's trivially provable that it's possible to create a Turing machine in Excel in many ways. You could take any row or column to be the tape and store state and table in other cells. Then add a bunch of conditionals and LOOKUPs you get your Turing machine. It would probably be easier using VBA, but it's an interesting idea. (Not that it would get you anywhere, though.)
Re:Ask HN: What can't you do in Excel? by gruseom on Tuesday January 13, 2009 @03:08PM (#432600)
I'm not so sure. Googling around on this brings up a lot of statements to the effect that Excel is not Turing-complete. (I mean, of course, excluding VBA.) I haven't found a proof either way, though surely one is out there.

This paper claims to prove that the authors' spreadsheet is Turing-complete in contrast to Excel:

http://web.engr.oregonstate.edu/~burnett/Turing/TuringMachin...

Actually, it would be more interesting if spreadsheets were not Turing-complete, given how much people are able to do with them.

Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @03:34PM (#432644)
Really? I'd find it hard to believe that it isn't Turing complete. The only reason I can think of would be limits on nested functions or otherwise, but I dunno, I've been googling around myself and some say it isn't. Well, next thing to do: implement a Turing machine in Excel. Or Google Docs. I think I'm going for the latter.

Edit: Spreadsheets have no state. This is hard. If only I could delay evaluation :P

Re:Ask HN: What can't you do in Excel? by eru on Tuesday January 13, 2009 @05:37PM (#432852)
Another idea: Implement one-dimensional cellular automata in Excel. There are fairly simple Turing-complete ones.
Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @05:54PM (#432875)
Will probably do. I thought of Minesweeper first, but Turing machines don't seem to be that hard anyway.
Re:Ask HN: What can't you do in Excel? by eru on Tuesday January 13, 2009 @07:37PM (#432973)
Minesweeper is in NP, only.
Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @09:22PM (#433059)
You're right, my bad.
Re:Ask HN: What can't you do in Excel? by gruseom on Tuesday January 13, 2009 @04:01PM (#432693)
Can you email me about this? Address in profile.
Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @04:34PM (#432744)
Oh, sure, I'll probably even start a blog out of this :P
Re:Ask HN: What can't you do in Excel? by gruseom on Tuesday January 13, 2009 @08:01PM (#432991)
Watch out, you're blowing your cover as lazy :)
Re:Ask HN: What can't you do in Excel? by nx on Tuesday January 13, 2009 @09:20PM (#433058)
Well this is just too interesting, and I should stop putting off this blog thing.
Re:Ask HN: What can't you do in Excel? by gruseom on Saturday January 17, 2009 @01:40PM (#438379)
So? What have you learned?
Re:Ask HN: What can't you do in Excel? by nx on Sunday January 18, 2009 @04:45PM (#439725)
It is possible, not specially hard, I implemented a Turing machine and a one-dimensional cellular automaton. You can program just about anything in a spreadsheet. I will later study the inner properties of the spreadsheet as a data structure and a programming paradigm.
Re:Ask HN: What can't you do in Excel? by eru on Tuesday January 13, 2009 @02:00PM (#432465)
OK, might work.