5 ms·
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 t
by nx 18y ago
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.)
- gruseom 18y agoI'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/TuringMachine.html 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.
- nx 18y agoReally? 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
- gruseom 18y agoCan you email me about this? Address in profile.
- nx 18y agoOh, sure, I'll probably even start a blog out of this :P
- gruseom 18y agoWatch out, you're blowing your cover as lazy :)
- nx 18y agoWell this is just too interesting, and I should stop putting off this blog thing.
- gruseom 18y agoSo? What have you learned?
- nx 18y agoIt 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.
- eru 18y agoAnother idea: Implement one-dimensional cellular automata in Excel. There are fairly simple Turing-complete ones.
- eru 18y agoOK, might work.
- deleted 18y ago[deleted]