Maybe the Spaghetti Code Conjecture is False

submited by

Style Pass

2021-09-25 18:30:05

The Spaghetti Code Conjecture says that Busy Beaver programs ought to be, in some sense, as complicated as possible. Scott Aaronson puts it this way:

Busy Beavers shouldn’t be “cleanly factorizable” into main routines and subroutines—but rather, the way to maximize runtime should be via “spaghetti code,” or a single n-state amorphous mass.

This vague conjecture was formulated as a sort of generalization of a more narrowly-scoped conjecture by Joshua Zelinsky. This conjecture says that the control flow graph of a Busy Beaver program ought to be strongly connected (i.e. that every node should be reachable from every other node). One concrete way to interpret the Spaghetti Code Conjecture is as a broad set of predictions about Busy Beaver graphs – that the entry and exit connections of nodes ought to be dispersed, or that reflexive nodes should be absent (or present), etc.

When I first heard the Spaghetti Code Conjecture, I thought it sounded like a good idea. I even had hopes that it could be used as the basis for a new form of program search. But I have come around to the belief that not only is the Spaghetti Code Conjecture of no practical use, it isn’t even true.