5 ms·
Microsoft Excel is not just Turing complete. It is in fact a halting oracle
- appleflaxen 3y agoThis sounds insightful but I don't know what it means. Can anyone explain it to me?
- Gormisdomai 3y agoUnder 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 https://en.m.wikipedia.org/wiki/Hypercomputation [2] https://en.m.wikipedia.org/wiki/Model_of_computation https://en.m.wikipedia.org/wiki/Model_of_computation [3] https://en.m.wikipedia.org/wiki/Turing_machine https://en.m.wikipedia.org/wiki/Turing_machine [4] https://support.microsoft.com/en-us/office/fill-a-formula-down-into-adjacent-cells-041edfe2-05bc-40e6-b933-ef48c3f308c6 https://support.microsoft.com/en-us/office/fill-a-formula-do...