3 ms·
Ahh, realized I wasn’t clear about this. By definition a touring machine has finite internal states, that’s also changed to infinity. Think of a machine that:
by Retric 4y ago
Ahh, realized I wasn’t clear about this. By definition a touring machine has finite internal states, that’s also changed to infinity.
Think of a machine that:
1 Knows it’s position on the tape
2 looks that position up on a table
3 writes the resulting cell to the tape
4 moves one position to the right
5 repeats from 1
With a finite table it’s going to run out of bounds, with an infinite table and the ability to store arbitrary position it’s always going to be possible to have a unique cell.