4 ms·

> Think about it this way. If a particular Turing machine halts, that’s a finitary fact: you can prove it by exhibiting a finite sequence of valid states for th

> Think about it this way. If a particular Turing machine halts, that’s a finitary fact: you can prove it by exhibiting a finite sequence of valid states for the Turing machine which ends in a halt. But if it doesn’t halt, that’s an infinitary statement: it doesn’t halt after N steps, for any N. Machines that halt can always be proved to halt, as you say just by exhibiting them running to halting. (In principle at least; in practice this can be quite difficult.) Machines that don't halt fall into two groups: those that can be proved not to halt and those that cannot be proved not to halt. Provably non-halting machines are not rare or strange. For example, a machine can wind up getting stuck in one state that just moves off to the edge of the tape forever. If this happens, it's obvious that the machine will never halt, and that's provable. Sometimes non-haltingness has an infinitary character, but not always.

Retric 4y ago
The incompleteness proof depends on the input to the program under consideration, BB is limited to programs that don’t have any input which makes the incompleteness proof irrelevant. For similar reasons you can have a solution to the halting problem given a program of infinite size that is only considering programs of finite size with finite inputs.
- 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.
karatinversion 4y ago
Infinitary in the sense that a proof of non-halting must be strong enough to establish something about all natural numbers (does not halt after 1 step, does not halt after 2 steps, does not halt after 3 steps…) which cannot be done on a case-by-case (“finitary”) way. In contrast to a proof of halting, which can be so done.
- nickdrozd 4y ago
  The usual way to deal with an infinite number of cases is to group them into a finite number of cases and then deal with those. That's how induction works. So if you can prove that (1) the machine is in a certain condition at some step and (2) whenever the machine is in that condition at some step it will get back into that same condition at a later step, then you can prove that the machine will never halt.
  - samatman 4y ago
    Right, the act of iterating a cycle might be infinite but the cycle itself is finite. Proving that nothing can break the cycle is possible in many simple cases.

Retric 4y ago

The incompleteness proof depends on the input to the program under consideration, BB is limited to programs that don’t have any input which makes the incompleteness proof irrelevant. For similar reasons you can have a solution to the halting problem given a program of infinite size that is only considering programs of finite size with finite inputs.

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.

karatinversion 4y ago

Infinitary in the sense that a proof of non-halting must be strong enough to establish something about all natural numbers (does not halt after 1 step, does not halt after 2 steps, does not halt after 3 steps…) which cannot be done on a case-by-case (“finitary”) way. In contrast to a proof of halting, which can be so done.

nickdrozd 4y ago
The usual way to deal with an infinite number of cases is to group them into a finite number of cases and then deal with those. That's how induction works. So if you can prove that (1) the machine is in a certain condition at some step and (2) whenever the machine is in that condition at some step it will get back into that same condition at a later step, then you can prove that the machine will never halt.
- samatman 4y ago
  Right, the act of iterating a cycle might be infinite but the cycle itself is finite. Proving that nothing can break the cycle is possible in many simple cases.