Microsoft Excel is not just Turing complete. It is in fact a halting oracle

https://twitter.com/mynamelowercase/status/1273044428899389440

by Gormisdomai • 3 years ago

3 2 3 years ago

twitter.com

appleflaxen• 3 years ago

This sounds insightful but I don't know what it means.

Can anyone explain it to me?

Gormisdomai• 3 years ago

Under one very theoretical framing[1], it turns out (maybe unsurprisingly) that spreadsheets are more powerful as a model of computation[2] than Turing Machines[3]. Mostly because of excel’s “drag down” feature[4].

In particular, a Turing machine with an infinite tape cannot simulate Excel with an infinite spreadsheet size. But Excel with an infinite spreadsheet size can simulate a Turing machine with an infinite tape.

None of this actually matters in the real world because computers have finite memory.

[1] https://en.m.wikipedia.org/wiki/Hypercomputation

[2] https://en.m.wikipedia.org/wiki/Model_of_computation

[3] https://en.m.wikipedia.org/wiki/Turing_machine

[4] https://support.microsoft.com/en-us/office/fill-a-formula-do...

Microsoft Excel is not just Turing complete. It is in fact a halting oracle

Related Stories