A New Record in Self-Cleaning Turing Machines
SCENARIO: It’s 1950, and a brand new Turing machine, the first of its kind, has been installed at a research facility. Lots of people want to use it, but the machine has just one tape. A program’s execution can be affected in undesirable ways by data left over on the tape from a previous program run, and so as a matter of etiquette the convention is adopted among the machine’s users that the tape is to be wiped clean after each use. Rather than cleaning the tape manually after program execution, the programmers soon figure out how to automate the wiping process by writing their programs with cleanup routines at the end. The Turing machine itself is eventually hacked so that it comes to a halt when and only when it detects that the tape is blank.
Now here’s a question: How long can an n-state k-color Turing machine program started on the blank tape run before wiping the tape clean? A basic search over the smaller program spaces yields the following early results:
