sligocki

I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states:

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.

Not sure if this is a joke, but actually that is guaranteed to be true. It is proven that for all n: BB(n+1) >= BB(n) + 3. But it is not proven that BB(n+1) >= BB(n) + 4, haha.

And 297/275 to 27/25?

50/18 reduces to 25/9 right?

Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) < BB(n + c) and vice-versa. I am not sure what the exact equation will be off-hand, maybe in this case we will need to replace BB() with a version based on binary encoding of TMs.

Yes, it seems that BB(3, 4) >>> BB(5, 2) (BB(5) = BB(5, 2)). This is not too surprising since BB(3, 4) has 12 transitions in it's table (3*4), while BB(5, 2) only has 10. But it seems that also BB(3, 4) >> BB(6, 2) (which both have the same number of transitions, so it appears that having more symbols is valuable to these little TMs.

Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) which comes out to <40 bits.

You are right that every TM can be converted into a Collatz-like problem using Conway's Fractran compilation. So technically the statement "Solving the BB(n, k) problem is at least as hard as solving a Collatz-like problem." is true in general.

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.

The Busy Beaver problem sits somewhere on the range from "intellectual curiosity" to "lens that allows us to view the edges of uncomputability". I would guess that the majority of people doing work here are hobbyists (including myself). In fact, when Tibor Rado first introduced BB, he introduced it as the "Busy Beaver Game", so it has had a playful energy since the beginning :)

His survey 3 years ago has kicked off quite a flurry of Busy Beaver activity of which my entire blog and https://bbchallenge.org/ are a couple examples.

Thank you! I'm so glad to hear!

Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem."

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 :)

The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you say, that would prove whether ZFC is consistent. But in order for us mere mortals to compute BB(748) we would effectively need to figure out if this specific 748-state TM ever halted (along with all the other 748-state TMs).

I'm the author. That's a great summary of the background, thanks! As you say, this post is extremely in the weeds analyzing a single Turing Machine's behavior. I wrote this post mainly aimed at people in the bbchallenge.org project or who have spent time analyzing Skelet's machines previously.

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).

Yes, that's correct. https://www.sligocki.com/2021/07/17/bb-collatz.html has a bit of background that's probably relevent here ... but this content is quite niche, heh :)

Thanks! I just figured out how to get MathJax working with github pages and used it to its full extent!

It's a good question. Yes and no. If the "God of Busy Beaver" told us a value of BB(n) (for large enough n) then that would reduce some math problems to "simply" running a TM for that many steps and seeing if it halted. However, there are (at least) two issues with this: (1) As we can see, the number of steps will be unbelievably large (even just for 6-states, 2-symbols!), so it won't really be practical to run a TM that long and (2) The only known way to prove BB(n) numbers is by directly proving the halting / non-halting of every single TM of that size ... so, in other words, we will not know BB(n) until we have already proven all the interesting math that can be encoded in n-state TMs!

Hello, I'm the author. Ask me anything :)

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?