3 ms·
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 insurmountabl
by 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 agoI'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 agoIt'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 agoEdit: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 agoSuppose 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 agoYou are correct, thank you
- srcreigh 2y agoBit 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...