The Turing Machine
A tape, a head and a few rules: the essence of computing
Summary
A Turing machine is an imaginary machine that Alan Turing described in 1936 to explain what computing is: a tape of endless length, a head that reads and writes one cell of the tape, and a few rules of the form "in this state, if you read this, write that and move there". A machine this simple can carry out every calculation today's computers can. With the same machine, Turing also showed that there are questions no computer will ever be able to answer.
In depth
Turing's 1936 paper set out to answer David Hilbert's question: is there a mechanical method that decides whether any mathematical statement is true? Turing built a model of a machine by breaking down a person calculating with pencil and paper into the simplest possible steps. He then designed a universal machine that can read the description of any other machine and imitate it; this idea is the basis of today's stored-program computers. In the same paper he proved that no algorithm can always tell in advance whether a program will eventually halt (the halting problem). The busy beaver problem, posed by Tibor Radó in 1962, makes this limit concrete: for five-state machines the answer was only found in 2024.
Rate The Turing Machine
What did you think of this content? Click the stars to leave your rating.
Leave a Comment and Rating
Sign in to comment and rate. Membership is free.