5 ms·

Excel is Turing-complete :P

• eru 18y ago
  Turing-Machines are Turing-complete, too.
  • nx 18y ago
    O RLY?
    • eru 18y ago
      To make my point explicit: Excel being Turing-complete does not imply it being feature-complete.
      • nx 18y ago
        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.
        • eru 18y ago
          Perhaps "O RLY?" was not witty enough?
          • GHFigs 18y ago
            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/
• eru 18y ago
  Can you prove it? (Not using scripting, of course.)
  • 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 ago
      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/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 ago
        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
        • gruseom 18y ago
          Can you email me about this? Address in profile.