There is an algorithm that can, at least in theory, and in likelihood, at most in theory, solve any problem, calculate the meaning of life, or simulate the universe even. Not very tractable in nature or entirely error proof, and rather pretentious, it otherwise is but a simple three-line marvel. As far as I know, it would sooner annihilate the universe than arrive at some grand epiphony. The algorithm more or less resembles the following:
- for each p:
- for each alg of length p:
- run alg for 2O(p) steps
- for each alg of length p:
That last step, for clarity, runs for some asymptotically exponential number of steps, beyond which the algorithm is guaranteed to loop indefinitely. We even solve the Halting Problem, were such a model allowed to execute.
Don’t attempt to write or execute the above in Python. It might require infinite patience, as they say. Theoretical algorithms are better served by theoretical computational models. But hey, let’s not capitalize on formalities.
If the last step didn’t impress with its intractableness, the second, inner loop also lends to interesting analysis. We effectively iterate over every single program of a certain length. And if the universal algorithm were to execute on a Turing Machine, (a reasonable expectation, considering that all reasonably-encoded computational models are equivalent to a polynomial factor) we iterate over all TMs of a given length.
There is another problem that aims for something very similar.
The Busy Beaver problem
The Busy Beaver problem yields to a particular Turing Machine model in analyzing the most amount of 1’s the TM of a certain length is capable of outputting on its tape. The Busy Beaver TM (BBTM) utilizes a binary alphabet of 1s and 0s and a card notation rather than the traditional TM notation of states and transitions. A card, effectively equivalent to a TM state, contains two rows of data of four items each:
| Input | Replace | Left/Right | Next card # |
|---|---|---|---|
| 0 | 0/1 | 0/1 | state |
| 1 | 0/1 | 0/1 | state |
A card defines the possible state transitions. Based on an input of 0 or 1, in which direction do we transition the tape head, which becomes the new symbol, and which becomes the next state (card)?
The formal problem definition is then what is the maximum number of 1’s printed by a BBTM upon halting?, assuming actually halting TMs. We disqualify any “rogue” TMs that do nothing but infinitely move along the tape in either direction, printing 1’s, or those that don’t contain a halt state.
For an n-card BBTM, the total number of states in the last column is then n+1, since we also include the halt state.
To determine the maximum number of 1’s printed by a n-card BBTM, eliminating those rogue TM cases, we must iterate and execute all n-card BBTMs, a computationally similar problem to iterating and executing all programs of a certain length in our universal algorithm. And how many unique n-card BBTMs are there?
N(n) = (4(n+1))2n. Remember, the n + 1 corresponds to the number of states plus the halt state.
And out of those N(n) TMs observed, what have we established as the maximum number of 1’s printed for each? Regretfully, this number grows horribly exponentially.
| n | max 1’s |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 3 | 6 |
| 4 | 13 |
| 5 | ≥4098 |
| 6 | ≥3.5 * 1018267 |
| 7 | ———————————- |
Many of the candidate BBTMs are still executing, uncertain if they will indefinitely loop or halt. And taking precise measurements for n much greater than 7 has shown to be a rather ambitious undertaking.
Questions, comments? Connect.