> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
70 karma · joined September 2, 2021
> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
However, the Collatz-like problems you will get from this completion will be gigantic, they will not have distilled the problem into a similar description of it's behavior, but instead created a more complicated way of observing that behavior. The Collatz-like problem I present here is a simplification of the behavior of this TM. If you observe the machine running you will see that it is effectively completing these transitions.
In other words, I am not arbitrarily choosing to convert this to a Collatz-like problem simply because it is possible. I am looking at the behavior of this machine and that behavior turns out to be Collatz-like naturally.
Of course none of this proves that my Collatz-like problem really is hard ... but as someone else here mentioned, being hard is not a mathematical thing, it is a belief we have about certain problems we cannot solve after considerable effort.
I also agree somewhat on the one trajectory vs. multiple trajectories point. However, note that (assuming we live in the world where this TM never halts) proving a single trajectory in this system is "harder" than a single trajectory in the classic Collatz conjecture. Specifically, (assuming the Collatz conjecture is true) proving any single trajectory is "simply" a finite computation. However, proving a single trajectory from the article requires showing that it never halts which will require some more fancy math!
Anywho, I don't want to oversell it. This does not prove that BB(3, 3) requires proving the Collatz conjecture or any existing well-studied open problem in Math. But I think it's sort of a "second best" result: As hard a problem akin to a well studied problem.
How hard is this Collatz-like problem? Well, let's see if anyone can solve it :)
In addition to proving this one machine by hand (which may be necessary to completely prove the BB(5) value), this post also introduces a new type of proof that a TM does not halt (specifically the "Reset Invariant"). There's potential that this technique could be automated to prove a whole group of TMs non-halting (which is the main way that we have made progress on proving Busy Beaver values in the past).
Thanks fn-mote for providing some context. In fact, I think you could appreciate most of this article without even knowing anything about Turing Machines. I spend almost the entire article just answering the question: Given a set of exponential transition rules, starting from C(5), does iterating these rules ever lead to Halt(N)? If so, in how many iterations? And what is the value of N in that case?