The idea of Turing machines evolved from the examination of the entscheidungsproblem by David Hilbert, which asks to show the existence of an algorithm that can be used to solve all mathematical problems. This problem required a proper mathematical definition of an algorithm, which was provided by Church and Turing via the Church - Turing thesis, which stated that all problems that can be solved using algorithms are equivalent to solving them on a Turing machine.
A Turing machine is composed of four parts :
Program - A set of instructions that the machine can execute.
Finite state control - It consists of a set of states, denoted as q, that the machine can attain, as described by the program. It also possesses two special states called qstart and qhalt, which define the starting and halting conditions, respectively, of the program.
Tape - Consists of boxes labelled from 0 onwards till infinity, which can hold in them one of the three given kinds of symbols. First, a symbol to denote the start of the tape. Second, a letter from a system of alphabets (can be binary, English or anything else). Third, a symbol for blank.
Read-Write head - It is used to mark the box the program points to during execution.
A given Turing machine can be characterized by a unique natural number (1, 2, 3, ….), called the Turing number. This can be done by noting the fact that all natural numbers have a unique factorization as a product of powers of prime numbers (numbers having factors only 1 and itself). This implies given a natural number t, there is a map unique to that t, from the set of prime numbers to the set of whole numbers (0, 1, 2, 3, ….), whose work is to link a particular prime number to its highest power present in t. It is easy for us to build an algorithm to effect this map, and therefore by Church -Turing thesis, we can combine this algorithm to our Turing machine. Therefore we have a map unique to our machine, and that map is also unique to t, which means that t is unique to a particular machine.
With the idea of Turing numbers, we are able to create what is called a Universal Turing Machine (UTM) which can simulate any other kind of Turing machine. A UTM works like a Turing machine of Turing number t if we input t, followed by a blank, followed by the value we wish to operate on.
Using the Turing machine, Alan Turing showed that the halting problem, which asks if there is algorithm that checks if a Turing Machine with Turing number x operating on an arbitrary input y causes the machine to terminate or not, cannot have a definite solution. This shows the result of entscheidungsproblem that there will not exist an algorithm that can solve all mathematical problems (by virtue of a counter-example).
REFERENCE :
Quantum Computation and Quantum Information, Nielsen and Chuang