9 ms·

_the second form surely exists_ Is this true for the BB function though? What if there is a beaver that never halts or loops, and has behavior sufficiently co

by Aeium 2y ago

_the second form surely exists_ Is this true for the BB function though? What if there is a beaver that never halts or loops, and has behavior sufficiently complex, such that it's impossible to prove it will never halt. Then for rules of that length, the second form doesn't exist.

School-Cotton 2y ago
Whether it’s possible to prove it halts or not is irrelevant. It either does halt, or not. Whether a human can prove that a function has a particular value doesn’t change whether that function is computable in the technical sense being used here.
mananaysiempre 2y ago
If you’re using ZFC, there is (TFA mentions the state of the art is BB(745); Yedida and Aaronson’s original work on BB(8000)[1] is quite fun to read from a programmer’s point of view). But the second form still exists (if you accept excluded middle)—you just can’t prove which one it is! Specifically, ZFC is consistent iff ZFC+“Y&A’s machine does halt” is consistent iff ZFC+“Y&A’s machine never halts” is consistent (a theorem in a fairly weak ambient metalogic). So you can take a stronger set theory that does prove the answer, it’s just that thus far we have no reason to prefer theories that answer yes to theories that answer no. (You don’t have to accept excluded middle, and it can on occasion be useful not to[2], but pragmatically you’re going to have a lot of difficulties even with first-year calculus unless you do.) [1] https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725 [2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
feoren 2y ago
> What if there is a beaver that never halts or loops A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next. A "beaver" is defined to not loop. All "beavers" must halt, because otherwise they're just not considered for BB(n). All the challenge is in proving whether a given Turing machine does (or does not) halt, and therefore must not (or must) loop. Proving "halt" or "loop" proves the other one. Yes, the function `busy_beaver_6() = 576125642131574254..." must exist.
- School-Cotton 2y ago
  I disagree unless you state what you mean by "loop". If it's just "repeat a state" then any 6-state TM "loops" or halts after at most 6 turns... and many that "loop" will eventually halt. There are infinitely many configurations if you consider the tape. It is still true, of course, that every Turing machine either halts on a given input, or doesn't.
  - samatman 2y ago
    I don't understand what you're disagreeing with. "loop" has a well-understood meaning here: return to an identical state. Not a similar one, identical. Because if it does that once, being a deterministic automaton, it will do so an infinite number of times without halting.
    - School-Cotton 2y ago
      In determining whether you've returned to an identical state, are you including the tape? Or just the machine states? If you are including the tape, it's not true that there are finitely many states. If you're not, then "looping" as you've defined it is not excluded from the definition of the busy beaver problem, and does not imply that the machine never halts.
      - samatman 2y ago
        > If you are including the tape, it's not true that there are finitely many states. An infinite Turing tape can be in an identical state, however. The number of states don't have to be finite. If a Turing machine returns to an identical state, it will not halt. That's what we call looping. An example of an identical state is 1 at indexes 3 and 5 of the tape, and 0 everywhere else. Another example is the Brainfuck program `++[]`. This trivially returns repeatedly to a given finite state.
        School-Cotton 2y ago
        Yes, but the original claim was that non-halting TMs must loop because the number of configurations is finite. But that's not true. Here's an example of a bf program that never returns to an identical configuration, and also never halts. The corresponding TM would be excluded from consideration for the busy beaver number, despite never "looping" according to your definition. +[+] A similar-in-spirit TM (with tape alphabet {0, 1}, and only one machine state) is the one that unconditionally sets the current symbol to 1 and then moves to the right. This never encounters the same configuration twice (the number of 1s on the tape increases each turn) and also never halts.

by Aeium 2y ago

School-Cotton 2y ago

Whether it’s possible to prove it halts or not is irrelevant. It either does halt, or not. Whether a human can prove that a function has a particular value doesn’t change whether that function is computable in the technical sense being used here.

mananaysiempre 2y ago

If you’re using ZFC, there is (TFA mentions the state of the art is BB(745); Yedida and Aaronson’s original work on BB(8000)[1] is quite fun to read from a programmer’s point of view). But the second form still exists (if you accept excluded middle)—you just can’t prove which one it is! Specifically, ZFC is consistent iff ZFC+“Y&A’s machine does halt” is consistent iff ZFC+“Y&A’s machine never halts” is consistent (a theorem in a fairly weak ambient metalogic). So you can take a stronger set theory that does prove the answer, it’s just that thus far we have no reason to prefer theories that answer yes to theories that answer no. (You don’t have to accept excluded middle, and it can on occasion be useful not to[2], but pragmatically you’re going to have a lot of difficulties even with first-year calculus unless you do.) [1] https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725 [2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...

feoren 2y ago

> What if there is a beaver that never halts or loops A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next. A "beaver" is defined to not loop. All "beavers" must halt, because otherwise they're just not considered for BB(n). All the challenge is in proving whether a given Turing machine does (or does not) halt, and therefore must not (or must) loop. Proving "halt" or "loop" proves the other one. Yes, the function `busy_beaver_6() = 576125642131574254..." must exist.

School-Cotton 2y ago
I disagree unless you state what you mean by "loop". If it's just "repeat a state" then any 6-state TM "loops" or halts after at most 6 turns... and many that "loop" will eventually halt. There are infinitely many configurations if you consider the tape. It is still true, of course, that every Turing machine either halts on a given input, or doesn't.
- samatman 2y ago
  I don't understand what you're disagreeing with. "loop" has a well-understood meaning here: return to an identical state. Not a similar one, identical. Because if it does that once, being a deterministic automaton, it will do so an infinite number of times without halting.
  - School-Cotton 2y ago
    In determining whether you've returned to an identical state, are you including the tape? Or just the machine states? If you are including the tape, it's not true that there are finitely many states. If you're not, then "looping" as you've defined it is not excluded from the definition of the busy beaver problem, and does not imply that the machine never halts.
    - samatman 2y ago
      > If you are including the tape, it's not true that there are finitely many states. An infinite Turing tape can be in an identical state, however. The number of states don't have to be finite. If a Turing machine returns to an identical state, it will not halt. That's what we call looping. An example of an identical state is 1 at indexes 3 and 5 of the tape, and 0 everywhere else. Another example is the Brainfuck program `++[]`. This trivially returns repeatedly to a given finite state.
      - School-Cotton 2y ago
        Yes, but the original claim was that non-halting TMs must loop because the number of configurations is finite. But that's not true. Here's an example of a bf program that never returns to an identical configuration, and also never halts. The corresponding TM would be excluded from consideration for the busy beaver number, despite never "looping" according to your definition. +[+] A similar-in-spirit TM (with tape alphabet {0, 1}, and only one machine state) is the one that unconditionally sets the current symbol to 1 and then moves to the right. This never encounters the same configuration twice (the number of 1s on the tape increases each turn) and also never halts.