Ask HN: What can't you do in Excel?

Post by eru » Tue, Jan 13, 2009, 7:00 PM UTC

nx wrote: post #181

eru wrote: post #180

Earlier quoted context omitted.

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, t…

Post by gruseom » Tue, Jan 13, 2009, 8:08 PM UTC

nx wrote: post #181

eru wrote: post #180

Earlier quoted context omitted.

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, t…

Post by gruseom » Tue, Jan 13, 2009, 9:01 PM UTC

nx wrote: post #185

gruseom wrote: post #184

Earlier quoted context omitted.

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 interes…

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

Post by eru » Tue, Jan 13, 2009, 10:37 PM UTC

nx wrote: post #185

gruseom wrote: post #184

Earlier quoted context omitted.

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 interes…

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

Post by eru » Wed, Jan 14, 2009, 12:37 AM UTC

nx wrote: post #189

eru wrote: post #188

Earlier quoted context omitted.

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.