đźš° This post is a continuation of â€śHalt, Quasihalt, Recurâ€ť. đźš°

Deciding whether a Turing machine is currently halted is trivial. All you have to do is check the machineâ€™s current state. If that state is the halt state, then itâ€™s halted. If it isnâ€™t, then it isnâ€™t.

As a termination condition, haltedness is convenient for the simulator implementor. Itâ€™s quick and itâ€™s cheap and itâ€™s easy. But for the Busy Beaver programmer, the requirement to halt is an onerous one. A program of n states and k colors has only nk transitions to work with, and one of those has to be a halt transition. The cost for detecting termination is offloaded from the simulator implementor to the programmer.

Suppose the simulator implementor is willing to bear the burden of detecting termination. What termination condition should be used? A machine is said to have quasihalted if it reaches a point past which some and only some of its internal states becomes unreachable. As a termination condition, quasihaltedness gives the programmer an enormous amount of expressivity. Unfortunately, it isnâ€™t decidable in general whether a machine is currently quasihalted; there are programs that quasihalt but cannot be proved to quasihalt. Thus it is impossible to implement as a termination condition.

Lin recurrence is a decidable predicate, and in theory it can be used as a termination condition. I donâ€™t know if there is a simple, non-technical description of Lin recurrence. It was devised by Shen Lin in order to prove the third Busy Beaver number. The way it works is that on every step of the machine, a copy of the current tape contents is stored away, along with the machineâ€™s current state and scanned color. Then on every step, every previous tape matching the current state and scanned color is compared to the current tape for the span of tape traversed between then and now. If there is a match, then the machine is said to be in recurrence. (Note that this method, the Lin algorithm, does not detect recurrence until after the recurrence has transpired for one period. It would be nice to able to detect recurrence as soon as it is entered.)

Implementing Lin recurrence as a termination condition is theoretically possible, but not practically. The Lin algorithm runs quadratic in the number steps the machine has run, meaning that a Turing machine that checks for recurrence will run slower the longer it runs. Itâ€™s like thereâ€™s a memory leak, which considering how the algorithm actually works is not so far from the truth.

đź›‚ EXERCISE đź›‚ Come up with a predicate that is feasible to implement as a termination condition for a Turing machine that does not need to be explicitly indicated by the programmer.

The Busy Beaver problem requires that programs be run starting on the blank tape. Ashes to ashes and dust to dust, so why not blank to blank? Just say that a machine terminates when its tape becomes blank again at some point after the first step. Call a program that leaves the tape blank a blanker. Or donâ€™t. Itâ€™s not a great name.

The blank tape termination condition is fairly cheap to implement as a termination condition. Thereâ€™s a trick to doing it right, but I wonâ€™t say what it is. Unlike haltingness, blankness doesnâ€™t take up space in the program, although it does fatally constrain the programmerâ€™s ability to leave anything on the tape. Remember though, weâ€™re not talking about general Turing machine programmers here. Weâ€™re talking about Busy Beaver programmers, who are insane. All theyâ€™re interested in is running programs for as long as possible. Who cares whatâ€™s left on the tape? Who cares what the program does, so long as it runs for a long time?

Just as halting gives rise to the Busy Beaver question and as quasihalting gives rise to the Beeping Busy Beaver question and as Lin recurrence gives rise to a question that still needs a catchy name, so too does the blank tape condition give rise to the Blanking Beaver question: what is the longest that an n-state k-color Turing machine program can run before leaving the tape blank, in a grim reminder of the ultimate futility of all endeavors?

đź›‚ EXERCISE đź›‚ Try to work out the âť·â‘ˇ Blanking Beaver champion by hand. Try to find the âť¸â‘ˇ and âť·â‘˘ champions by computer search, or by hand if youâ€™re ambitious or bored.

đź›‚ EXERCISE đź›‚ Come up with a catchy name for the question given rise to by Lin recurrence as the termination predicate.

The âť¸â‘ˇ Blanking Beaver champion program is `1RB 1LB 1LA 1LC 1RC 0LC`. It runs for 34 steps before blanking the tape. Here is its tape evolution over 40 steps:

This program uses its first six steps and states `A` and `B` to prepare a solid block of four marks. Then it switches to state `C`, never to reach another state again (and thus quasihalting). Over the course of the subsequent 28 steps that single state is miraculously able to clear the tape.

The preceding program description evinces a clear subroutine structure â€“ first arrange for the tape block to be filled in, then switch to the wipe state and wipe it. Indeed, this program appears to have been â€śconstructedâ€ť in a modular fashion. Its `A` and `B` states are identical to the âť·â‘ˇ halting champion, `1RB 1LB 1LA 1RH`, except that instead of halting, it transitions to the appended `C` state. The state transition graph is not strongly connected, contravening the Spaghetti Code Conjecture. (It isnâ€™t a proper counterexample though, since it can be dismissed as being â€śnot sufficiently largeâ€ť.)

The âťąâ‘ˇ Blanking Beaver champion reaches the blank tape in 66345 steps. That number may sound familiar, as the champions for quasihalting and Lin recurrence both terminate in 66349 steps. The presumptive champion program for all three termination conditions is the same: `1RB 0LC 1LD 0LA 1RC 1RD 1LA 0LD`. The different termination conditions are intended to be different ways of measuring the amount of complexity that can be fit into a program of a certain size. The fact that these unrelated predicates all seem to point to the same program suggests that in some sense, that program really is as complex as a âťąâ‘ˇ program can be.

Here are the best known values for these various sequences:

# âť·â‘ˇ

Predicate Steps Program
Quasihalt 6 `1RB 1LB 1LB 1LA`
Halt 6 `1RB 1LB 1LA 1RH`
Blank Tape 8 `1RB 0RA 1LB 1LA`
Recurrence 9 `1RB 0LB 1LA 0RB`

# âť¸â‘ˇ

Predicate Steps Program
Halt 21 `1RB 1RH 1LB 0RC 1LC 1LA`
Blank Tape 34 `1RB 1LB 1LA 1LC 1RC 0LC`
Quasihalt 55 `1RB 0LB 1LA 0RC 1LC 1LA`
Recurrence 101 `1RB 1LB 0RC 0LA 1LC 0LA`

# âť·â‘˘

Predicate Steps Program
Halt 38 `1RB 2LB 1RH 2LA 2RB 1LB`
Quasihalt 59 `1RB 2LB 1LA 2LB 2RA 0RA`
Blank Tape 77 `1RB 2LA 0RB 1LA 0LB 1RA`
Recurrence 165 `1RB 0LA ... 1LB 2LA 0RB`

# âťąâ‘ˇ

Predicate Steps Program
Halt 107 `1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA`
Blank Tape 66345 `1RB 0LC 1LD 0LA 1RC 1RD 1LA 0LD`
Quasihalt 66349 `1RB 0LC 1LD 0LA 1RC 1RD 1LA 0LD`
Recurrence 66349 `1RB 0LC 1LD 0LA 1RC 1RD 1LA 0LD`

Computability theory tells us that the quasihalting sequence must eventually dominate the halting sequence. Additionally, itâ€™s almost certainly the case that the recurrence and blank tape sequences also dominate the halting sequence, but that has not been proved. All that said, no values have been found that beat the halting sequence for the âťşâ‘ˇ and âť·â‘Ł cases. Finding new champions will not be easy.

đź›‚ EXERCISE đź›‚ This post makes two major changes to previously used terminology. What are the changes, and why were they made?

đź›‚ EXERCISE đź›‚ Fill in the following table to show the resource access required to implement each termination predicate:

Â  Halt Quasihalt Recurrence Blank Tape
Machine state Â  Â  Â  Â
Program Â  Â  Â  Â
Current tape contents Â  Â  Â  Â
Past tape contents Â  Â  Â  Â
Oracle for halting Â  Â  Â  Â
Other (please specify) Â  Â  Â  Â