Analysis of the (5,2)-BBB with BBB(M) > 1.7 * 10^502

[Pascal Michel]

In a mail on February 17, 2022, Shawn gave the following machine M with BBB(M) > 1.7 * 10^502:

1RB 1LC  1RC 0RD  0LB 0RC  0RE 1RD  1LE 1LA

In a mail on February 22, 2022, he gave an analysis of the machine, using configurations

 g(x,n,m) = ...0 bin(x) 1^n <E 1^m 0...

I give here a more detailed analysis, using these configurations.

Let g(x,0,m) = ...0 bin(x) (E0) 1^m 0...,

and, if n > 0, g(x,n,m) = ...0 bin(x) 1^(n - 1) (E1) 1^m 0...,

where bin(x) is the number x written in binary notation, and x is even if n > 0, because g(2x + 1,n,m) = g(x,n + 1,m).

Then we have:

(a) ...0(A0)0... --(8)--> g(0,1,3)

(b) if k > 0 or m > 0, g(2x,3k + 1,m) --(5k^2 + 2km + 15k + m + 6)--> g(4x + 2,5k + m,2)

(c) g(4x,3k + 2,m) --(5k^2 + 2km + 15k + m + 14) --> g(8x + 2,5k + m + 1,2)

(d) g(4x + 2,3k + 2,m) --(5k^2 + 2km + 15k + m + 12)--> g(8x + 2,5k + m + 1,2)

(e) if k > 0, g(2x,3k,m) --(5k^2 + 2km + 10k)--> g(x,0,5k + m)

(f) g(2x + 1,0,m) --(1)--> g(x,1,m + 1)

(g) if x > 0, g(2x,0,m)--(1)--> g(x,0,m + 1)

(h) if k > 0, g(0,3k,m) --(5k^2 + 2km + 5k - m - 1)--> ...0(D0)0... last state D

Then ...0(A0)0... --> last state D using 1971 transitions with configurations g(x,n,m).

Number of transitions of type

(a)     1

(b) 622

(c)   57

(d) 451

(e) 387

(f)  387

(g)  65

(h)    1

Note: a transition of type (e) is always followed by some (possibly none) transitions of type (g) and then a transition of type (f)..

Pascal

[Shawn Ligocki]

Thanks for sharing this analysis, Pascal! Knowing that you have a long history of analyzing TMs for Collatz-like behavior, I wonder if you could share any sort of general insights or intuition you've developed on the subject?

Specifically, after performing some of these analyses myself I'm left with the following (perhaps half-formed) thoughts and ideas and I would love to hear if you have any thoughts on them (or if you have different interests that intersect with these analyses):

Is there any theory around the average orbit lengths of random Collatz-like functions with random starting points? For example, it feels to me that if we have an arbitrary "pure Collatz-like function of type 3 -> b", say:

f(3k) undefined / halts

f(3k + 1) = bk + 3

f(3k + 2) = bk + 7

then, even if we do not know with certainty that all orbits halt (all iterations of f eventually become undefined) we can say that 1/3 of inputs immediately halt (f is undefined for them) and about 2/9 halt after 2 applications of f, etc. So, for example, if we know somehow (or can estimate) that, say, 1% of all 5x2 TMs simulate "pure Collatz-like functions of type 3 -> b", do you think we could make a prediction about roughly how well the best one would do?

Here's my thinking: Say that 1% (7 million) of the BBB 5x2 TMs simulate "pure Collatz-like functions of type 3 -> b", then I will guess that they each are sort of randomly sampling from the group of all "pure Collatz-like functions of type 3 -> b" and also randomly sampling among (small) initial values for the iteration. So, it feels reasonable to predict that approximately 2/3 will not halt after a single iteration of their f, ~4/9 will not halt after 2 iterations, ... ~(2/3)^k will not halt after k iterations. So, for example, I guess that (2/3)^39 ~= 1 / (7.3 million) will not halt after 39 iterations, so that (among our 7M TMs) the best will iterate approximately 40 times? (maybe ±5 or ±10, with some "confidence"?)

Or to put it another way, if I find a TM that iterates 30 times, should I be impressed and think it will be the winner? My intuition says no, there are probably 1/200k will last this long, I should keep searching to find one that iterates longer. But if I find one that iterates 50 times? Wow, truly spectacular luck, only 1/600M should have lasted that long. I can feel some confidence in predicting that no others (specifically simulating "pure Collatz-like functions of type 3 -> b") will likely iterate more times!

What do you feel about this sort of idea? I am excited about it as a tool for giving a sense for "how lucky" a TM was to have found an especially long orbit of a Collatz-like function. But also nervous about the vagueness of a lot of the language (guess, about, on average, intuition).

Thanks,

-Shawn

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CAC8KPfEB7ke2MHss74tZJ8GXzZ2jHx10S25iKKTP9XOWP5adOA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Pascal Michel]

I have no answer to your questions.

I think that there are very difficult questions, and that there is no publications about these questions.

Conway proved in 1972 that Collatz-like functions are a universal model of computation, and Rice proved in 1953 that any nontrivial question about a universal model of computation is undecidable (see "Rice's theorem" in Wikipedia).

Between decidable problems and undecidable Turing-complete problems, there are an infinity of Turing degrees, with an amazingly intricate structure according to Turing reduction, and we have absolutely no tools to place a problem within these degrees.

We can only either prove that a problem is decidable by giving an algorithm, or prove that a problem is Turing-hard by reducing a known Turing-complete problem to this problem.

While it is possible to classify Turing machine according to the numbers of states and symbols, with a finite number of machines in each class, I do not know any way to classify Collatz-like functions, with finite classes.

This makes difficult the notion of random Collatz-like function.

Pascal

[Shawn Ligocki]

Thanks for the detailed explanation, Pascal! Working in the world of Turing Machines and number theory, it is so much easier to ask a question than to answer it :/ I enjoyed reading about Rice's Theorem, thanks for sharing.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/71917c81-ec8c-439a-af1d-2f0fd0afe7a6n%40googlegroups.com.

[Nicholas Drozd]

Somewhat along these lines, there is a 2013 paper by Conway called "On
Unsettleable Arithmetical Problems''. He says that he believes the
Collatz conjecture and its variations to be neither provable nor
disprovable in any sense, despite being what he calls "probvious"
(probabilistically obvious).

[Shawn Ligocki]

Thanks Nick, this was a great read! And it gives me words for what I'm trying to talk about, probvious intuition and reasoning :)