What is a Turing Machine?
The movie The Imitation Game ends with the quote : “His machine was never perfected, though it generated a whole field of research into what became known as ‘Turing Machines‘. Today we call them ‘computers.’ ” The his here refers to the protagonist of the movie. Benedict Cumberbatch, who is the main protagonist, plays the role of Alan Turing. Turing in his celebrated 1936 paper “On Computable Numbers, with an Application to the Entscheidungs problem” introduced what he called automatic computing machines. This has now become the Turing Machine referred in the movie. What is this Turing machine?
Some time before Turing published his paper, Alonzo Church published a paper “An Unsolvable Problem of Elementary Number Theory.” Both of these papers were addressing one common problem which is the tenth of Hilbert’s 23 famous problems called the Entscheidungs problem. We shall not talk about it here. But let us make a remark that what we are seeing is the birth of the theory of computer science.
A Turing machine is a machine( a hypothetical one) which consists of an infinite tape with/without an input with a pointer which can move either left or right and while doing so can read from the tape and write onto the tape. Why the use of the word ‘hypothetical’? This is because it is not possible to have an infinite tape. Such a tape would require an infinite amount of building materials and there are only 
But the only condition is that the Turing machine has a ‘finite control‘. At each step the read/write pointer looks at the tape and reads the character and then decides what to do next. Having a finite control means that there can be only finitely many possible decisions. It then erases the present character and then decides and writes a character in that place(which may be the erased character) and moves to the left or to the right. One of the decisions may be to bring the Turing machine to a ‘halt‘.
Given an input the Turing can accept an input or may reject it. Thus we may think that a Turing machine runs in a finite time. However it may so happen that on a certain input the Turing machine continues to keep running forever and does not halt. So the Turing machine can take an input and accept it or reject it or may keep running forever.
There is another condition that the input to a Turing machine can include only a finite set of inputs. The set of characters is called the input alphabet. We may allow some additional writing privileges to the Turing machine to have some extra symbols to write. The set of all symbols that the Turing machine can write on the tape is called the tape alphabet. The input alphabet is a subset of the tape alphabet. The set of all words that the Turing machine accepts is called the language of the Turing machine.
Given a set of characters, i.e. an alphabet, a language is a subset of all possible words that can be made using that alphabet. A language is called recursively enumerable or Turing recognizable if there is a Turing machine which accepts all the words in that language. A language is called decidable if there is a Turing machine that accepts all words in that language and halts and rejects any word that is not in that language( such a Turing machine is called a total Turing machine).
But are there languages in both the classes? Well, we can see that if a language is decidable it is also Turing recognizable. So we can construct a Turing machine which accepts all inputs( all possible words from a given alphabet). There is no word that it rejects. Thus we have a language that is both decidable and Turing recognizable.
But are there languages that are not decidable or not even Turing recognizable? To answer this question we have to introduce the notion of a universal Turing machine, a Turing machine that can simulate any other Turing machine. It is possible to construct a Turing machine on which we can run any other Turing machine. This idea gave rise to the fact that we can run different programs on one single device. We can ask the question that given the description of a Turing machine and an input to the Turing machine can we decide whether there the Turing machine will halt on this input or keep going on forever. This problem is called the Halting problem. We can show that there is a universal Turing machine that can accept if the input is the description of a Turing machine and an input given to that Turing machine. However, it is not a total Turing machine. Thus, the halting problem is recursively enumerable but not decidable. We may also show that problem that whether a Turing machine does not halt on a given input is neither recursively enumerable nor decidable.
What if we have a machine that resembles a Turing machine in everything accept that it has two or more tapes and each tape with its own read write pointer. We may think that increasing the number of tapes may increase the capacity of Turing machines to accept more different kinds of languages. However this is not true. It can be shown that a Turing machine with one tape is equivalent to a Turing machine with 2 or more tapes. In fact, all of the machines that we can think of which perform finite number of operations in finitely time has been found to be either less powerful or equivalent to a Turing machine. Thus, a Turing machine is the best so far. A modern day computer is only an approximation to a Turing machine.
It is thought by most computer scientists that a Turing machine is the best possible machine that the human mind can think of. Infact a function is said to be computable if there is a Turing machine that takes as input the input to the function and writes the output on the tape and halts. Hence, we may say that this theory, known as the Church-Turing thesis, sets a limit to the human mind.
Image Courtesy : Shutterstock