3 ms·

Still confused — aren't we talking about a particular machine? Obviously the number of possible states in any given machine is unbounded, but the number of stat

• 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.