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 e...| Something Something Programming
Suppose someone claims that a particular Turing machine program halts when run on the blank tape. How can this claim be verified? The obvious answer is to run it on the blank tape and see if it halts. But what if the program in fact does not halt? The verifier will be stuck running a non-halting program, waiting forever for a halt that will never come.| Something Something Programming
The goal of the Busy Beaver contest is to find n-state k-color Turing machine programs that run for as long as possible before halting. It’s basically an optimization problem: what is the longest finite computation that can squeezed out of a program of a certain length? Or from the flip-side: how much description can be packed into a program of a certain length?| Something Something Programming
Turing machine programs are sometimes represented as directed graphs. The vertices of the graph are the program’s states and the edges are transitions between states. The program’s print and shift instructions are relegated to being labels for the edges. Here’s an example:| Something Something Programming