Re:Ask HN: What can't you do in Excel?
by nx on Sunday January 11, 2009 @03:35PM
(#429505)
Excel is Turing-complete :P
[ Parent
| on HN ]
Turing-Machines are Turing-complete, too.
O RLY?
To make my point explicit: Excel being Turing-complete does not imply it being feature-complete.
I know. It was a joke, thus the ":P", and so was the "O RLY?". But maybe the emoticon wasn't clear enough and I should've added an interrobang there? Anyway, thanks for the -10 karma points.
BTW, I do my spreadsheets with a Von Neumann derivate of a finite state automaton.
Perhaps "O RLY?" was not witty enough?
HAI
CAN HAS STDIO?
I HAS A WITTEH
I HAS A KARMA
IZ WITTEH BIGGER THAN "O RLY"?
YARLY
UP KARMA!!1
NOWAI
DOWN KARMA!!1
KTHX
KTHXBYE
BTW "On-Topic: Anything that good hackers would find interesting."
BTW http://lolcode.com/Can you prove it? (Not using scripting, of course.)
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.)
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.
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
Another idea: Implement one-dimensional cellular automata in Excel. There are fairly simple Turing-complete ones.
Will probably do. I thought of Minesweeper first, but Turing machines don't seem to be that hard anyway.
Minesweeper is in NP, only.
You're right, my bad.
Can you email me about this? Address in profile.
Oh, sure, I'll probably even start a blog out of this :P
Watch out, you're blowing your cover as lazy :)
Well this is just too interesting, and I should stop putting off this blog thing.
So? What have you learned?
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.