Hacker News Reader

Comment by nickdrozd | Hacker News Reader

It is sometimes thought that extremely long-running Turing machine programs must be deeply complicated, or "spaghetti code". This new reigning champion program is a counterexample. All things considered, it is relatively simple.

There are three states: A, B, C. (States are just like goto targets in C.) State B passes control to A and C, but states A and C don't "know about" each other; they only pass control back to B. This is a sort of modular construction, whereas in true spaghetti code each state would be able to pass to all the others.

This program has some other interesting features. It never prints a blank (that is, whenever it scans a 0, it prints 1, 2, or 3). Additionally, every instruction changes either the state or the color -- there are no "lazy instructions" like B1 -> 1LB that just move position without changing anything else.

View on HN

There is some debate in the bbchallenge project regarding the current long-running champions: do their properties reflect those of the actual longest-running machine of that size, or are their properties just the easiest to automatically search for and prove things about, as a kind of streetlamp effect? There's no way to know, until the entire search space has been ruled out, either definitely or heuristically. (Every size past BB(5, 2) contains chaotic, pseudorandom machines that are expected to run forever, but can't be proven to do so without big advances in number theory.)

Though I suspect that no long-running machine can be utterly chaotic, at least when you look at the patterns it produces on the tape. To run for a long time, a machine must simulate some sort of higher-level rule: if it were dumping symbols on the tape at random, then it would very soon reach a halting configuration, a cyclical configuration, or some other simplified pattern. Still, one can have long-running machines that do simulate something chaotic on a higher level, spending an inordinate amount of time between each high-level step until it halts.

At a high level, wouldn’t you expect Champions to be chaotic in the limit? As in, the halting problem tells us that any increasing sequence of Champions is not computable.

Yes, for a busy beaver properly defined in information theoretic terms, like BBλ2 [1], one can prove that its champions must be incompressible up to some constant. Mikhail Andreev's article "Busy Beavers and Kolmogorov complexity" [2] explores these connections.

[1] https://oeis.org/A361211

[2] https://arxiv.org/pdf/1703.05170

> streetlamp effect

I agree completely, all of these kinds of conjectures are shaped by what is detectable. If there are any "dark matter" programs out there, they by definition will be difficult to find. That said, I find it entirely plausible that the champions will win by exploiting complex and exotic mathematical facts, while the implementations of the math do not themselves need to be complex or exotic at the code level.

More rambling thoughts about this: https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...

Yeah, thankfully we're still in the range where halting machines are at least estimable in terms of inductive notations like the up-arrow. But as the machines gain more breathing room for working with variable-length data, we can start getting monsters like the TREE sequence.

Handwaving here, but I think longest running machines can't follow a specific structure in general.

Rough sketch of an argument:

Let's construct a number from all intermediate states of the machine concatenated. The number of digits of this number should correspond to the runtime (sketchy). We only care about the halting machines, so it's finite. We know that it must be unique because if a smaller machine computes the same number, we could get a bigger number by simply running the smaller program and doing other nonsense. That means the biggest programs are komolgorov optimal, and the numbers themselves should be k-trivial and thus nearly but not quite computable. Since they're not computable, the programs themselves can't follow a structure to generate them (since that would be computable in turn for larger values).

Of course, there can't be some grand global structure to describe all the champions in one go. But there could be properties that many have in common, e.g., predominantly consisting some number of nested recursions, characterized by some transfinite ordinal. For instance, this particular machine recurses over the first several hyperoperations.

> whereas in true spaghetti code each state would be able to pass to all the others.

An n-state s-symbol TM can transition to n other states at most (or halt). Thus, for s=4 or s=2, only the smallest of TMs could be spaghetti like.

Reply on news.ycombinator.com