What is a Turing machine? “A Turing machine is an idealised computing device consisting of a read/write head (or ‘scanner’) with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol–‘0’ or ‘1’, for example. This tape is the machine’s general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

The input that is inscribed on the tape before the computation starts must consist of a finite number of symbols. However, the tape is of unbounded length–for Turing’s aim was to show that there are tasks that these machines are unable to perform, even given unlimited working memory and unlimited time.”

Or read here:

You could say that the computer was invented twice – once by Charles Babbage and once by Alan Turing.

While Babbage’s machine was supposed to be a practical thing, Turing’s was just a machine of the mind. It was invented not to compute tables of numbers but to solve problems in logic and to probe the limits of computation and human thought. …

In Grammar and Torture we look at every computer science student’s nightmare – formal grammar – and meet the idea of a hierarchy of machines, ranging from the simple finite state machine to the Turing machine, which corresponds to different complexities of language, computer or human.

This is interesting but it also raises the question of what a Turing machine is and why did anyone ever bother to think up such an idea?

While a Turing machine does have connections with grammar and languages, it is so much more. But to start at the beginning…

There are some helpful illustrations in this explanation (click through to see them):

A Turing machine is a hypothetical machine thought of by the mathematician Alan Turing in 1936. Despite its simplicity, the machine can simulate ANY computer algorithm, no matter how complicated it is!

———

The Turing machine is hypothetical, an abstract mental model. But it turns out there exists something very much like a Turing machine in real life- it’s coded into our DNA.

“Had Turing known about DNA as a biological molecule

serving as memory in biological systems, carrying the instructions for life, he

may have grasped the remarkable similarity between DNA and his machine

tapes.”

The concept formed the basis of the digital computer and, as suggested

in [9], there is no better place in nature where a process similar to the way

Turing machines work can be found than in the unfolding of DNA transcription.

For DNA is a set of instructions contained in every living organism

empowering the organism to self-replicate. In fact it is today common, even

in textbooks, to consider DNA as the digital repository of the organism’s

development plan, and the organism’s development itself is not infrequently

thought of as a mechanical, computational process in biology.