3 ms·

What'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 ago
  Linux 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.
  • andi999 5y ago
    Good thing is there is no halting problem when using 64bit pointers.
  • astrange 5y ago
    Turing machines don't have pointers, just offsets from the current position. Since you can't move infinite steps, you can still use finite offsets.