3 ms·

This is not a material distinction: for every pair (M, input) you can create a machine M’ which has no actual input and instead first writes down the input to M

by xyzzyz 4y ago

This is not a material distinction: for every pair (M, input) you can create a machine M’ which has no actual input and instead first writes down the input to M onto the empty tape, and then runs M. This technique practically allows you to perform most of the same proofs on inputless machines. > For similar reasons you can have a solution to the halting problem given a program of infinite size. Sorry, what is a “program of infinite size” in context of Turing machines?

Retric 4y ago
> 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 https://en.wikipedia.org/wiki/Wikipedia Replace “finite table” with “infinite table”.
- karatinversion 4y ago
  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.
- 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 ago
    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.
    - jakelazaroff 4y ago
      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.
      - 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.

by xyzzyz 4y ago

Retric 4y ago

> 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 https://en.wikipedia.org/wiki/Wikipedia Replace “finite table” with “infinite table”.

karatinversion 4y ago
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.
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 ago
  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.
  - jakelazaroff 4y ago
    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.
    - 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.