4 ms·

So we were just lucky that all non-halting programs of length 5 just happened to be provably non-halting?

tromp 2y ago
The article touches on that: > But just four days ago, mxdys and another contributor known as Racheline discovered a barrier for BB(6) that seems insurmountable: a six-rule machine whose halting problem resembles a famously intractable math problem called the Collatz conjecture. Connections between Turing machines and the Collatz conjecture date back to a 1993 paper by the mathematician Pascal Michel, but the newly discovered machine, dubbed “Antihydra,” is the smallest one that appears unsolvable without a conceptual breakthrough in mathematics.
- dwh452 2y ago
  I'm curious how the Turing machines can resemble problems which take input? BB(n) is defined as a n-state Turing machine that starts off with an empty tape. Collatz(n) is how many steps are taken before it terminates when starting with input 'n'. Does this mean a BB(6) machine which resembles Collatz is testing all possible values as part of it program and not part of anything on the tape (since the tape start out empty)?
  - LegionMammal978 2y ago
    It's not testing all values, but one particular starting point. In all likelyhood, it will never reach its stopping condition from this starting point, but proving this even for a single value is currently intractable. Compare with the "5x + 1" variant of the Collatz cojecture, where many values are believed (but not proven) to run off to infinity, never to return.
  - srcreigh 2y ago
    Edit:nvm see thread For collatz, the empty input machine loops over all natural numbers and halts if it finds one which doesn’t eventually reach 1. To prove that it never halts, you’d have to prove the collatz conjecture. Otherwise you’d have to find the smallest counter example of the collatz conjecture.
    - LegionMammal978 2y ago
      Suppose that there exists a natural number that diverges to infinity under the Collatz map. Then the Collatz conjecture would be false, but your machine would still run forever on that diverging number. As far as I am aware, there is no known machine that halts iff the Collatz conjecture is false.
      - srcreigh 2y ago
        You are correct, thank you
- srcreigh 2y ago
  Bit of a side note, but the article is a bit misleading here. Collatz-TM connections have been investigated much earlier. My fav is John Conway in 1972, who showed that the generalized Collatz problem is undecidable.[1] [1]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...
LegionMammal978 2y ago
Yes. In fact, Allen Brady feared as early as 1988 that there would be a totally intractable machine with 5 states [0]: > Prediction 5. It will never be proved that Σ(5) = 1,915 and S(5) = 2,358,064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.) > Reason: Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition. Luckily, this prediction did not come to pass, but only by a margin of one extra state. [0] Allen Brady, "The Busy Beaver Game and the Meaning of Life", in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, 1988, pp. 259–277. This chapter can also be found in the 2nd ed., Springer, 1995, pp. 237–254.
Sniffnoy 2y ago
When you say "provably", do you mean that in the mathematical sense or in a practical sense? For the practical sense, other commenters have already replied. For the mathematical sense, I would say it would be pretty surprising to me if BB(5) had been undecidable -- 5 states and 2 symbols is just so few with which to try to encode undecidable behavior. However, it's worth noting that as a consequence of the incompleteness theorem, there must be some n such that standard mathematics cannot prove the value of BB(n). And in recent years various people have been working on finding such n and seeing how low they can get the number. The current record[0] is 745. I expect that record can be probably be brought lower (more easily than the record for computing BB can be brought higher!), but even so, that's a lot of distance between 5 (the highest we know) and 745 (the lowest we know to be unknowable). [0]This is the current record both for ZFC and for PA, in case you're wondering what I mean by "standard mathematics"... so it at least ought to be possible to bring it down further for PA! I think so far nobody's found a way to do better for PA than for ZFC, even though, like, that has to be possible, right?
- ko27 2y ago
  Are there any interesting mathematical problems that can be encoded with 5 states and 2 symbols, which now we can prove using BB(5)?
  - Sniffnoy 2y ago
    I don't believe so. But even if there were, unfortunately, these things basically work the other way around. If you can encode a problem in n states, and you know BB(n), then, as you say, you could use that to solve the problem. Trouble is, how do you know BB(n)? In reality, the only way to determine BB(n) is to go and solve all such problems; there isn't any other easier method that you can apply that would then let you get answers for these problems as a consequence. So, the value of BB(n) will always be a summation of "we did all the hard work of solving all the n-state problems", not something you do separately to get those answers out.
  - UncombedCoconut 2y ago
    Mostly no: we did find some non-halting TMs that required new proofs, but none of those had the flavor of new math, per se. Indeed, we found that all but 30 of them could be proved by finite automata methods, meaning the TM's state/tape at any step could be reduced to one of finitely many states and we'd still know all we needed to know about future steps. I would argue that such a non-halting proof can't have much mathematical content. (Maybe a bit, in about the same way that an integer equation is sometimes proved unsolvable by considering it modulo n and checking every case.) Also, I learned some math I wasn't personally familiar with from the analysis of a particular machine: https://www.sligocki.com/2023/03/14/skelet-10.html https://www.sligocki.com/2023/03/14/skelet-10.html (Zeckendorf's Theorem).

The article touches on that: > But just four days ago, mxdys and another contributor known as Racheline discovered a barrier for BB(6) that seems insurmountable: a six-rule machine whose halting problem resembles a famously intractable math problem called the Collatz conjecture. Connections between Turing machines and the Collatz conjecture date back to a 1993 paper by the mathematician Pascal Michel, but the newly discovered machine, dubbed “Antihydra,” is the smallest one that appears unsolvable without a conceptual breakthrough in mathematics.

dwh452 2y ago
I'm curious how the Turing machines can resemble problems which take input? BB(n) is defined as a n-state Turing machine that starts off with an empty tape. Collatz(n) is how many steps are taken before it terminates when starting with input 'n'. Does this mean a BB(6) machine which resembles Collatz is testing all possible values as part of it program and not part of anything on the tape (since the tape start out empty)?
- LegionMammal978 2y ago
  It's not testing all values, but one particular starting point. In all likelyhood, it will never reach its stopping condition from this starting point, but proving this even for a single value is currently intractable. Compare with the "5x + 1" variant of the Collatz cojecture, where many values are believed (but not proven) to run off to infinity, never to return.
- srcreigh 2y ago
  Edit:nvm see thread For collatz, the empty input machine loops over all natural numbers and halts if it finds one which doesn’t eventually reach 1. To prove that it never halts, you’d have to prove the collatz conjecture. Otherwise you’d have to find the smallest counter example of the collatz conjecture.
  - LegionMammal978 2y ago
    Suppose that there exists a natural number that diverges to infinity under the Collatz map. Then the Collatz conjecture would be false, but your machine would still run forever on that diverging number. As far as I am aware, there is no known machine that halts iff the Collatz conjecture is false.
    - srcreigh 2y ago
      You are correct, thank you
srcreigh 2y ago
Bit of a side note, but the article is a bit misleading here. Collatz-TM connections have been investigated much earlier. My fav is John Conway in 1972, who showed that the generalized Collatz problem is undecidable.[1] [1]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...

LegionMammal978 2y ago

Yes. In fact, Allen Brady feared as early as 1988 that there would be a totally intractable machine with 5 states [0]: > Prediction 5. It will never be proved that Σ(5) = 1,915 and S(5) = 2,358,064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.) > Reason: Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition. Luckily, this prediction did not come to pass, but only by a margin of one extra state. [0] Allen Brady, "The Busy Beaver Game and the Meaning of Life", in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, 1988, pp. 259–277. This chapter can also be found in the 2nd ed., Springer, 1995, pp. 237–254.

Sniffnoy 2y ago

When you say "provably", do you mean that in the mathematical sense or in a practical sense? For the practical sense, other commenters have already replied. For the mathematical sense, I would say it would be pretty surprising to me if BB(5) had been undecidable -- 5 states and 2 symbols is just so few with which to try to encode undecidable behavior. However, it's worth noting that as a consequence of the incompleteness theorem, there must be some n such that standard mathematics cannot prove the value of BB(n). And in recent years various people have been working on finding such n and seeing how low they can get the number. The current record[0] is 745. I expect that record can be probably be brought lower (more easily than the record for computing BB can be brought higher!), but even so, that's a lot of distance between 5 (the highest we know) and 745 (the lowest we know to be unknowable). [0]This is the current record both for ZFC and for PA, in case you're wondering what I mean by "standard mathematics"... so it at least ought to be possible to bring it down further for PA! I think so far nobody's found a way to do better for PA than for ZFC, even though, like, that has to be possible, right?

ko27 2y ago
Are there any interesting mathematical problems that can be encoded with 5 states and 2 symbols, which now we can prove using BB(5)?
- Sniffnoy 2y ago
  I don't believe so. But even if there were, unfortunately, these things basically work the other way around. If you can encode a problem in n states, and you know BB(n), then, as you say, you could use that to solve the problem. Trouble is, how do you know BB(n)? In reality, the only way to determine BB(n) is to go and solve all such problems; there isn't any other easier method that you can apply that would then let you get answers for these problems as a consequence. So, the value of BB(n) will always be a summation of "we did all the hard work of solving all the n-state problems", not something you do separately to get those answers out.
- UncombedCoconut 2y ago
  Mostly no: we did find some non-halting TMs that required new proofs, but none of those had the flavor of new math, per se. Indeed, we found that all but 30 of them could be proved by finite automata methods, meaning the TM's state/tape at any step could be reduced to one of finitely many states and we'd still know all we needed to know about future steps. I would argue that such a non-halting proof can't have much mathematical content. (Maybe a bit, in about the same way that an integer equation is sometimes proved unsolvable by considering it modulo n and checking every case.) Also, I learned some math I wasn't personally familiar with from the analysis of a particular machine: https://www.sligocki.com/2023/03/14/skelet-10.html https://www.sligocki.com/2023/03/14/skelet-10.html (Zeckendorf's Theorem).