The Turing Machine: A Brief Introduction

By

Home / The Turing Machine: A Brief Introduction

Alan Turing (1912-1954) “invented” the Turing machine as a theoretical model for exploring the limits of rules-based mathematics. This purely theoretical device became a powerful tool in the minds of mathematicians, and modern computers still follow many of its principles. The Turing machine is even being honored via art at the Intuition and Ingenuity exhibit in the 2012 Kinetica Art Fair.

Alan Turing Memorial: Image by Bernt Rostad

Components of a Turing Machine

The two important components of a Turing machine, or TM, are the “read/write head” and the “tape.” The machine deals with one cell of the tape at a time, similar to the way a movie projector works, except that the movie’s tape only moves in one direction, and the “head” only “reads” the film by shining light through one frame at a time. The Turing machine, however, can read and re-write the active cell, or move the tape either right or left to the next cell.

The Turing machine’s “head” also has a finite number of internal states. These correspond to a computer’s programmed instructions, along with some of its active memory. The most important states are the initial state and the “halt” state where no subsequent instruction is specified.

A Turing machine’s “tape” extends to infinity in at least one direction. The simplest TM only uses two tape symbols, corresponding to zero and one, or the colours “blank” and “grey.” However, any finite number of symbols may be permitted without making a TM more computationally powerful.

One can specify a Turing machine as a set of 4-tuples (current state, symbol in the current cell, next state, next action). The “next action” would either be “write this new value into the current cell” or “move in this direction.”

Leave a Comment