3 ms·
I might be misunderstanding something, but I don't think an infinite table makes sense? Each machine has a finite set of states and operates on a finite alphabe
by jakelazaroff 4y ago
I might be misunderstanding something, but I don't think an infinite table makes sense? Each machine has a finite set of states and operates on a finite alphabet, so the size of the table will always be at most the product of those two numbers.
- Retric 4y agoYou 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.
- jakelazaroff 4y agoStill 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.
- Retric 4y agoAhh, 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.