5 ms·

Excel Turing Machine

55 points by pjvds 13y ago

harrytuttle 13y ago
Just because you can, doesn't mean it's right ;) Nice work by the way. It's quite amazing the odd things you can do in Excel.
- TuringTest 13y ago
  Since Excel is Turing complete, you can do ''every possible calculation'' on it ;-)
willvarfar 13y ago
Somewhat related, my friend's enigma machine in an excel spreadsheet: http://williamedwardscoder.tumblr.com/post/19946053957/enigma-spreadsheet http://williamedwardscoder.tumblr.com/post/19946053957/enigm...
rwg 13y ago
Having implemented AES and a few other algorithms in "pure formula" Excel, I fully support seeing more things implemented in Excel! One of the biggest things to wrap your head around is that cells in Excel are write-once, read many. This forces you to unroll all of your loops, and you generally end up with a giant state machine, with each state occupying a row and depending on the state of the previous row.
- zeckalpha 13y ago
  So Excel is a pure functional language?
  - rwg 13y ago
    Yep. Additionally, there are no user-defined functions, and the limit on the length of the "code" that makes up a cell is low enough that you occasionally bump into it when trying to "program" in Excel. Excel also has a tendency to get crashy when you have a very complex cell dependency tree...
  - Monkeyget 13y ago
    I wouldn't call it functional. It's dataflow programming : http://en.wikipedia.org/wiki/Dataflow_programming http://en.wikipedia.org/wiki/Dataflow_programming
PLenz 13y ago
And the bandwidth from HN has killed their server...
triplesec 13y ago
google cache, because server fell over: http://webcache.googleusercontent.com/search?num=100&safe=off&q=cache%3Awww.felienne.com%2F%3Fp%3D2974&oq=cache%3Awww.felienne.com%2F%3Fp%3D2974&gs_l=serp.3...3915.3915.0.4230.1.1.0.0.0.0.54.54.1.1.0....0...1c.1.27.serp..1.0.0.Y24cp9XRlVU http://webcache.googleusercontent.com/search?num=100&safe=of...
jonahss 13y ago
Cool. I was working on simulating turing machines in excel last year and got an a^ib^i acceptor working but never finished creating a full universal turing machine. https://github.com/Jonahss/Spreadsheets-Without-Macros https://github.com/Jonahss/Spreadsheets-Without-Macros I create a circular dependency and set Microsoft excel to evaluate circular dependencies through one iteration. Every time you tell it to calculate, it steps through another clock cycle. This way I got a cool animated tapehead.
gruseom 13y ago
This is very cool! I've sometimes wondered about doing that. An obvious question is whether this suffices to show Turing completeness. I think the answer is no: because Excel has a finite number of cells, there are programs that this Turing machine won't have enough cells for. To get around that, you'd have to do something clever with iterative calcs (i.e. circular references) that effectively reuse the same cells behind the scenes. VBA is out of the question, of course. :)

55 points by pjvds 13y ago

Just because you can, doesn't mean it's right ;) Nice work by the way. It's quite amazing the odd things you can do in Excel.

TuringTest 13y ago
Since Excel is Turing complete, you can do ''every possible calculation'' on it ;-)

willvarfar 13y ago

Somewhat related, my friend's enigma machine in an excel spreadsheet: http://williamedwardscoder.tumblr.com/post/19946053957/enigma-spreadsheet http://williamedwardscoder.tumblr.com/post/19946053957/enigm...

rwg 13y ago

Having implemented AES and a few other algorithms in "pure formula" Excel, I fully support seeing more things implemented in Excel! One of the biggest things to wrap your head around is that cells in Excel are write-once, read many. This forces you to unroll all of your loops, and you generally end up with a giant state machine, with each state occupying a row and depending on the state of the previous row.

zeckalpha 13y ago
So Excel is a pure functional language?
- rwg 13y ago
  Yep. Additionally, there are no user-defined functions, and the limit on the length of the "code" that makes up a cell is low enough that you occasionally bump into it when trying to "program" in Excel. Excel also has a tendency to get crashy when you have a very complex cell dependency tree...
- Monkeyget 13y ago
  I wouldn't call it functional. It's dataflow programming : http://en.wikipedia.org/wiki/Dataflow_programming http://en.wikipedia.org/wiki/Dataflow_programming

PLenz 13y ago

And the bandwidth from HN has killed their server...

triplesec 13y ago

google cache, because server fell over: http://webcache.googleusercontent.com/search?num=100&safe=off&q=cache%3Awww.felienne.com%2F%3Fp%3D2974&oq=cache%3Awww.felienne.com%2F%3Fp%3D2974&gs_l=serp.3...3915.3915.0.4230.1.1.0.0.0.0.54.54.1.1.0....0...1c.1.27.serp..1.0.0.Y24cp9XRlVU http://webcache.googleusercontent.com/search?num=100&safe=of...

jonahss 13y ago

Cool. I was working on simulating turing machines in excel last year and got an a^ib^i acceptor working but never finished creating a full universal turing machine. https://github.com/Jonahss/Spreadsheets-Without-Macros https://github.com/Jonahss/Spreadsheets-Without-Macros I create a circular dependency and set Microsoft excel to evaluate circular dependencies through one iteration. Every time you tell it to calculate, it steps through another clock cycle. This way I got a cool animated tapehead.

gruseom 13y ago

This is very cool! I've sometimes wondered about doing that. An obvious question is whether this suffices to show Turing completeness. I think the answer is no: because Excel has a finite number of cells, there are programs that this Turing machine won't have enough cells for. To get around that, you'd have to do something clever with iterative calcs (i.e. circular references) that effectively reuse the same cells behind the scenes. VBA is out of the question, of course. :)