A Busy Beaver champion derived from scratch | Hacker News Reader

A Busy Beaver champion derived from scratch

nickdrozd.github.io

99 pointsnickdrozd33 comments

Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse engineering showed that the program turns out to compute a variant of the Collatz function, where instead of C(n:odd)=3n+1, we have L(3k)=0 and L(3k+r)=L(5k+r+3). There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs), but this Collatz example doesn't satisfy that criterion. Thus the author suggests that the spaghetti conjecture is false.

Discussion: the whole thing is very encoding dependent, but if you figure the BB machine on N states is randomly distributed on all the N-state machines, then for the types of encodings being discussed, for large N, the flow graph has (I think) a high chance of being complete but that is not guaranteed. So that's a reason to think the conjecture is strictly false but approximately true.

The BB champ being a Collatz variant is iirc a well known approach to manually constructed BB champs. That is inspired by an old result (Conway's?) found in Jeff Lagarias's book on the 3n+1 problem. It says the generalized Collatz conjecture is Pi-0-2 complete so specific instances sound like a good place to look for functions that are on the edge of undecidability.

I wonder if anything is known about the arithmetic (not computational) complexity of random programs like that. I'm imaginging e.g. Shannon's theorem that most boolean functions on N inputs require exponentially many gates to compute. The analogy would be with the likelihood of functions on some parameter, expressed as N-state programs, being Pi-0-2 complete.

> we have L(3k)=0 and L(3k+r)=L(3k+r+3)

L(3k+r)=L(5k+r+3)

Oops, fixed.

I'm absolutely out of the loop and didn't even remember what a BB game is (that's why I clicked, TBH), but when reading your post the first thing that came to my mind was hydra games, as in "Goodstein's theorem". Goodstein sequences are known to reach 0, eventually (unlike the Collatz function, ironically), but that requires some absoulutely astronomical number of steps. I have no idea how complicated it is to encode, though. So, was it used in generating BBs as well?

The two most interesting facts about the Goodstein algorithm are 1) that it always halts (Goodstein's theorem); and that 2) in a certain narrow technical sense of the word "difficult", it is difficult to prove that the Goodstein algorithm always halts. The proof of this "difficulty" is called the Kirby-Paris theorem, described in the Wikipedia article about Goodstein's theorem. Goodstein proved the first of these two facts, and Kirby & Paris proved the second one some years later.

There are ways to concoct algorithms along the lines of Goodstein's, that are even harder to prove always halt, and that take even longer / grow even faster. I haven't heard of anyone using any of these as BB champions but it seems like an unsatisfying answer, since you already know they halt.

What is nicer about the Collatz and similar iterations is that you don't know whether they halt. So maybe your current champion takes 123456789 steps before halting, and you've got a Collatz parameter that you experimentally find runs for even more steps, but does will it eventually halt and become your new champion, or will it never halt? The only way to find out is keep running it, and similar keep running all the other parameters that, in your current knowledge, might or might not halt.

See https://googology.wikia.org for some fast-growing functions, such as the Buchholz hydra which grows much faster than Goodstein's.

While Goodstein sequences do get really long quite fast, they're not that easy to code. This binary lambda calculus program [1] may be the shortest possible, but still takes 351 bits. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] that potentially grows so much faster than Goodstein, that it's not even provable in ZFC [3].

[1] https://github.com/tromp/AIT/blob/master/goodstein.lam

[2] https://github.com/tromp/AIT/blob/master/laver.lam

[3] https://codegolf.stackexchange.com/questions/79620/laver-tab...

Thank you for that, the article is nice and your pragmatic summary goes very well with it.

> There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs)

Sorry, but can someone unpack this? "complete control flow graphs"? That sounds like it means that the states are some form of Kn and that from any state you can get to any other state with the appropriate symbol.

Yes, that is what it means. It is described in the page linked from where the article refers to the spaghetti conjecture.

Great writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically:

For N=0,1: the problem is trivaial/degenerate.

For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish.

For N=n+1: well we just proved it up till n, so it seems pretty unlikely that n+1 would be different, things don't really just suddenly change like that y'know?

QED

So I'm not too surprised that this conjecture is being called into question.

[1]: https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjec...

Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in its own right, but deserves a different label, since the beaver never halts but rather gets bored and wanders off.

ADHD Aardvark, maybe?

Makework Manatee?

Diligent Dingo

Prolific Pangolin

Interminable Ibex

Verbose Vervet

This thread reminds me of how Ubuntu has wonderfully memorable release codenames

Canonical missed a great opportunity by not naming 18.04 „Busy Beaver”.

That might have been a poor choice for Googleability.

On the contrary I’m always confused with these names, especially when sites refer by name only or year only. Bionic <-> 16, 18, 20? No clue. Focal minus Bionic is 4. Are these separated by one, two or four years? No idea, always have to google it.

> Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered.

What's the difference?

The machines used in the article don't have to halt whereas the busy beaver only admits Turing machines that halt. For the purpose of this article the Turing machine either has to halt or has to enter some kind of degenerate state where it can still technically run forever but is in some sense stuck in a trivial infinite loop. The precise details of this degenerate state are explained in this article:

https://nickdrozd.github.io/2021/01/14/halt-quasihalt-recur....

This degenerate state is known as quasihalting. The author points out that for the traditional busy beaver function, let's call it BB, then BB(4) = 107. For this modified busy beaver function, let's call it, QQ, QQ(4) ~= 33 million.

The article goes into some detail why considering Turing machines that quasi halt instead of strictly halting provides some insight into some interesting questions, notably the spaghetti code conjecture.

Hm, that reminds me -- the convention in the nand2tetris course (where you virtually build a computer and OS from circuit) was that your programs don't halt either, at the level of the machine code, you just send them into a (small) infinite loop.

They just showed that QQ(4)>32mil, the exact value is still not known. And that function L is a "champion" only in comparison to other functions checked by them. Proving the exact value of QQ(4) could be impossible in standard theories. QQ is uncomputable, afterall.

Can something really be called a Turing machine if it's not able to halt (or continue going) by itself?

In this case it appears that the author considers halting to be decided externally to the program, which is not the mechanism Turing machines use.

Hm. I'm not sure if you're asking what you want to ask.

The definition of a turing machine is not based on the halting property at all. A turing machine is defined as a 5 tuple (if I recall right) with some structure to the tuple elements and that's it. Infinitely running turing machines are just turing machines. The halting problem is actually based around the idea of halting, or non-halting turing machines.

Now, a busy beaver is defined as a turing machine which stops after making a mess of a certain size. So a TM that never stops cannot be a busy beaver by strict definition.

What I meant is that the usual formal definition of Turing machine includes a built-in notion of halting that works as such: the machine's state + the symbol under the head decides whether it halts or not at every step (regardless of the contents in the rest of the tape).

In the case of the OP's machine, this isn't the case if I understand correctly. So the OP's machine isn't really a Turing machine by the usual definition.

It does contain that definition, but non-halting is valid. The simplest definition has a set of states S, and a subset of states F called the final states. Given an input I, if the turing machine started on I, enters a state F eventually, the turing machine is considered 'halting' and accepts the input as part of it's described language, otherwise it is not. It is perfectly valid to define a turing machine with an empty set of final states. Or, in a functional sense, it is perfectly valid to define the predicate "has this halted?" as the constant false.

However, all turing machines with an empty set of final states accept the empty language, and the empty language only, making them rather boring.

As you said, machines that don't halt are offtopic, as they can't be busy beaver champions. The question I'm raising is about how halting works in Turing machines Vs the machine used in the OP.

There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations.

What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense.

Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)).

QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them.

Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.

a typo in the collatz description:

C (2k + 1) = C (3k + 2)

should be

C (2k + 1) = C (6k + 4)

yes, but note that those two are the same when C (2k) is applied as well. C (2k + 1) = C (3k + 2) saves you one step of computation, which can save you a lot of time if you're applying the steps.

So what does "colour" means with regards to Turing Machines?

I think it means the number of possible settings for 1 square of the tape. 2 colors = each square is either black or white, i.e. it's a binary machine.

Reply on news.ycombinator.com