Hacker News new | past | comments | ask | show | jobs | submit login

You need the table before the machine starts, so “current state” is finite but possible states isn’t.

Think a given natural number X is finite Aka 2, a list of all natural numbers is infinite.




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 states in one particular machine is finite.


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.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: