6 ms·

> because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets Think about it this

> because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets 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. And no finite enumeration of steps can prove that it doesn’t halt eventually. Since the statement is infinitary, it’s liable to avoid being probable if our axioms don’t capture it - and so computable set of axioms captures all true statements. And if we can’t prove that a particular Turing machine of N states doesn’t halt, we can’t prove any value for BB(N), as otherwise we could just staple the first BB(N) states of the Turing machine to show it doesn’t halt, which we can’t prove.

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

nickdrozd 4y ago

> 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.
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.