4 ms·
Zero. No Turing machine has ever been built. The tape needs to be infinite to be a Turing machine.
by andi999 5y ago
Zero. 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.