6 ms·
If we had that, how many n64 implementations could we stack? More generally, what’s the most nested Turing machine ever built?
by mdonahoe 5y ago
If we had that, how many n64 implementations could we stack?
More generally, what’s the most nested Turing machine ever built?
- d33 5y agoYou might love this article from page 14 of PoC||GTFO #20: https://www.alchemistowl.org/pocorgtfo/pocorgtfo20.pdf https://www.alchemistowl.org/pocorgtfo/pocorgtfo20.pdf (warning: it's a relatively big PDF file, which also works as a .zip file with resources)
- andi999 5y agoZero. No Turing machine has ever been built. The tape needs to be infinite to be a Turing machine.
- atoav 5y agoGP probably meant something among the lines of: "What is the most nested turing complete system ever built"
- mdonahoe 5y agoYou are correct, this is what I meant. I've found "self-interpreter" implementations that aim to be short https://arxiv.org/html/cs/0311032 https://arxiv.org/html/cs/0311032 https://codegolf.stackexchange.com/questions/585/self-interpreting-interpreter https://codegolf.stackexchange.com/questions/585/self-interp... But I haven't found anyone yet that optimized for actual number of recursive implementations on a real machine.
- astrange 5y agoCan you prove that statement in finite time?
- emteycz 5y agoWhat's the problem with adding more tape as needed? You don't need a literally infinite tape to have infinite tape from the machine's POV.
- throwawayninja 5y agoLinux already overcommits memory so much you can imaging it's infinite, the big show-stopper is the 64 bit integers used to track it. We'd need infinite pointer sizes before we could meaningfully use infinite tape.