The Turing machine

In 1936 Alan Turing wrote the article On computable numbers, with an application to the Entscheidungsproblem. In this article he introduced a theoretical device known as the "Turing machine." This wasn't a physical machine, but a mathematical model of computation.

• Components: A Turing machine consists of an infinite tape divided into cells, a read/write head that can move along the tape, and a set of internal states.
• Operation: The machine operates by reading a symbol on the tape, writing a new symbol, changing its internal state, and moving its read/write head left or right, all based on a set of predetermined rules: the program.

Will a Turing program stop?

In 1958 Martin Davis introduced the Halting Problem in its book Computability and Unsolvability. Martin Davis built directly on Turing's foundations by giving a precise formulation of what we now call the Halting Problem. While Turing had essentially discovered this undecidability result in his 1936 paper, Davis formalized it as a specific decision problem: "Given a Turing machine and an input, will the machine halt?"

Searching for the maximum number of steps

In 1961 Tibor Radó introduced the Busy Beaver (BB) problem in his article On Non-Computable functions. Tibor Radó's introduction of the Busy Beaver problem created a fascinating connection to both earlier works. The Busy Beaver function BB(n) asks: "What is the maximum number of steps a halting n-state Turing machine can take before halting?" Where n represents the number of states in the program. Radó proved this BB function is uncomputable, directly linking to the Halting Problem. The only way the Halting Problem could be solved, is by simply running any machine for BB(n) steps and declaring it non-halting if it hasn't stopped.

The transformation from Radó's 1961 theoretical paper to an actual computational challenge began almost immediately. Tibor Radó defined the Busy Beaver Competition in 1962, just one year after introducing the mathematical concept. This marked a crucial shift from pure theory to practical exploration of the limits of computation. The first major milestone came with Shen Lin and Tibor Radó's 1965 collaboration, where they published an article on proving BB(3). Tragically, Radó died later that year, but their work established the first rigorous methods for actually computing busy beaver values rather than just proving their existence. The challenge has attracted both professional mathematicians and amateur enthusiasts. BB(1) – BB(5) are currently found and the search for BB(6) is ongoing.

A Turing machine implementation

In 1972, Washington University professors Wesley Clark and Bob Arnzen likely made the first physical version of Turing's conceptual machine. Clark used the TOWTMTEWP ("The Only Working Turing Machine There Ever Was Probably") as an educational tool, demonstrating basic computer theory for his students. Today, the TOWTMTEWP is housed in the collection of The Henry Ford museum, a testament to its significance in the history of computing. Unfortunately, it is currently not on public display.

The Turing machine game

The Turing machine game as described in this project, combines this history into a real world game. The implementation contains:

• a turing tape, the playing board;
• a movable read head, represented by an arrow;
• the possibility to write 0 and 1 with pawns;
• and the several busy bever programs, represented by state cards.

I also defined a tape on which three symbols can be written, the 0, the 1 and the blank. That makes it easier to distinguish between written data and the blanco tape.