A Turing machine is a mathematical model of computation describing an imaginary machine that manipulates symbols according to a table of rules. The machine uses a head to draw on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet. The idea was conceived in 1936 by the British mathematician and computer scientist Alan Turing. By providing a mathematical description of a very simple device capable of arbitrary computations, Turing was able to prove properties of computation in general. In particular, Turing was able to give a negative answer to the so-called ‘decision problem’: the question of whether every mathematical statement is either provable or disprovable by an algorithm.
Formally, a Turing machine is a tuple M = (S,A,s0,f) which consists of: a finite set of states S; a finite alphabet A; an initial state s0; and a transition function f() which maps the set Sx(A∪{∅}) to the set (S∪{∅})xAx{-1,+1}, where x denotes the Cartesian product. The transition function f() specifies the next state transitioned to from the current state, which symbol to write in the cell pointed at by the head, and the next head movement, with -1 being a movement to the left +1 being a movement to the right. Note that the second argument of the transition function f() is taken from the set A∪{∅} rather than the set A to take into account the fact that the head may be pointing at a blank cell, denoted here by ∅.
Note also that the first output of the transition function is taken from the set S∪{∅} to take into account the fact that the machine may reach a terminal state at the next time step; the terminal state is again denoted here by ∅. An input string for the Turing machine M is a finite sequence (a1,a2,…,an) of elements of A which represents the initial configuration of the memory tape. Each input string (a1,a2,…,an) induces a (possibly infinite) sequence (s1,s2,…,st) of elements of S. The input string (a1,a2,…,an) is said to be accepted by M if the induced sequence (s1,s2,…,st) is finite; that is, if the machine reaches the terminal state. Let A* denote the set of all input strings for the Turing machine M. A language L over A is then defined as a subset of A*.
The language accepted by the Turing machine M is defined by L(M) = {a*∈ A* | M accepts a*}. If M accepts a* then let t(M,a*) denote the number of time steps until the Turing machine M terminates with input string a*, and if M does not accept a* then let t(M,a*) = ∞. Furthermore, given a natural number n let An denote the set of all input strings of length n and let T(M,n) denote the worst case run-time for M, defined by T(M,n) = max{t(M,an) | an∈ An}. Then we say that M runs in polynomial time if: (1) M accepts all input strings a* ∈ A*, and (2) there exists a constant c ≥ 0 and a positive integer k such that for all n, T(M,n) ≤ cnk; or equivalently, T(M,n) ∈ O(nk) using the so-called ‘big O’ notation.
We can then define the set P as the set of languages L such that L = L(M) for some Turing machine M which runs in polynomial time, in which case we say that the Turing machine M decides L in polynomial time. We further define the set NP as the set of languages L where there exists a binary relation R ⊂ A*xA* and a positive integer k such that: (1) for all input strings a* ∈ A*, a* is in the language L if and only if there exists b* ∈ A* such that (a*,b*) ∈ R and |b*| ∈ O(|a*|), and (2) the language L(R) over A∪{#} defined by L(R) = {a*#b* | (a*,b*) ∈ R} is in the set P. A Turing machine that decides L(R) is referred to as a verifier for the language L. In words, NP is the set of languages that can be verified in polynomial time.
It can be shown that P ⊆ NP. However it is not currently known whether P = NP or P ⊂ NP. This is a major unsolved problem in mathematics and computer science. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution. Informally, the problem is to determine whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved. Here, ‘quickly’ means an algorithm exists that solves the task and runs in polynomial time. If P ≠ NP, which is widely believed, there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
Aside from being an important problem in computational theory, it is claimed that a proof either way would have profound implications for cryptography, algorithm research, artificial intelligence, and other fields. Personally, though, I am skeptical of this claim. We have seen that a Turing machine is an idealized conception of a computer which assumes the existence of an infinite memory tape. Obviously in the real world no computer has an infinite memory. Can result about such idealized machines really tell us anything about the real world of finite-memory computers? I don’t think so. Moreover, I suspect the reason a solution to the problem has proven so elusive is directly related to this infinite-memory assumption. I shall return to this point in a future blog post.
Leave a Reply