Turing machines were invented by Alan
Turing in 1936 as idealized models for the basic processes of mathematical calculation. Turing's main interest was showing what his machines could in principle make, not in finding out
what simple examples of them actually did. Indeed, even though
he had access to the necessary technology, Turing never explicitly simulated any
Turing machine on a computer.
Since Turing's time, Turing machines were extensively
used as abstract models in theoretical computer science. But in almost no cases has the explicit behavior of simple Turing machines been considered. In the early 1960s, however, Marvin
Minsky and others worked on finding the simplest Turing machines that
could exhibit certain properties. Most of their effort was devoted to finding
ingenious constructions for creating appropriate machines. But around 1961 they did
systematically study all 4096 2-state 2-color machines, and simulated the
behavior of some simple Turing machines on a computer. They found repetitive and
nested behavior, but did not investigate enough examples to discover the more
complex behavior shown in the main text.
As a descendant of abstract studies of Turing machines, Tibor
Radó in 1962 formulated what he called the Busy Beaver Problem: to find a
Turing machine with a specified number of states that "keeps busy" for as many
steps as possible before finally reaching a particular "halt state" (numbered 0
below). (A variant of the problem asks for the maximum number of black cells
that are left when the machine halts.) By 1966 the results for 2, 3 and 4 states were found: the maximum numbers of steps are 6, 21 and 107, respectively,
with 4, 5 and 13 final black cells.
The result for 5 states is still unknown, but a machine taking
47,176,870 steps and leaving 4098 black cells was found by Heiner
Marxen and Jürgen
Buntrock in 1990. Its rule is:
No hay comentarios.:
Publicar un comentario