3 ms·

See also this article (shared on Hacker News 2 weeks ago): https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html https://www.sligocki.com//2023/10/16/bb-3-3-

by mcherm 3y ago

See also this article (shared on Hacker News 2 weeks ago): https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html Basically, they showed that a VERY small Turing Machine -- of a size many had hoped we would be able to exhaustively solve -- turns out to depend on whether something similar to the Collatz sequence ever haults. In other words, research published just 2 weeks ago shows that we don't need a Turing machine with a couple thousand states to be beyond the reach of modern human mathematics -- even one with just a few states can stimy us.

raincole 3y ago
What does "exhaustively solve a Turing Machine" mean is this context?
- pxeger1 3y ago
  “Solve” means “solve the halting problem for” (i.e. prove whether it will halt or not), and “exhaustively” means “for all possible Turing machines with a given number of states”
  - raincole 3y ago
    But intuitively a Turning machine, no matter how small number of states, can't be exhaustively solved, since there are infinite number of possilbe strings on the tape?
    - denotational 3y ago
      Proving properties hold over sets of infinite cardinality is fairly routine in mathematics. We know that not every Turing Machine can be “solved”, because this would give us an oracle for HALT, but there are machines that can be. A trivial example is a TM that halts immediately, regardless of the input; a less trivial example is one that reads an arbitrarily large integer input on the tape and outputs its factorisation (or, if we don’t want to consider output, decides whether an input pair is formed of an integer and it’s factorisation). Given that the set of Turing Machines with a certain number of states (or less) is finite for a given alphabet, it’s “just” a case of solving that finite set. EDIT: Note that as the sibling comment points out, BB is usually considered to start with an empty tape, but fundamentally, proving that a machine always halts regardless of their starting tape is not intrinsically impossible as you suggest.
    - LegionMammal978 3y ago
      Generally, when we talk about the halting problem in the Busy Beaver context, we're talking about the halting problem starting from an empty tape. However, some authors have analyzed the behavior of Turing machines on certain classes of infinite tapes. For instance, in [0], the authors surveyed the behavior of TMs starting on a tape with an arbitrary word in the middle, and an infinitely repeating word on one or both sides; one finding is that no 2-state 2-symbol TM is a universal Turing machine, for any of these input tapes. [0] https://arxiv.org/abs/1110.2230 https://arxiv.org/abs/1110.2230
- klyrs 3y ago
  I interpreted that to mean "exhaustively determine whether or not every single (3,3) Turing machine halts", thereby computing BB(3,3). After all, there are only 19^9 (around 2^39) of them.
srcreigh 3y ago
Also, for a nice deepening of the situation.. in the 70's John Conway proved that generalized Collatz problems are undecidable. AKA, you can compile turing machines to Collatz problems This means all the characteristics of busy beaver numbers, including how every axiom system has a limit in what it can prove, is actually true of Collatz problems too.

by mcherm 3y ago

raincole 3y ago

What does "exhaustively solve a Turing Machine" mean is this context?

pxeger1 3y ago
“Solve” means “solve the halting problem for” (i.e. prove whether it will halt or not), and “exhaustively” means “for all possible Turing machines with a given number of states”
- raincole 3y ago
  But intuitively a Turning machine, no matter how small number of states, can't be exhaustively solved, since there are infinite number of possilbe strings on the tape?
  - denotational 3y ago
    Proving properties hold over sets of infinite cardinality is fairly routine in mathematics. We know that not every Turing Machine can be “solved”, because this would give us an oracle for HALT, but there are machines that can be. A trivial example is a TM that halts immediately, regardless of the input; a less trivial example is one that reads an arbitrarily large integer input on the tape and outputs its factorisation (or, if we don’t want to consider output, decides whether an input pair is formed of an integer and it’s factorisation). Given that the set of Turing Machines with a certain number of states (or less) is finite for a given alphabet, it’s “just” a case of solving that finite set. EDIT: Note that as the sibling comment points out, BB is usually considered to start with an empty tape, but fundamentally, proving that a machine always halts regardless of their starting tape is not intrinsically impossible as you suggest.
  - LegionMammal978 3y ago
    Generally, when we talk about the halting problem in the Busy Beaver context, we're talking about the halting problem starting from an empty tape. However, some authors have analyzed the behavior of Turing machines on certain classes of infinite tapes. For instance, in [0], the authors surveyed the behavior of TMs starting on a tape with an arbitrary word in the middle, and an infinitely repeating word on one or both sides; one finding is that no 2-state 2-symbol TM is a universal Turing machine, for any of these input tapes. [0] https://arxiv.org/abs/1110.2230 https://arxiv.org/abs/1110.2230
klyrs 3y ago
I interpreted that to mean "exhaustively determine whether or not every single (3,3) Turing machine halts", thereby computing BB(3,3). After all, there are only 19^9 (around 2^39) of them.

srcreigh 3y ago

Also, for a nice deepening of the situation.. in the 70's John Conway proved that generalized Collatz problems are undecidable. AKA, you can compile turing machines to Collatz problems This means all the characteristics of busy beaver numbers, including how every axiom system has a limit in what it can prove, is actually true of Collatz problems too.