> This technique practically allows you to perform most of the same proofs on inputless machines.
Emulating a machine allows you to know stuff that the machine being emulated can’t such as the width the the data written to the tape. It seems reasonable that you can still prove incompleteness, but I suspect it’s non trivial.
> Sorry, what is a “program of infinite size” in the context of Turing machines.
“The choice of which replacement symbol to write and which direction to move is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read.” https://en.wikipedia.org/wiki/Wikipedia
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.
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.
Well yes, and a proof system with the omega rule also escapes incompleteness, but I never yet saw anyone prove a theorem by checking it held for every natural number.
Emulating a machine allows you to know stuff that the machine being emulated can’t such as the width the the data written to the tape. It seems reasonable that you can still prove incompleteness, but I suspect it’s non trivial.
> Sorry, what is a “program of infinite size” in the context of Turing machines.
“The choice of which replacement symbol to write and which direction to move is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read.” https://en.wikipedia.org/wiki/Wikipedia
Replace “finite table” with “infinite table”.