O'Reilly logo

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

17  Is Everything a Turing Machine?

No matter how well you understand the concept and workings of the Turing Machine, it won't help you actually build a computer. Digital computers are built from transistors or other switching mechanisms, such as relays or vacuum tubes. These transistors are assembled into logic gates that implement simple logical functions, which then form higher-level components such as registers and adders.1

The Turing Machine is built from — well, Turing never tells us. Turing didn't intend for his machines to function as blueprints for actual computers. The machines serve instead as a simplified abstract model of computation, whether performed by human or machine. Turing's initial purpose for creating the Turing Machine was the very specific goal of proving that there is no general decision procedure for first-order logic. Only later did the imaginary devices begin contributing to our understanding of the theory of computing. This transition took about 20 years, after which the Turing Machine became a subject of study within the discipline we now know as computer science.

Adapting the Turing Machine for purposes other than Turing's proof required that the machine be reformulated somewhat. Most of Turing's machines spend the rest of infinity computing the digits of some real number between 0 and 1. A much more common task in mathematics — as well as computer programming — is the computation of a function. A function requires one or more numbers as input, also ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required