Algorithms and Data

Structures
Part 3: Computational Complexity and
Computability (Wikipedia Book 2014)

By Wikipedians

Editors: Reiner Creutzburg, Jenny Knackmuß

PDF generated using the open source mwlib toolkit. See [Link] for more information.
PDF generated at: Sun, 22 Dec 2013 14:54:36 UTC
Contents
Articles
Run time (program lifecycle phase) 1
Best, worst and average case 2
Big O notation 5
Computational complexity theory 17
Computability 29
Turing machine 34
Church–Turing thesis 51
Theoretical computer science 61

References
Article Sources and Contributors 64
Image Sources, Licenses and Contributors 66

Article Licenses
License 67
Run time (program lifecycle phase) 1

Run time (program lifecycle phase)

In computer science, runtime, or execution time is the time during which a program is running (executing), in
contrast to other phases of a program's lifecycle such as compile time, link time, load time, etc.
A run-time error is detected after or during the execution of a program, whereas a compile-time error is detected by
the compiler before the program is ever executed. Type checking, storage allocation, code generation, and code
optimization are typically done at compile time, but may be done at run time depending on the particular language
and compiler.

Implementation details
In certain cases, the execution of a program begins after a loader performs the necessary memory setup and links the
program with any dynamically linked libraries it needs. In some cases a language or implementation will have these
tasks done by the language runtime instead, though this is unusual in mainstream languages on common consumer
operating systems.
Some program debugging can only be performed (or is more efficient or accurate when performed) at runtime. Logic
errors and array bounds checking are examples. For this reason, some programming bugs are not discovered until the
program is tested in a "live" environment with real data, despite sophisticated compile-time checking and pre-release
testing. In this case, the end user may encounter a runtime error message.

Application errors (exceptions)

Exception handling is one language feature designed to handle runtime errors, providing a structured way to catch
completely unexpected situations as well as predictable errors or unusual results without the amount of inline error
checking required of languages without it. More recent advancements in runtime engines enable automated
exception handling which provides 'root-cause' debug information for every exception of interest and is implemented
independent of the source code, by attaching a special software product to the runtime engine.
Best, worst and average case 2

Best, worst and average case

In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least,
at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity,
but it could also be memory or other resources.
In real-time computing, the worst-case execution time is often of particular concern since it is important to know
how much time might be needed in the worst case to guarantee that the algorithm will always finish on time.
Average performance and worst-case performance are the most used in algorithm analysis. Less widely found is
best-case performance, but it does have uses: for example, where the best cases of individual tasks are known, they
can be used to improve the accuracy of an overall worst-case analysis. Computer scientists use probabilistic analysis
techniques, especially expected value, to determine expected running times.
The terms are used in other contexts; for example the worst- and best-case outcome of a planned-for epidemic,
worst-case temperature to which an electronic circuit element is exposed, etc. Where components of specified
tolerance are used, devices must be designed to work properly with the worst-case combination of tolerances and
external conditions.

Best-case performance for algorithm

The term best-case performance is used in computer science to describe an algorithm's behavior under optimal
conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first
element of the list.
Development and choice of algorithms is rarely based on best-case performance: most academic and commercial
enterprises are more interested in improving Average-case complexity and worst-case performance. Algorithms may
also be trivially modified to have good best-case running time by hard-coding solutions to a finite set of inputs,
making the measure almost meaningless.[1]

Worst-case versus average-case performance

Worst-case performance analysis and average case performance analysis have some similarities, but in practice
usually require different tools and approaches.
Determining what average input means is difficult, and often that average input has properties which make it
difficult to characterise mathematically (consider, for instance, algorithms that are designed to operate on strings of
text). Similarly, even when a sensible description of a particular "average case" (which will probably only be
applicable for some uses of the algorithm) is possible, they tend to result in more difficult analysis of equations.
Worst-case analysis has similar problems: it is typically impossible to determine the exact worst-case scenario.
Instead, a scenario is considered such that it is at least as bad as the worst case. For example, when analysing an
algorithm, it may be possible to find the longest possible path through the algorithm (by considering the maximum
number of loops, for instance) even if it is not possible to determine the exact input that would generate this path
(indeed, such an input may not exist). This gives a safe analysis (the worst case is never underestimated), but one
which is pessimistic, since there may be no input that would require this path.
Alternatively, a scenario which is thought to be close to (but not necessarily worse than) the real worst case may be
considered. This may lead to an optimistic result, meaning that the analysis may actually underestimate the true
worst case.
In some situations it may be necessary to use a pessimistic analysis in order to guarantee safety. Often however, a
pessimistic analysis may be too pessimistic, so an analysis that gets closer to the real value but may be optimistic
(perhaps with some known low probability of failure) can be a much more practical approach.
Best, worst and average case 3

When analyzing algorithms which often take a small time to complete, but periodically require a much larger time,
amortized analysis can be used to determine the worst-case running time over a (possibly infinite) series of
operations. This amortized worst-case cost can be much closer to the average case cost, while still providing a
guaranteed upper limit on the running time.
The worst-case analysis is related to the worst-case complexity.[2]

Practical consequences
Many problems with bad worst-case performance have good average-case performance. For problems we want to
solve, this is a good thing: we can hope that the particular instances we care about are average. For cryptography,
this is very bad: we want typical instances of a cryptographic problem to be hard. Here methods like random
self-reducibility can be used for some specific problems to show that the worst case is no harder than the average
case, or, equivalently, that the average case is no easier than the worst case.
On the other hand some algorithms like hash tables have very poor worst case behaviours, but a well written hash
table of sufficient size will statistically never give the worst case; the average number of operations performed
follows an exponential decay curve, and so the run time of an operation is statistically bounded.

Examples

Sorting algorithms

Algorithm Data Structure Time Complexity:Best Time Complexity:Average Time Complexity:Worst Space Complexity:Worst

Quick Sort Array O(n log(n)) O(n log(n)) O(n^2) O(log(n))

Merge sort Array O(n log(n)) O(n log(n)) O(n log(n)) O(n)

Bubble sort Array O(n) O(n^2) O(n^2) O(1)

Insertion sort Array O(n) O(n^2) O(n^2) O(1)

Selection sort Array O(n^2) O(n^2) O(n^2) O(1)

• Insertion sort applied to a list of n elements, assumed to be all different and initially in random order. On average,
half the elements in a list A1 ... Aj are less than elementAj+1, and half are greater. Therefore the algorithm
compares the j+1-st element to be inserted on the average with half the already sorted sub-list, so tj = j/2. Working
out the resulting average-case running time yields a quadratic function of the input size, just like the worst-case
running time.
• Quicksort applied to a list of n elements, again assumed to be all different and initially in random order. This
popular sorting algorithm has an average-case performance of O(n log n), which contributes to making it a very
fast algorithm in practice. But given a worst-case input, its performance degrades to O(n2).

Data structures
Best, worst and average case 4

Data Time Time Time Time Time Time Time Time Space
structure Complexity: Complexity: Complexity: Complexity: Complexity: Complexity: Complexity: Complexity: Complexity:
Avg: Avg: Search Avg: Avg: Worst: Worst: Worst: Worst: Worst
Indexing Insertion Deletion Indexing Search Insertion Deletion

Basic O(1) O(n) - - O(1) O(n) - - O(n)

Array

Dynamic O(1) O(n) O(n) - O(1) O(n) O(n) - O(n)

array

Singly O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
linked list

Doubly O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
linked list

Hash - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)

table

Binary - O((log n)) O((log n)) O((log n)) - O(n) O(n) O(n) O(n)
search
tree

B-tree - O((log n)) O((log n)) O((log n)) - O((log n)) O((log n)) O((log n)) O(n)

Red-black - O((log n)) O((log n)) O((log n)) - O((log n)) O((log n)) O((log n)) O(n)
tree

AVL tree - O((log n)) O((log n)) O((log n)) - O((log n)) O((log n)) O((log n)) O(n)

• Linear search on a list of n elements. In the worst case, the search must visit every element once. This happens
when the value being searched for is either the last element in the list, or is not in the list. However, on average,
assuming the value searched for is in the list and each list element is equally likely to be the value searched for,
the search visits only n/2 elements.

Graph search

Node/Edge management Storage Add vertex Add edge Remove vertex Remove edge Query

Adjacency list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|V|)

incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)

Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)

incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

References
[1] Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".
[2] Worst-case complexity (http:/ / www. fsz. bme. hu/ ~szirmay/ ray6. pdf)

• [Link]
Big O notation 5

Big O notation
In mathematics, big O notation
describes the limiting behavior of a
function when the argument tends
towards a particular value or infinity,
usually in terms of simpler functions. It
is a member of a larger family of
notations that is called Landau
notation, Bachmann–Landau
notation (after Edmund Landau and
Paul Bachmann), or asymptotic
notation. In computer science, big O
notation is used to classify algorithms
by how they respond (e.g., in their
processing time or working space
requirements) to changes in input size.
In analytic number theory, it is used to
estimate the "error committed" while
replacing the asymptotic size, or
asymptotic mean size, of an
arithmetical function, by the value, or Example of Big O notation: f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g.,
x0 = 5) such that f(x) < cg(x) whenever x > x0.
mean value, it takes at a large finite
argument. A famous example is the
problem of estimating the remainder term in the prime number theorem.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate
may be represented using the same O notation. The letter O is used because the growth rate of a function is also
referred to as order of the function. A description of a function in terms of big O notation usually only provides an
upper bound on the growth rate of the function. Associated with big O notation are several related notations, using
the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.
Big O notation is also used in many other fields to provide similar estimates.

Formal definition
Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

if and only if there is a positive constant M such that for all sufficiently large values of x, f(x) is at most M multiplied
by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real
number x0 such that

In many contexts, the assumption that we are interested in the growth rate as the variable x goes to infinity is left
unstated, and one writes more simply that f(x) = O(g(x)). The notation can also be used to describe the behavior of f
near some real number a (often, a = 0): we say

if and only if there exist positive numbers δ and M such that

Big O notation 6

If g(x) is non-zero for values of x sufficiently close to a, both of these definitions can be unified using the limit
superior:

if and only if

Example
In typical usage, the formal definition of O notation is not used directly; rather, the O notation for a function f(x) is
derived by the following simplification rules:
• If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
• If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.
For example, let , and suppose we wish to simplify this function, using O notation, to
describe its growth rate as x approaches infinity. This function is the sum of three terms: 6x4, −2x3, and 5. Of these
three terms, the one with the highest growth rate is the one with the largest exponent as a function of x, namely 6x4.
Now one may apply the second rule: 6x4 is a product of 6 and x4 in which the first factor does not depend on x.
Omitting this factor results in the simplified form x4. Thus, we say that f(x) is a "big-oh" of (x4). Mathematically, we
can write f(x) = O(x4). One may confirm this calculation using the formal definition: let f(x) = 6x4 − 2x3 + 5 and
g(x) = x4. Applying the formal definition from above, the statement that f(x) = O(x4) is equivalent to its expansion,

for some suitable choice of x0 and M and for all x > x0. To prove this, let x0 = 1 and M = 13. Then, for all x > x0:

so

Usage
Big O notation has two main areas of application. In mathematics, it is commonly used to describe how closely a
finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic
expansion. In computer science, it is useful in the analysis of algorithms. In both applications, the function g(x)
appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order
terms. There are two formally close, but noticeably different, usages of this notation: infinite asymptotics and
infinitesimal asymptotics. This distinction is only in application and not in principle, however—the formal definition
for the "big O" is the same for both cases, only with different limits for the function argument.
Big O notation 7

Infinite asymptotics
Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it
takes to complete a problem of size n might be found to be T(n) = 4n2 − 2n + 2. As n grows large, the n2 term will
come to dominate, so that all other terms can be neglected—for instance when n = 500, the term 4n2 is 1000 times as
large as the 2n term. Ignoring the latter would have negligible effect on the expression's value for most purposes.
Further, the coefficients become irrelevant if we compare to any other order of expression, such as an expression
containing a term n3 or n4. Even if T(n) = 1,000,000n2, if U(n) = n3, the latter will always exceed the former once n
grows larger than 1,000,000 (T(1,000,000) = 1,000,0003= U(1,000,000)). Additionally, the number of steps depends
on the details of the machine model on which the algorithm runs, but different types of machines typically vary by
only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what
remains: we write either

or

and say that the algorithm has order of n2 time complexity. Note that "=" is not meant to express "is equal to" in its
normal mathematical sense, but rather a more colloquial "is", so the second expression is technically accurate (see
the "Equals sign" discussion below) while the first is a common abuse of notation.[1]

Infinitesimal asymptotics
Big O can also be used to describe the error term in an approximation to a mathematical function. The most
significant terms are written explicitly, and then the least-significant terms are summarized in a single big O term.
For example,

expresses the fact that the error, the difference , is smaller in absolute value than some
constant times when is close enough to 0.

Properties
If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order
of f(n). For example

In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard
lower-order terms of the polynomial. O(nc) and O(cn) are very different. If c is greater than one, then the latter grows
much faster. A function that grows faster than nc for any c is called superpolynomial. One that grows more slowly
than any exponential function of the form is called subexponential. An algorithm can require time that is both
superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization.
O(log n) is exactly the same as O(log(nc)). The logarithms differ only by a constant factor (since
) and thus the big O notation ignores that. Similarly, logs with different constant bases are
equivalent.
Exponentials with different bases, on the other hand, are not of the same order. For example, and are not of
the same order. Changing units may or may not affect the order of the resulting algorithm. Changing units is
equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm
runs in the order of n2, replacing n by cn means the algorithm runs in the order of , and the big O notation
ignores the constant . This can be written as . If, however, an algorithm runs in the order of
Big O notation 8

, replacing n with cn gives . This is not equivalent to in general. Changing of variable may affect the order of th
resulting algorithm. For example, if an algorithm's running time is O(n) when measured in terms of the number n of
digits of an input number x, then its running time is O(log x) when measured as a function of the input number x
itself, because n = Θ(log x).

Product

Sum

This implies , which means that is a

convex cone.
If f and g are positive functions,

Multiplication by a constant
Let k be a constant. Then:
if k is nonzero.

Multiple variables
Big O (and little o, and Ω...) can also be used with multiple variables. To define Big O formally for multiple
variables, suppose and are two functions defined on some subset of . We say

if and only if

For example, the statement

asserts that there exist constants C and M such that

where g(n,m) is defined by

Note that this definition allows all of the coordinates of to increase to infinity. In particular, the statement

(i.e., ) is quite different from

(i.e., ).
It is worth noting that Rodney R. Howell in his paper [2] "On Asymptotic Notation with Multiple Variables" claims
that it is impossible to define Big O notation in multiple variables in a way that implies the properties commonly
used in algorithms analysis.
Big O notation 9

Matters of notation

Equals sign
The statement "f(x) is O(g(x))" as defined above is usually written as f(x) = O(g(x)). Some consider this to be an
abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement
does not have. As de Bruijn says, O(x) = O(x2) is true but O(x2) = O(x) is not. Knuth describes such statements as
"one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like n = n2 from the
identities n = O(n2) and n2 = O(n2)." For these reasons, it would be more precise to use set notation and write
f(x) ∈ O(g(x)), thinking of O(g(x)) as the class of all functions h(x) such that |h(x)| ≤ C|g(x)| for some constant C.
However, the use of the equals sign is customary. Knuth pointed out that "mathematicians customarily use the = sign
as they use the word 'is' in English: Aristotle is a man, but a man isn't necessarily Aristotle."[3]

Other arithmetic operators

Big O notation can also be used in conjunction with other arithmetic operators in more complicated equations. For
example, h(x) + O(f(x)) denotes the collection of functions having the growth of h(x) plus a part whose growth is
limited to that of f(x). Thus,

expresses the same as

Example
Suppose an algorithm is being developed to operate on a set of n elements. Its developers are interested in finding a
function T(n) that will express how long the algorithm will take to run (in some arbitrary measurement of time) in
terms of the number of elements in the input set. The algorithm works by first calling a subroutine to sort the
elements in the set and then perform its own operations. The sort has a known time complexity of O(n2), and after
the subroutine runs the algorithm must take an additional time before it terminates. Thus the
overall time complexity of the algorithm can be expressed as

This can perhaps be most easily read by replacing O(n2) with "some function that grows asymptotically no faster
than n2 ". Again, this usage disregards some of the formal meaning of the "=" and "+" symbols, but it does allow one
to use the big O notation as a kind of convenient placeholder.

Declaration of variables
Another feature of the notation, although less exceptional, is that function arguments may need to be inferred from
the context when several variables are involved. The following two right-hand side big O notations have
dramatically different meanings:

The first case states that f(m) exhibits polynomial growth, while the second, assuming m > 1, states that g(n) exhibits
exponential growth. To avoid confusion, some authors use the notation

rather than the less explicit

Big O notation 10

Multiple usages
In more complicated usage, O(...) can appear in different places in an equation, even several times on each side. For
example, the following are true for

The meaning of such statements is as follows: for any functions which satisfy each O(...) on the left side, there are
some functions satisfying each O(...) on the right side, such that substituting all these functions into the equation
makes the two sides equal. For example, the third equation above means: "For any function , there
is some function such that ." In terms of the "set notation" above, the meaning is
that the class of functions represented by the left side is a subset of the class of functions represented by the right
side. In this use the "=" is a formal symbol that unlike the usual use of "=" is not a symmetric relation. Thus for
example does not imply the false statement .

Orders of common functions

Here is a list of classes of functions that are commonly encountered when analyzing the running time of an
algorithm. In each case, c is a constant and n increases without bound. The slower-growing functions are generally
listed first.

Notation Name Example

constant Determining if a number is even or odd; using a constant-size lookup table

double logarithmic Finding an item using interpolation search in a sorted array of uniformly distributed values.

logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all
operations in a Binomial heap.

fractional power Searching in a kd-tree

linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array;
adding two n-bit integers by ripple carry.

n log-star n Performing triangulation of a simple polygon using Seidel's algorithm. (Note

linearithmic, Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge
loglinear, or sort
quasilinear

quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive
implementation), Shell sort, quicksort (worst case), selection sort or insertion sort

polynomial or Tree-adjoining grammar parsing; maximum matching for bipartite graphs

algebraic

L-notation or Factoring a number using the quadratic sieve or number field sieve
sub-exponential

exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming;
determining if two logical statements are equivalent using brute-force search

factorial Solving the traveling salesman problem via brute-force search; generating all unrestricted
permutations of a poset; finding the determinant with expansion by minors; enumerating all
partitions of a set.
Big O notation 11

The statement is sometimes weakened to to derive simpler formulas for

asymptotic complexity. For any and , is a subset of for any , so
may be considered as a polynomial with some bigger order.

Related asymptotic notations

Big O is the most commonly used asymptotic notation for comparing functions, although in many cases Big O may
be replaced with Big Theta Θ for asymptotically tighter bounds. Here, we define some related notations in terms of
Big O, progressing up to the family of Bachmann–Landau notations to which Big O notation belongs.

Little-o notation
The relation is read as " is little-o of ". Intuitively, it means that grows much
faster than , or similarly, the growth of is nothing compared to that of . It assumes that f and g
are both functions of one variable. Formally, f(n) = o(g(n)) as n → ∞ means that for every positive constant there
exists a constant N such that

Note the difference between the earlier formal definition for the big-O notation, and the present definition of little-o:
while the former has to be true for at least one constant M the latter must hold for every positive constant ,
however small. In this way little-o notation makes a stronger statement than the corresponding big-O notation: every
function that is little-o of g is also big-O of g, but not every function that is big-O g is also little-o of g (for instance g
itself is not, unless it is identically zero near ∞).
If g(x) is nonzero, or at least becomes nonzero beyond a certain point, the relation f(x) = o(g(x)) is equivalent to

For example,
•
•
•
Little-o notation is common in mathematics but rarer in computer science. In computer science the variable (and
function value) is most often a natural number. In mathematics, the variable and function values are often real
numbers. The following properties can be useful:
•
•
•
• (and thus the above properties apply with most combinations of o and O).
As with big O notation, the statement " is " is usually written as , which is a
slight abuse of notation.
Big O notation 12

Big Omega notation

There are two very widespread and incompatible definitions of the statement

where is some real number, or , where and are real functions defined in a neighbourhood of ,
and where is positive in this neighbourhood.
The first one (chronologically) is used in analytic number theory, and the other one in computational complexity
theory. When the two subjects meet, this situation is bound to generate confusion.

The Hardy–Littlewood definition

In 1914 G.H. Hardy and J.E. Littlewood introduced the new symbol ,[4] which is defined as follows:

Thus is the negation of .

In 1918 the same authors introduced the two new symbols and ,[5] thus defined:

Hence is the negation of , and the negation of

.
Contrary to a later assertion of D.E. Knuth,[6] Edmund Landau did use these three symbols, with the same meanings,
in 1924.[7]
These Hardy-Littlewood symbols are prototypes, which after Landau were never used again exactly thus.
became , and became .
These three symbols , as well as (meaning that and
are both satisfied), are now currently used in analytic number theory.

Simple examples
We have
,
and more precisely
.
We have
,
and more precisely
;
however
.
Big O notation 13

The Knuth definition

In 1976 D.E. Knuth published a paper to justify his use of the -symbol to describe a stronger property. Knuth
wrote: "For all the applications I have seen so far in computer science, a stronger requirement […] is much more
appropriate". He defined

with the comment: "Although I have changed Hardy and Littlewood's definition of , I feel justified in doing so
because their definition is by no mean in wide use, and because there are other ways to say what they want to say in
the comparatively rare cases when their definition applies". However, the Hardy–Littlewood definition had been
well used for at least 25 years.[8]

Family of Bachmann–Landau notations

Notation Name Intuition Informal definition: for sufficiently Formal Definition

large ...

Big is bounded for some

Omicron; above by positive k or
Big O; (up to
Big Oh constant
factor)
asymptotically

Big Two Number theory: Number theory:

Omega definitions :
for infinitely
Number many values of n and for some Complexity theory:
theory: positive k
is not Complexity theory:
dominated by for some positive
k
asymptotically
Complexity
theory:

is bounded
below by
asymptotically

Big is bounded for

Theta both above some positive k1, k2
and below by

asymptotically

Small is , for every

Omicron; dominated by fixed positive number
Small O;
Small asymptotically
Oh

Small dominates , for every

Omega fixed positive number
asymptotically

On the is equal to
order of
asymptotically
Big O notation 14

Aside from the Big O notation, the Big Theta Θ and Big Omega Ω notations are the two most often used in computer
science; the small omega ω notation is occasionally used in computer science.
Aside from the Big O notation, the small o, Big Omega Ω and notations are the three most often used in number
theory; the small omega ω notation is never used in number theory.

Use in computer science

Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe
an asymptotic tight bound where using Big Theta Θ notation might be more factually appropriate in a given context.
For example, when considering a function , all of the following are generally
acceptable, but tightnesses of bound (i.e., numbers 2 and 3 below) are usually strongly preferred over laxness of
bound (i.e., number 1 below).
1. T(n) = O(n100), which is identical to T(n) ∈ O(n100)
2. T(n) = O(n3), which is identical to T(n) ∈ O(n3)
3. T(n) = Θ(n3), which is identical to T(n) ∈ Θ(n3).
The equivalent English statements are respectively:
1. T(n) grows asymptotically no faster than n100
2. T(n) grows asymptotically no faster than n3
3. T(n) grows asymptotically as fast as n3.
So while all three statements are true, progressively more information is contained in each. In some fields, however,
the Big O notation (number 2 in the lists above) would be used more commonly than the Big Theta notation (bullets
number 3 in the lists above) because functions that grow more slowly are more desirable. For example, if
represents the running time of a newly developed algorithm for input size , the inventors and users of the
algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making
an explicit statement about the lower asymptotic bound.

Extensions to the Bachmann–Landau notations

Another notation sometimes used in computer science is Õ (read soft-O): f(n) = Õ(g(n)) is shorthand for
f(n) = O(g(n) logk g(n)) for some k. Essentially, it is Big O notation, ignoring logarithmic factors because the
growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input
parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by
the logarithmic-growth factor(s). This notation is often used to obviate the "nitpicking" within growth-rates that are
stated as too tightly bounded for the matters at hand (since logk n is always o(nε) for any constant k and any ε > 0).
Also the L notation, defined as

is convenient for functions that are between polynomial and exponential.

Generalizations and related usages

The generalization to functions taking values in any normed vector space is straightforward (replacing absolute
values by norms), where f and g need not take their values in the same space. A generalization to functions g taking
values in any topological group is also possible. The "limiting process" x→xo can also be generalized by introducing
an arbitrary filter base, i.e. to directed nets f and g. The o notation can be used to define derivatives and
differentiability in quite general spaces, and also (asymptotical) equivalence of functions,
Big O notation 15

which is an equivalence relation and a more restrictive notion than the relationship "f is Θ(g)" from above. (It
reduces to if f and g are positive real valued functions.) For example, 2x is Θ(x), but 2x − x is not
o(x).

History (Bachmann–Landau, Hardy, and Vinogradov notations)

The symbol O was first introduced by number theorist Paul Bachmann in 1894, in the second volume of his book
Analytische Zahlentheorie ("analytic number theory"), the first volume of which (not yet containing big O notation)
was published in 1892.[9] The number theorist Edmund Landau adopted it, and was thus inspired to introduce in
1909 the notation o;[10] hence both are now called Landau symbols. These notations were used in applied
mathematics during the 1950s for asymptotic analysis. The big O was popularized in computer science by Donald
Knuth, who re-introduced the related Omega and Theta notations. Knuth also noted that the Omega notation had
been introduced by Hardy and Littlewood under a different meaning "≠o" (i.e. "is not an o of"), and proposed the
above definition. Hardy and Littlewood's original definition (which was also used in one paper by Landau) is still
used in number theory (where Knuth's definition is never used). In fact, Landau introduced in 1924, in the paper just
mentioned, the symbols ("rechts") and ("links"), precursors for the modern symbols ("is not smaller
than a small o of") and ("is not larger than a small o of"). Thus the Omega symbols (with their original
meanings) are sometimes also referred to as "Landau symbols". Also, Landau never used the Big Theta and small
omega symbols.
Hardy's symbols were (in terms of the modern O notation)
and
(Hardy however never defined or used the notation , nor , as it has been sometimes reported). It should also
be noted that Hardy introduces the symbols and (as well as some other symbols) in his 1910 tract "Orders of
Infinity", and makes use of it only in three papers (1910–1913). In the remaining papers (nearly 400!) and books he
constantly uses the Landau symbols O and o.
Hardy's notation is not used anymore. On the other hand, in the 1930s,[11] the Russian number theorist Ivan
Matveyevich Vinogradov introduced his notation , which has been increasingly used in number theory instead
of the notation. We have

and frequently both notations are used in the same paper.

The big-O, standing for "order of", was originally a capital omicron; today the identical-looking Latin capital letter O
is used, but never the digit zero.

References and Notes

[1] Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition (http:/ / highered. mcgraw-hill. com/ sites/ 0070131511/ )
[2] http:/ / citeseerx. ist. psu. edu/ viewdoc/ summary?doi=10. 1. 1. 110. 3078
[3] ( Unabridged version (http:/ / www-cs-staff. stanford. edu/ ~knuth/ ocalc. tex))
[4] G. H. Hardy and J. E. Littlewood, "Some problems of Diophantine approximation", Acta Mathematica 37 (1914), p. 225
[5] G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes »,
Acta Mathematica, vol. 41, 1918.
[6] Donald Knuth. "Big Omicron and big Omega and big Theta", SIGACT News, Apr.-June 1976, 18-24. (http:/ / www. phil. uu. nl/
datastructuren/ 10-11/ knuth_big_omicron. pdf)
[7] E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150.
[8] E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
[9] Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6, p. 25
[10] Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig 1909, p.883.
[11] See for instance "A new estimate for G(n) in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249-253.
Translated in English in: Selected works / Ivan Matveevič Vinogradov ; prepared by the Steklov Mathematical Institute of the Academy of
Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.
Big O notation 16

Further reading
• Paul Bachmann. Die Analytische Zahlentheorie. Zahlentheorie. pt. 2 Leipzig: B. G. Teubner, 1894.
• Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen. 2 vols. Leipzig: B. G. Teubner, 1909.
• G. H. Hardy. Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond, 1910.
• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition.
Addison–Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp. 107–123.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms,
Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation,
pp. 41–50.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages
226–228 of section 7.1: Measuring complexity.
• Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL ([Link]
~avigad/Papers/[Link])
• Paul E. Black, "big-O notation" ([Link] in Dictionary of
Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology.
11 March 2005. Retrieved December 16, 2006.
• Paul E. Black, "little-o notation" ([Link] in Dictionary of
Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology.
17 December 2004. Retrieved December 16, 2006.
• Paul E. Black, "Ω" ([Link] in Dictionary of Algorithms and
Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December
2004. Retrieved December 16, 2006.
• Paul E. Black, "ω" ([Link] in Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004.
Retrieved December 16, 2006.
• Paul E. Black, "Θ" ([Link] in Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.
Retrieved December 16, 2006.

External links
• Introduction to Asymptotic Notations ([Link]
pdf)
• Landau Symbols ([Link]
• O-Notation Visualizer: Interactive Graphs of Common O-Notations ([Link]
[Link])
• Big-O Notation – What is it good for ([Link]
Computational complexity theory 17

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and
mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating
those classes to each other. A computational problem is understood to be a task that is in principle amenable to being
solved by a computer, which is equivalent to stating that the problem may be solved by mechanical application of
mathematical steps, such as an algorithm.
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm
used. The theory formalizes this intuition, by introducing mathematical models of computation to study these
problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity
measures are also used, such as the amount of communication (used in communication complexity), the number of
gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the
roles of computational complexity theory is to determine the practical limits on what computers can and cannot do.
Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key
distinction between analysis of algorithms and computational complexity theory is that the former is devoted to
analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a
more general question about all possible algorithms that could be used to solve the same problem. More precisely, it
tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing
restrictions on the available resources is what distinguishes computational complexity from computability theory: the
latter theory asks what kind of problems can, in principle, be solved algorithmically.
Computational complexity theory 18

Computational problems

Problem instances
A computational problem can be
viewed as an infinite collection of
instances together with a solution for
every instance. The input string for a
computational problem is referred to as
a problem instance, and should not be
confused with the problem itself. In
computational complexity theory, a
problem refers to the abstract question
to be solved. In contrast, an instance of
this problem is a rather concrete
utterance, which can serve as the input
for a decision problem. For example,
consider the problem of primality
testing. The instance is a number (e.g.
15) and the solution is "yes" if the
number is prime and "no" otherwise
(in this case "no"). Stated another way,
the instance is a particular input to the
problem, and the solution is the output
corresponding to the given input. A traveling salesman tour through Germany’s 15 largest cities.

To further highlight the difference between a problem and an instance, consider the following instance of the
decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of
Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving
other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most
10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.

Representing problem instances

When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is
taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer,
mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in
binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists
in binary.
Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input
encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be
achieved by ensuring that different representations can be transformed into each other efficiently.
Computational complexity theory 19

Decision problems as formal languages

Decision problems are one of the central objects of study in
computational complexity theory. A decision problem is a special
type of computational problem whose answer is either yes or no,
or alternately either 1 or 0. A decision problem can be viewed as a
formal language, where the members of the language are instances
whose output is yes, and the non-members are those instances
whose output is no. The objective is to decide, with the aid of an
algorithm, whether a given input string is a member of the formal
language under consideration. If the algorithm deciding this
problem returns the answer yes, the algorithm is said to accept the
input string, otherwise it is said to reject the input.

An example of a decision problem is the following. The input is an

arbitrary graph. The problem consists in deciding whether the
given graph is connected, or not. The formal language associated
with this decision problem is then the set of all connected
graphs—of course, to obtain a precise definition of this language, A decision problem has only two possible outputs, yes
one has to decide how graphs are encoded as binary strings. or no (or alternately 1 or 0) on any input.

Function problems
A function problem is a computational problem where a single output (of a total function) is expected for every
input, but the output is more complex than that of a decision problem, that is, it isn't just yes or no. Notable examples
include the traveling salesman problem and the integer factorization problem.
It is tempting to think that the notion of function problems is much richer than the notion of decision problems.
However, this is not really the case, since function problems can be recast as decision problems. For example, the
multiplication of two integers can be expressed as the set of triples (a, b, c) such that the relation a × b = c holds.
Deciding whether a given triple is member of this set corresponds to solving the problem of multiplying two
numbers. Similarly, finding the minimum value of a mathematical function f(x) is equivalent to a search on k for the
problem of determining whether a feasible point exists for f(x)≤ k.

Measuring the size of an instance

To measure the difficulty of solving a computational problem, one may wish to see how much time the best
algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In
particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space
required, or any measure of complexity) is calculated as function of the size of the instance. This is usually taken to
be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input
size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve
a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?
If the input size is n, the time taken can be expressed as a function of n. Since the time taken on different inputs of
the same size can be different, the worst-case time complexity T(n) is defined to be the maximum time taken over all
inputs of size n. If T(n) is a polynomial in n, then the algorithm is said to be a polynomial time algorithm. Cobham's
thesis says that a problem can be solved with a feasible amount of resources if it admits a polynomial time algorithm.
Computational complexity theory 20

Machine models and complexity measures

Turing machine
A Turing machine is a mathematical model of a general computing
machine. It is a theoretical device that manipulates symbols contained
on a strip of tape. Turing machines are not intended as a practical
computing technology, but rather as a thought experiment representing
a computing machine—anything from an advanced supercomputer to a
mathematician with a pencil and paper. It is believed that if a problem
can be solved by an algorithm, there exists a Turing machine that
An artistic representation of a Turing machine
solves the problem. Indeed, this is the statement of the Church–Turing
thesis. Furthermore, it is known that everything that can be computed
on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular
automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to
analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine
is the most commonly used model in complexity theory.

Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines,
probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing
machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as
time or space) are bounded, some of these may be more powerful than others.
A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its
future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits.
The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that
use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing
machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future
actions from a given state. One way to view non-determinism is that the Turing machine branches into many
possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have
solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically
interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see
nondeterministic algorithm.

Other machine models

Many machine models different from the standard multi-tape Turing machines have been proposed in the literature,
for example random access machines. Perhaps surprisingly, each of these models can be converted to another
without providing any extra computational power. The time and memory consumption of these alternate models may
vary.[1] What all these models have in common is that the machines operate deterministically.
However, some computational problems are easier to analyze in terms of more unusual resources. For example, a
nondeterministic Turing machine is a computational model that is allowed to branch out to check many different
possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to
compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that
nondeterministic time is a very important resource in analyzing computational problems.
Computational complexity theory 21

Complexity measures
For a precise definition of what it means to solve a problem using a given amount of time and space, a computational
model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on
input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer
("yes" or "no"). A Turing machine M is said to operate within time f(n), if the time required by M on each input of
length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in
time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their
difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time
f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).
Analogous definitions can be made for space requirements. Although time and space are the most well-known
complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are
very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory
include communication complexity, circuit complexity, and decision tree complexity.
The complexity of an algorithm is often expressed using big O notation.

Best, worst and average case complexity

The best, worst and average case complexity refer to
three different ways of measuring the time complexity
(or any other complexity measure) of different inputs of
the same size. Since some inputs of size n may be faster
to solve than others, we define the following
complexities:

• Best-case complexity: This is the complexity of

solving the problem for the best input of size n.
• Worst-case complexity: This is the complexity of
solving the problem for the worst input of size n.
• Average-case complexity: This is the complexity of
solving the problem on an average. This complexity
Visualization of the quicksort algorithm that has average case
is only defined with respect to a probability performance .
distribution over the inputs. For instance, if all
inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined
with respect to the uniform distribution over all inputs of size n.

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of
integers that is given as the input. The worst-case is when the input is sorted or sorted in reverse order, and the
algorithm takes time O(n2) for this case. If we assume that all possible permutations of the input list are equally
likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in
half, also needing O(n log n) time.

Upper and lower bounds on the complexity of problems

To classify the computation time (or similar resources, such as space consumption), one is interested in proving
upper and lower bounds on the minimum amount of time required by the most efficient algorithm solving a given
problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise.
Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the
time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most
T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all
Computational complexity theory 22

possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms
known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem
requires showing that no algorithm can have time complexity lower than T(n).
Upper and lower bounds are usually stated using the big O notation, which hides constant factors and smaller terms.
This makes the bounds independent of the specific details of the computational model used. For instance, if
T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2).

Complexity classes

Defining complexity classes

A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the
following factors:
• The type of computational problem: The most commonly used problems are decision problems. However,
complexity classes can be defined based on function problems, counting problems, optimization problems,
promise problems, etc.
• The model of computation: The most common model of computation is the deterministic Turing machine, but
many complexity classes are based on nondeterministic Turing machines, Boolean circuits, quantum Turing
machines, monotone circuits, etc.
• The resource (or resources) that are being bounded and the bounds: These two properties are usually stated
together, such as "polynomial time", "logarithmic space", "constant depth", etc.
Of course, some complexity classes have complex definitions that do not fit into this framework. Thus, a typical
complexity class has a definition like the following:
The set of decision problems solvable by a deterministic Turing machine within time f(n). (This complexity
class is known as DTIME(f(n)).)
But bounding the computation time above by some concrete function f(n) often yields complexity classes that
depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear
time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing
machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time
complexities in any two reasonable and general models of computation are polynomially related" (Goldreich 2008,
Chapter 1.2). This forms the basis for the complexity class P, which is the set of decision problems solvable by a
deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.
Computational complexity theory 23

Important complexity classes

Many important complexity classes can be
defined by bounding the time or space used
by the algorithm. Some important
complexity classes of decision problems
defined in this manner are the following:

A representation of the relation among complexity classes

Complexity class Model of computation Resource constraint

DTIME(f(n)) Deterministic Turing machine Time f(n)

P Deterministic Turing machine Time poly(n)

EXPTIME Deterministic Turing machine Time 2poly(n)

NTIME(f(n)) Non-deterministic Turing machine Time f(n)

NP Non-deterministic Turing machine Time poly(n)

NEXPTIME Non-deterministic Turing machine Time 2poly(n)

DSPACE(f(n)) Deterministic Turing machine Space f(n)

L Deterministic Turing machine Space O(log n)

PSPACE Deterministic Turing machine Space poly(n)

EXPSPACE Deterministic Turing machine Space 2poly(n)

NSPACE(f(n)) Non-deterministic Turing machine Space f(n)

NL Non-deterministic Turing machine Space O(log n)

NPSPACE Non-deterministic Turing machine Space poly(n)

NEXPSPACE Non-deterministic Turing machine Space 2poly(n)

It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem.
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing
machines; AC and NC, which are defined using Boolean circuits and BQP and QMA, which are defined using
quantum Turing machines. #P is an important complexity class of counting problems (not decision problems).
Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.
Computational complexity theory 24

Hierarchy theorems
For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say)
computation time indeed defines a bigger set of problems. In particular, although DTIME(n) is contained in
DTIME(n2), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to
such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems
because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there
are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set
inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed
in order to increase the number of problems that can be solved.
More precisely, the time hierarchy theorem states that

.
The space hierarchy theorem states that

.
The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance,
the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us
that L is strictly contained in PSPACE.

Reduction
Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one
problem into another problem. It captures the informal notion of a problem being at least as difficult as another
problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we
say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as
Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as
polynomial-time reductions or log-space reductions.
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes
polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two
integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be
done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more
difficult than multiplication, since squaring can be reduced to multiplication.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of
problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for
X allows us to solve any problem in C. Of course, the notion of hard problems depends on the type of reduction
being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the
set of problems that are hard for NP is the set of NP-hard problems.
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in
C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the
class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most
likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem,
Π2, to another problem, Π1, would indicate that there is no known polynomial-time solution for Π1. This is because a
polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems
can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that
P = NP.
Computational complexity theory 25

Important open problems

P versus NP problem
The complexity class P is often seen as a mathematical
abstraction modeling those computational tasks that
admit an efficient algorithm. This hypothesis is called
the Cobham–Edmonds thesis. The complexity class
NP, on the other hand, contains many problems that
people would like to solve efficiently, but for which no
efficient algorithm is known, such as the Boolean
satisfiability problem, the Hamiltonian path problem
and the vertex cover problem. Since deterministic Diagram of complexity classes provided that P ≠ NP. The existence
Turing machines are special nondeterministic Turing of problems in NP outside both P and NP-complete in this case was
machines, it is easily observed that each problem in P is established by Ladner.

also member of the class NP.

The question of whether P equals NP is one of the most important open questions in theoretical computer science
because of the wide implications of a solution.[] If the answer is yes, many important problems can be shown to have
more efficient solutions. These include various types of integer programming problems in operations research, many
problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure
mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay
Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.

Problems in NP not known to be in P or NP-complete

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such
problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and
the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the
very few NP problems not known to be in P or to be NP-complete.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are
isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P,
NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not
NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level.[2]
Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph
isomorphism is not NP-complete. The best algorithm for this problem, due to Laszlo Babai and Eugene Luks has run
time 2O(√(n log(n))) for graphs with n vertices.
The integer factorization problem is the computational problem of determining the prime factorization of a given
integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No
efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic
systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and
co-UP[3]). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will
equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time
O(e(64/9)1/3([Link] 2)1/3(log ([Link] 2))2/3) to factor an n-bit integer. However, the best known quantum algorithm for
this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where
the problem lies with respect to non-quantum complexity classes.
Computational complexity theory 26

Separations between other complexity classes

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆
PP ⊆ PSPACE, but it is possible that P = PSPACE. If P is not equal to NP, then P is not equal to PSPACE either.
Since there are many known complexity classes between P and PSPACE, such as RP, BPP, PP, BQP, MA, PH,
etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal
would be a major breakthrough in complexity theory.
Along the same lines, co-NP is the class containing the complement problems (i.e. problems with the yes/no answers
reversed) of NP problems. It is believed[4] that NP is not equal to co-NP; however, it has not yet been proven. It has
been shown that if these two complexity classes are not equal then P is not equal to NP.
Similarly, it is not known if L (the set of all problems that can be solved in logarithmic space) is strictly contained in
P or equal to P. Again, there are many complexity classes between the two, such as NL and NC, and it is not known
if they are distinct or equal classes.
It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP.

Intractability
Problems that can be solved in theory (e.g., given infinite time), but which in practice take too long for their
solutions to be useful, are known as intractable problems.[5] In complexity theory, problems that lack
polynomial-time solutions are considered to be intractable for more than the smallest inputs. In fact, the
Cobham–Edmonds thesis states that only those problems that can be solved in polynomial time can be feasibly
computed on some computational device. Problems that are known to be intractable in this sense include those that
are EXPTIME-hard. If NP is not the same as P, then the NP-complete problems are also intractable in this sense. To
see why exponential-time algorithms might be unusable in practice, consider a program that makes 2n operations
before halting. For small n, say 100, and assuming for the sake of example that the computer does 1012 operations
each second, the program would run for about 4 × 1010 years, which is the same order of magnitude as the age of the
universe. Even with a much faster computer, the program would only be useful for very small instances and in that
sense the intractability of a problem is somewhat independent of technological progress. Nevertheless a polynomial
time algorithm is not always practical. If its running time is, say, n15, it is unreasonable to consider it efficient and it
is still useless except on small instances.
What intractability means in practice is open to debate. Saying that a problem is not in P does not imply that all large
cases of the problem are hard or even that most of them are. For example the decision problem in Presburger
arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times
in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less
than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability
problem.

History
An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by
Gabriel Lamé in 1844.
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous
foundations were laid out by various researchers. Most influential among these was the definition of Turing
machines by Alan Turing in 1936, which turned out to be a very robust and flexible notion of computer.
Fortnow & Homer (2003) date the beginning of systematic studies in computational complexity to the seminal paper
"On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard Stearns (1965), which laid out
the definitions of time and space complexity and proved the hierarchy theorems. Also, in 1965 Edmonds defined a
"good" algorithm as one with running time bounded by a polynomial of the input size.[6]
Computational complexity theory 27

According to Fortnow & Homer (2003), earlier papers studying problems solvable by Turing machines with specific
bounded resources include John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's
study of rudimentary sets (1961), as well as Hisao Yamada's paper on real-time computations (1962). Somewhat
earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity
measure.[7] As he remembers:
However, [my] initial interest [in automata theory] was increasingly set aside in favor of computational
complexity, an exciting fusion of combinatorial methods, inherited from switching theory, with the conceptual
arsenal of the theory of algorithms. These ideas had occurred to me earlier in 1955 when I coined the term
"signalizing function", which is nowadays commonly known as "complexity measure".
—Boris Trakhtenbrot, From Logic to Theoretical Computer Science – An Update. In: Pillars of Computer
Science, LNCS 4800, Springer 2008.
In 1967, Manuel Blum developed an axiomatic complexity theory based on his axioms and proved an important
result, the so-called, speed-up theorem. The field really began to flourish in 1971 when the US researcher Stephen
Cook and, working independently, Leonid Levin in the USSR, proved that there exist practically relevant problems
that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility
Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems,
each infamous for its computational intractability, are NP-complete.

Relationship between computability theory, complexity theory and formal language theory.

References
[1] See
[2] Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer
Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323
[3] Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. September 13, 2002. http:/ / weblog. fortnow.
com/ 2002/ 09/ complexity-class-of-week-factoring. html
[4] Boaz Barak's course on Computational Complexity (http:/ / www. cs. princeton. edu/ courses/ archive/ spr06/ cos522/ ) Lecture 2 (http:/ /
www. cs. princeton. edu/ courses/ archive/ spr06/ cos522/ lec2. pdf)
[5] Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) Introduction to Automata Theory, Languages, and Computation, Addison Wesley,
Boston/San Francisco/New York (page 368)
[6] Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture
[7] Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski Penzenskogo Pedinstituta (Transactions of the Penza
Pedagogoical Institute) 4, 75–87 (1956) (in Russian)
Computational complexity theory 28

Textbooks
• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach ([Link]
[Link]/theory/complexity/), Cambridge, ISBN 978-0-521-42426-4, Zbl 1193.68112 ([Link]
[Link]/zmath/en/search/?format=complete&q=an:1193.68112)
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity ([Link]
frontpage/0,11855,5-0-22-1519914-0,[Link]?referer=[Link]/cgi-bin/search_book.
pl?isbn=0-387-94883-X), Berlin, New York: Springer-Verlag
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons,
ISBN 978-0-471-34506-0
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective ([Link]
[Link]/~oded/[Link]), Cambridge University Press
• van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity,
MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 0-201-53082-1
• Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course
Technology, ISBN 0-534-95097-3
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of
NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5

Surveys
• Khalil, Hatem; Ulery, Dana (1976), A Review of Current Studies on Complexity of Algorithms for Partial
Differential Equations ([Link] ACM '76 Proceedings of the
1976 Annual Conference, p. 197, doi: 10.1145/800191.805573 ([Link]
• Cook, Stephen (1983), "An overview of computational complexity", Commun. ACM (ACM) 26 (6): 400–408,
doi: 10.1145/358141.358144 ([Link] ISSN 0001-0782 ([Link]
[Link]/issn/0001-0782)
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity" ([Link]
[Link]/~fortnow/papers/[Link]), Bulletin of the EATCS 80: 95–133
• Mertens, Stephan (2002), "Computational Complexity for Physicists", Computing in Science and Engg.
(Piscataway, NJ, USA: IEEE Educational Activities Department) 4 (3): 31–47, arXiv: cond-mat/0012185 (http://
[Link]/abs/cond-mat/0012185), doi: 10.1109/5992.998639 ([Link]
ISSN 1521-9615 ([Link]

External links
• The Complexity Zoo ([Link]
• Hazewinkel, Michiel, ed. (2001), "Computational complexity classes" ([Link]
[Link]?title=p/c130160), Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Computability 29

Computability
You might be looking for Computable function, Computability theory, Computation, or Theory of computation.
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability
theory within mathematical logic and the theory of computation within computer science. The computability of a
problem is closely linked to the existence of an algorithm to solve the problem.
The most widely-studied models of computability are the Turing-computable and μ-recursive functions, and the
lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as
well: computability notions weaker than Turing machines are studied in automata theory, while computability
notions stronger than Turing machines are studied in the field of hypercomputation.

Problems
A central idea in computability is that of a (computational) problem, which is a task whose computability can be
explored.
There are two key types of problems:
• A decision problem fixes a set S, which may be a set of strings, natural numbers, or other objects taken from some
larger set U. A particular instance of the problem is to decide, given an element u of U, whether u is in S. For
example, let U be the set of natural numbers and S the set of prime numbers. The corresponding decision problem
corresponds to primality testing.
• A function problem consists of a function f from a set U to a set V. An instance of the problem is to compute,
given an element u in U, the corresponding element f(u) in V. For example, U and V may be the set of all finite
binary strings, and f may take a string and return the string obtained by reversing the digits of the input (so
f(0101) = 1010).
Other types of problems include search problems and optimization problems.
One goal of computability theory is to determine which problems, or classes of problems, can be solved in each
model of computation.

Formal models of computation

A model of computation is a formal description of a particular type of computational process. The description often
takes the form of an abstract machine that is meant to perform the task at hand. General models of computation
equivalent to a Turing machine (See: Church–Turing thesis) include:
Lambda calculus
A computation consists of an initial lambda expression (or two if you want to separate the function and its
input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of
Beta reduction.
Combinatory logic
is a concept which has many similarities to -calculus, but also important differences exist (e.g. fixed point
combinator Y has normal form in combinatory logic but not in -calculus). Combinatory logic was
developed with great ambitions: understanding the nature of paradoxes, making foundations of mathematics
more economic (conceptually), eliminating the notion of variables (thus clarifying their role in mathematics).
μ-recursive functions
a computation consists of a μ-recursive function, i.e. its defining sequence, any input value(s) and a sequence
of recursive functions appearing in the defining sequence with inputs and outputs. Thus, if in the defining
Computability 30

sequence of a recursive function the functions and appear, then terms of the form 'g(5)=7' or 'h(3,2)=10'
appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries
above by using composition, primitive recursion or μ-recursion. For instance if , then for 'f(5)=3' to a
terms like 'g(5)=6' and 'h(3,6)=3' must occur above. The computation terminates only if the final term gives the
value of the recursive function applied to the inputs.
String rewriting systems
including Markov algorithm, that uses grammar-like rules to operate on strings of symbols; also Post canonical
system.
Register machine
is a theoretically interesting idealization of a computer. There are several variants. In most of them, each
register can hold a natural number (of unlimited size), and the instructions are simple (and few in number), e.g.
only decrementation (combined with conditional jump) and incrementation exist (and halting). The lack of the
infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its
role with Gödel numbering techniques: the fact that each register holds a natural number allows the possibility
of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriate huge natural number
— unambiguity of both representation and interpretation can be established by number theoretical foundations
of these techniques.
Turing machine
Also similar to the finite state machine, except that the input is provided on an execution "tape", which the
Turing machine can read from, write to, or move back and forth past its read/write "head". The tape is allowed
to grow to arbitrary size. The Turing machine is capable of performing complex calculations which can have
arbitrary duration. This model is perhaps the most important model of computation in computer science, as it
simulates computation in the absence of predefined resource limits.
Multi-tape Turing machine
Here, there may be more than one tape; moreover there may be multiple heads per tape. Surprisingly, any
computation that can be performed by this sort of machine can also be performed by an ordinary Turing
machine, although the latter may be slower or require a larger total region of its tape.
P′′
Like Turing machines, P′′ uses an infinite tape of symbols (without random access), and a rather minimalistic
set of instructions. But these instructions are very different, thus, unlike Turing machines, P′′ does not need to
maintain a distinct state, because all “memory-like” functionality can be provided only by the tape. Instead of
rewriting the current symbol, it can perform a modular arithmetic incrementation on it. P′′ has also a pair of
instructions for a cycle, inspecting the blank symbol. Despite its minimalistic nature, it has become the
parental formal language of an implemented and (for entertainment) used programming language called
Brainfuck.
In addition to the general computational models, some simpler computational models are useful for special, restricted
applications. Regular expressions, for example, specify string patterns in many contexts, from office productivity
software to programming languages. Another formalism mathematically equivalent to regular expressions, Finite
automata are used in circuit design and in some kinds of problem-solving. Context-free grammars specify
programming language syntax. Non-deterministic pushdown automata are another formalism equivalent to
context-free grammars.
Different models of computation have the ability to do different tasks. One way to measure the power of a
computational model is to study the class of formal languages that the model can generate; in such a way is the
Chomsky hierarchy of languages is obtained.
Other restricted models of computation include:
Computability 31

Deterministic finite automaton(DFA)

Also called a finite state machine. All real computing devices in existence today can be modeled as a finite
state machine, as all real computers operate on finite resources. Such a machine has a set of states, and a set of
state transitions which are affected by the input stream. Certain states are defined to be accepting states. An
input stream is fed into the machine one character at a time, and the state transitions for the current state are
compared to the input stream, and if there is a matching transition the machine may enter a new state. If at the
end of the input stream the machine is in an accepting state, then the whole input stream is accepted.
Nondeterministic finite automaton(NFA)
it is another simple model of computation, although its processing sequence is not uniquely determined. It can
be interpreted as taking multiple paths of computation simultaneously through a finite number of states.
However, it is possible to prove that any NFA is reducible to an equivalent DFA.
Pushdown automaton
Similar to the finite state machine, except that it has available an execution stack, which is allowed to grow to
arbitrary size. The state transitions additionally specify whether to add a symbol to the stack, or to remove a
symbol from the stack. It is more powerful than a DFA due to its infinite-memory stack, although only the top
element of the stack is accessible at any time.

Power of automata
With these computational models in hand, we can determine what their limits are. That is, what classes of languages
can they accept?

Power of finite state machines

Computer scientists call any language that can be accepted by a finite state machine a regular language. Because of
the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language
that is not regular, we must construct a language that would require an infinite number of states.
An example of such a language is the set of all strings consisting of the letters 'a' and 'b' which contain an equal
number of the letter 'a' and 'b'. To see why this language cannot be correctly recognized by a finite state machine,
assume first that such a machine M exists. M must have some number of states n. Now consider the string x
consisting of 'a's followed by 'b's.
As M reads in x, there must be some state in the machine that is repeated as it reads in the first series of 'a's, since
there are 'a's and only n states by the pigeonhole principle. Call this state S, and further let d be the number
of 'a's that our machine read in order to get from the first occurrence of S to some subsequent occurrence during the
'a' sequence. We know, then, that at that second occurrence of S, we can add in an additional d (where ) 'a's
and we will be again at state S. This means that we know that a string of 'a's must end up in the same
state as the string of 'a's. This implies that if our machine accepts x, it must also accept the string of
'a's followed by 'b's, which is not in the language of strings containing an equal number of
'a's and 'b's. In other words, M cannot correctly distinguish between a string of equal number of 'a's and 'b's and a
string with 'a's and 'b's.
We know, therefore, that this language cannot be accepted correctly by any finite state machine, and is thus not a
regular language. A more general form of this result is called the Pumping lemma for regular languages, which can
be used to show that broad classes of languages cannot be recognized by a finite state machine.
Computability 32

Power of pushdown automata

Computer scientists define a language that can be accepted by a pushdown automaton as a Context-free language,
which can be specified as a Context-free grammar. The language consisting of strings with equal numbers of 'a's
and 'b's, which we showed was not a regular language, can be decided by a push-down automaton. Also, in general, a
push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular.
This model of computation is thus strictly more powerful than finite state machines.
However, it turns out there are languages that cannot be decided by push-down automaton either. The result is
similar to that for regular expressions, and won't be detailed here. There exists a Pumping lemma for context-free
languages. An example of such a language is the set of prime numbers.

Power of Turing machines

Turing machines can decide any context-free language, in addition to languages not decidable by a push-down
automaton, such as the language consisting of prime numbers. It is therefore a strictly more powerful model of
computation.
Because Turing machines have the ability to "back up" in their input tape, it is possible for a Turing machine to run
for a long time in a way that is not possible with the other computation models previously described. It is possible to
construct a Turing machine that will never finish running (halt) on some inputs. We say that a Turing machine can
decide a language if it eventually will halt on all inputs and give an answer. A language that can be so decided is
called a recursive language. We can further describe Turing machines that will eventually halt and give an answer
for any input in a language, but which may run forever for input strings which are not in the language. Such Turing
machines could tell us that a given string is in the language, but we may never be sure based on its behavior that a
given string is not in a language, since it may run forever in such a case. A language which is accepted by such a
Turing machine is called a recursively enumerable language.
The Turing machine, it turns out, is an exceedingly powerful model of automata. Attempts to amend the definition of
a Turing machine to produce a more powerful machine have surprisingly met with failure. For example, adding an
extra tape to the Turing machine, giving it a 2-dimensional (or 3 or any-dimensional) infinite surface to work with
can all be simulated by a Turing machine with the basic 1-dimensional tape. These models are thus not more
powerful. In fact, a consequence of the Church-Turing thesis is that there is no reasonable model of computation
which can decide languages that cannot be decided by a Turing machine.
The question to ask then is: do there exist languages which are recursively enumerable, but not recursive? And,
furthermore, are there languages which are not even recursively enumerable?

The halting problem

The halting problem is one of the most famous problems in computer science, because it has profound implications
on the theory of computability and on how we use computers in everyday practice. The problem can be phrased:
Given a description of a Turing machine and its initial input, determine whether the program, when executed
on this input, ever halts (completes). The alternative is that it runs forever without halting.
Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the
tables and asking a Turing machine to answer a question about another Turing machine. It can be shown (See main
article: Halting problem) that it is not possible to construct a Turing machine that can answer this question in all
cases.
That is, the only general way to know for sure if a given program will halt on a particular input in all cases is simply
to run it and see if it halts. If it does halt, then you know it halts. If it doesn't halt, however, you may never know if it
will eventually halt. The language consisting of all Turing machine descriptions paired with all possible input
streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore
Computability 33

called non-computable or undecidable.

An extension of the halting problem is called Rice's Theorem, which states that it is undecidable (in general) whether
a given language possesses any specific nontrivial property.

Beyond recursively enumerable languages

The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever
when given input which is a representation of a Turing machine that does not itself halt. The halting language is
therefore recursively enumerable. It is possible to construct languages which are not even recursively enumerable,
however.
A simple example of such a language is the complement of the halting language; that is the language consisting of all
Turing machines paired with input strings where the Turing machines do not halt on their input. To see that this
language is not recursively enumerable, imagine that we construct a Turing machine M which is able to give a
definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually
halt. We can then construct another Turing machine that simulates the operation of this machine, along with
simulating directly the execution of the machine given in the input as well, by interleaving the execution of the two
programs. Since the direct simulation will eventually halt if the program it is simulating halts, and since by
assumption the simulation of M will eventually halt if the input program would never halt, we know that will
eventually have one of its parallel versions halt. is thus a decider for the halting problem. We have previously
shown, however, that the halting problem is undecidable. We have a contradiction, and we have thus shown that our
assumption that M exists is incorrect. The complement of the halting language is therefore not recursively
enumerable.

Concurrency-based models
A number of computational models based on concurrency have been developed, including the Parallel Random
Access Machine and the Petri net. These models of concurrent computation still do not implement any mathematical
functions that cannot be implemented by Turing machines.

Stronger models of computation

The Church-Turing thesis conjectures that there is no effective model of computing that can compute more
mathematical functions than a Turing machine. Computer scientists have imagined many varieties of
hypercomputers, models of computation that go beyond Turing computability.

Infinite execution
Imagine a machine where each step of the computation requires half the time of the previous step. If we normalize to
1 time unit the amount of time required for the first step, the execution would require

time to run. This infinite series converges to 2 time units, which means that this Turing machine can run an infinite
execution in 2 time units. This machine is capable of deciding the halting problem by directly simulating the
execution of the machine in question. By extension, any convergent series would work. Assuming that the series
converges to a value n, the Turing machine would complete an infinite execution in n time units.
Computability 34

Oracle machines
So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable
problems. For example, the Turing machine may have a "halting oracle" which answers immediately whether a given
Turing machine will ever halt on a given input. These machines are a central topic of study in recursion theory.

Limits of hyper-computation
Even these machines, which seemingly represent the limit of automata that we could imagine, run into their own
limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own
version of the halting problem. For example, an Oracle machine cannot answer the question of whether a given
Oracle machine will ever halt.

References
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part
Two: Computability Theory, Chapters 3–6, pp. 123–222.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1.
Chapter 3: Computability, pp. 57–70.
• S. Barry Cooper (2004). Computability Theory (1st ed.). Chapman & Hall/CRC. ISBN 978-1-58488-237-4.

Turing machine
Turing machines
Machine
• Universal Turing machine
• Alternating Turing machine
• Quantum Turing machine
• Non-deterministic Turing machine
• Read-only Turing machine
• Read-only right moving Turing machines
• Probabilistic Turing machine
• Multi-track Turing machine
• Turing machine equivalents
• Turing machine examples
Science

• Alan Turing
• Category:Turing machine

• v
• t
• e [1]
Turing machine 35

A Turing machine is a hypothetical device that manipulates symbols

on a strip of tape according to a table of rules. Despite its simplicity, a
Turing machine can be adapted to simulate the logic of any computer
algorithm, and is particularly useful in explaining the functions of a
CPU inside a computer.
The "Turing" machine was invented in 1936 by Alan Turing[2] who
called it an "a-machine" (automatic machine). The Turing machine is An artistic representation of a Turing machine
not intended as practical computing technology, but rather as a (Rules table not represented)
hypothetical device representing a computing machine. Turing
machines help computer scientists understand the limits of mechanical computation.
Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936
publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:
...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on
each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called
the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by
that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However,
the tape can be moved back and forth through the machine, this being one of the elementary operations
of the machine. Any symbol on the tape may therefore eventually have an innings.[3] (Turing 1948, p.
61)
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or
simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was
introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of
computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal
notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or "mechanical
procedure". Studying their abstract properties yields many insights into computer science and complexity theory.

Informal description
For visualizations of Turing machines, see Turing machine gallery.
The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are
symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a
finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1,
change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article
("On computable numbers, with an application to the Entscheidungsproblem", see also references below), Turing
imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical
rules slavishly (or as Turing puts it, "in a desultory manner").
More precisely, a Turing machine consists
of:
1. A tape divided into cells, one next to the
other. Each cell contains a symbol from
The head is always over a particular square of the tape; only a finite stretch of
some finite alphabet. The alphabet
squares is shown. The instruction to be performed (q4) is shown over the scanned
contains a special blank symbol (here square. (Drawing after Kleene (1952) p.375.)
written as '0') and one or more other
symbols. The tape is assumed to be
Turing machine 36

arbitrarily extendable to the left and to

the right, i.e., the Turing machine is
always supplied with as much tape as it
needs for its computation. Cells that have
not been written before are assumed to be
filled with the blank symbol. In some Here, the internal state (q1) is shown inside the head, and the illustration describes
the tape as being infinite and pre-filled with "0", the symbol serving as blank. The
models the tape has a left end marked
system's full state (its complete configuration) consists of the internal state, any
with a special symbol; the tape extends or non-blank symbols on the tape (in this illustration "11B"), and the position of the
is indefinitely extensible to the right. head relative to those symbols including blanks, i.e. "011B". (Drawing after
Minsky (1967) p. 121).
2. A head that can read and write symbols
on the tape and move the tape left and
right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
3. A state register that stores the state of the Turing machine, one of finitely many. Among these is the special start
state with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person
performing computations would ordinarily be in.
4. A finite table (occasionally called an action table or transition function) of instructions (usually quintuples
[5-tuples] : qiaj→qi1aj1dk, but sometimes quadruples [4-tuples]) that, given the state(qi) the machine is currently
in and the symbol(aj) it is reading on the tape (symbol currently under the head) tells the machine to do the
following in sequence (for the 5-tuple models):
• Either erase or write a symbol (replacing aj with aj1), and then
• Move the head (which is described by dk and can have values: 'L' for one step left or 'R' for one step right or
'N' for staying in the same place), and then
• Assume the same or a new state as prescribed (go to state qi1).
In the 4-tuple models, erasing or writing a symbol (aj1) and moving the head left or right (dk) are specified as
separate instructions. Specifically, the table tells the machine to (ia) erase or write a symbol or (ib) move the head
left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the
same instruction. In some models, if there is no entry in the table for the current combination of symbol and state
then the machine will halt; other models require all entries to be filled.
Note that every part of the machine (i.e. its state and symbol-collections) and its actions (such as printing, erasing
and tape motion) is finite, discrete and distinguishable; it is the potentially unlimited amount of tape that gives it an
unbounded amount of storage space.

Formal definition
Hopcroft and Ullman (1979, p. 148) formally defined a (one-tape) Turing machine as a 7-tuple
where
• is a finite, non-empty set of states
• is a finite, non-empty set of the tape alphabet/symbols
• is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the
computation)
• is the set of input symbols
• is the initial state
• is the set of final or accepting states.
• is a partial function called the transition function, where L is left shift,
R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)
Anything that operates according to these specifications is a Turing machine.
Turing machine 37

The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
•
•
• ("blank")
•
• (the initial state)
•
• see state-table below
Initially all tape cells are marked with 0.

State table for 3 state, 2 symbol busy beaver

Tape symbol Current state A Current state B Current state C

Write symbol Move tape Next state Write symbol Move tape Next state Write symbol Move tape Next state

0 1 R B 1 L A 1 L B

1 1 L C 1 R B 1 R HALT

Additional details required to visualize or implement Turing machines

In the words of van Emde Boas (1990), p. 6: "The set-theoretical object [his formal seven-tuple description similar to
the above] provides only partial information on how the machine will behave and what its computations will look
like."
For instance,
• There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and
writing symbols indefinitely.
• The shift left and shift right operations may shift the tape head across the tape, but when actually building a
Turing machine it is more practical to make the tape slide back and forth under the head instead.
• The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical
definition), but it is more common to think of it as stretching infinitely at both ends and being pre-filled with
blanks except on the explicitly given finite fragment the tape head is on. (This is, of course, not implementable in
practice.) The tape cannot be fixed in length, since that would not correspond to the given definition and would
seriously limit the range of computations the machine can perform to those of a linear bounded automaton.

Alternative definitions
Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always
done in such a way that the resulting machine has the same computational power. For example, changing the set
to , where N ("None" or "No-operation") would allow the machine to stay on the same tape
cell instead of moving left or right, does not increase the machine's computational power.
The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per
the convention of Turing/Davis (Turing (1936) in Undecidable, p. 126-127 and Davis (2000) p. 152):
(definition 1): (qi, Sj, Sk/E/N, L/R/N, qm)
( current state qi , symbol scanned Sj , print symbol Sk/erase E/none N , move_tape_one_square left
L/right R/none N , new state qm )
Other authors (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) adopt a different
convention, with new state qm listed immediately after the scanned symbol Sj:
Turing machine 38

(definition 2): (qi, Sj, qm, Sk/E/N, L/R/N)

( current state qi , symbol scanned Sj , new state qm , print symbol Sk/erase E/none N ,
move_tape_one_square left L/right R/none N )
For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.

Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
Current state Scanned symbol Print symbol Move tape Final (i.e. next) state 5-tuples

A 0 1 R B (A, 0, 1, R, B)

A 1 1 L C (A, 1, 1, L, C)

B 0 1 L A (B, 0, 1, L, A)

B 1 1 R B (B, 1, 1, R, B)

C 0 1 L B (C, 0, 1, L, B)

C 1 1 N H (C, 1, 1, N, H)

In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf Turing
in Undecidable, p. 126). He allowed for erasure of the "scanned square" by naming a 0th symbol S0 = "erase" or
"blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol Sk" or
"erase" (cf footnote 12 in Post (1947), Undecidable p. 300). The abbreviations are Turing's (Undecidable p. 119).
Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of
five-tuples:

Current m-configuration Tape Print-operation Tape-motion Final m-configuration 5-tuple 5-tuple 4-tuple
(Turing state) symbol (Turing state) comments

N1 qi Sj Print(Sk) Left L qm (qi, Sj, Sk, "blank" = S0,

L, qm) 1=S1, etc.

N2 qi Sj Print(Sk) Right R qm (qi, Sj, Sk, "blank" = S0,

R, qm) 1=S1, etc.

N3 qi Sj Print(Sk) None N qm (qi, Sj, Sk, "blank" = S0, (qi, Sj, Sk,
N, qm) 1=S1, etc. qm)

4 qi Sj None N Left L qm (qi, Sj, N, (qi, Sj, L,

L, qm) qm)

5 qi Sj None N Right R qm (qi, Sj, N, (qi, Sj, R,

R, qm) qm)

6 qi Sj None N None N qm (qi, Sj, N, Direct "jump" (qi, Sj, N,

N, qm) qm)

7 qi Sj Erase Left L qm (qi, Sj, E,

L, qm)

8 qi Sj Erase Right R qm (qi, Sj, E,

R, qm)

9 qi Sj Erase None N qm (qi, Sj, E, (qi, Sj, E,

N, qm) qm)

Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the
three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see Turing machine
examples.
Turing machine 39

Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions
(cf Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at Post–Turing
machine.

The "state"
The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most
commentators after Turing have used "state" to mean the name/designator of the current instruction to be
performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of
what he called the machine's "m-configuration", (its internal state) and the machine's (or person's) "state of progress"
through the computation - the current state of the total system. What Turing called "the state formula" includes both
the current instruction and all the symbols on the tape:
Thus the state of progress of the computation at any stage is completely determined by the note of instructions
and the symbols on the tape. That is, the state of the system may be described by a single expression
(sequence of symbols) consisting of the symbols on the tape followed by Δ (which we suppose not to appear
elsewhere) and then by the note of instructions. This expression is called the 'state formula'.
—Undecidable, p.139–140, emphasis added
Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current
"m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape
(Undecidable, p. 121); this he calls "the complete configuration" (Undecidable, p. 118). To print the "complete
configuration" on one line, he places the state-label/m-configuration to the left of the scanned symbol.
A variant of this is seen in Kleene (1952) where Kleene shows how to write the Gödel number of a machine's
"situation": he places the "m-configuration" symbol q4 over the scanned square in roughly the center of the 6
non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the right of the scanned square.
But Kleene refers to "q4" itself as "the machine state" (Kleene, p. 374-375). Hopcroft and Ullman call this composite
the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label,
m-configuration) to the left of the scanned symbol (p. 149).
Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure
below):
1A1
This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state
is A. Blanks (in this case represented by "0"s) can be part of the total state as shown here: B01; the tape has a single
1 on it, but the head is scanning the 0 ("blank") to its left and the state is B.
"State" in the context of Turing machines should be clarified as to which is being described: (i) the current
instruction, or (ii) the list of symbols on the tape together with the current instruction, or (iii) the list of symbols on
the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned
symbol.
Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.
Turing machine 40

Turing machine "state" diagrams

The table for the 3-state busy beaver ("P" = print/write a "1")
Tape symbol Current state A Current state B Current state C

Write symbol Move tape Next state Write symbol Move tape Next state Write symbol Move tape Next state

0 P R B P L A P L B

1 P L C P R B P R HALT

To the right: the above TABLE as

expressed as a "state transition"
diagram.
Usually large TABLES are better left
as tables (Booth, p. 74). They are more
readily simulated by computer in
tabular form (Booth, p. 74). However,
certain concepts—e.g. machines with
"reset" states and machines with
The "3-state busy beaver" Turing machine in a finite state representation. Each circle
repeating patterns (cf Hill and Peterson
represents a "state" of the TABLE—an "m-configuration" or "instruction". "Direction" of
p. 244ff)—can be more readily seen a state transition is shown by an arrow. The label (e.g.. 0/P,R) near the outgoing state (at
when viewed as a drawing. the "tail" of the arrow) specifies the scanned symbol that causes a particular transition
(e.g. 0) followed by a slash /, followed by the subsequent "behaviors" of the machine, e.g.
Whether a drawing represents an "P Print" then move tape "R Right". No general accepted format exists. The convention
improvement on its TABLE must be shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).
decided by the reader for the particular
context. See Finite state machine for more.
The reader should again be cautioned
that such diagrams represent a
snapshot of their TABLE frozen in
time, not the course ("trajectory") of a
computation through time and/or
space. While every time the busy
beaver machine "runs" it will always
follow the same state-trajectory, this is
not true for the "copy" machine that
can be provided with variable input
"parameters".

The diagram "Progress of the

computation" shows the 3-state busy The evolution of the busy-beaver's computation starts at the top and proceeds to the
bottom.
beaver's "state" (instruction) progress
through its computation from start to
finish. On the far right is the Turing "complete configuration" (Kleene "situation", Hopcroft–Ullman "instantaneous
description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire
tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf Turing (1936)
Undecidable pp. 139–140).
Turing machine 41

Models equivalent to the Turing machine model

Many machines that might be thought to have more computational capability than a simple universal Turing machine
can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky (1967)). They might compute faster,
perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e.
more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of
machine: that anything that can be "computed" can be computed by some Turing machine.)
A Turing machine is equivalent to a pushdown automaton that has been made more flexible and concise by relaxing
the last-in-first-out requirement of its stack.
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational
power as the Turing machine model.
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input
and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine
(DTM) for which the action table has at most one entry for each combination of symbol and state.
Read-only, right-moving Turing machines are equivalent to NDFAs (as well as DFAs by conversion using the
NDFA to DFA conversion algorithm).
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming
language.

Choice c-machines, Oracle o-machines

Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely
determined by the configuration" and a "choice machine":
...whose motion is only partially determined by the configuration ... When such a machine reaches one of these
ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator.
This would be the case if we were using machines to deal with axiomatic systems.
—Undecidable, p. 118
Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find
all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices
are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i1, i2, ...,
in (i1 = 0 or 1, i2 = 0 or 1, ..., in = 0 or 1), and hence the number 2n + i12n-1 + i22n-2 + ... +in completely determines the
proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, Undecidable,
p. 138)
This is indeed the technique by which a deterministic (i.e. a-) Turing machine can be used to mimic the action of a
nondeterministic Turing machine; Turing solved the matter in a footnote and appears to dismiss it from further
consideration.
An oracle machine or o-machine is a Turing a-machine that pauses its computation at state "o" while, to complete its
calculation, it "awaits the decision" of "the oracle"—an unspecified entity "apart from saying that it cannot be a
machine" (Turing (1939), Undecidable p. 166–168). The concept is now actively used by mathematicians.
Turing machine 42

Universal Turing machines

As Turing wrote in Undecidable, p. 128 (italics added):
It is possible to invent a single machine which can be used
to compute any computable sequence. If this machine U is
supplied with the tape on the beginning of which is written
the string of quintuples separated by semicolons of some
computing machine M, then U will compute the same
sequence as M.

This finding is now taken for granted, but at the time (1936) it was
considered astonishing. The model of computation that Turing called Model of a Turing machine
his "universal machine"—"U" for short—is considered by some (cf
Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the stored-program
computer.
Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming
techniques that accompanied it.
—Minsky (1967), p. 104
In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic
factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and R. E. Stearns.
(Arora and Barak, 2009, theorem 1.9)

Comparison with real machines

It is often said that Turing machines, unlike simpler automata, are as
powerful as real machines, and are able to execute any operation that a
real program can. What is neglected in this statement is that, because a
real machine can only have a finite number of configurations, this "real
machine" is really nothing but a linear bounded automaton. On the
other hand, Turing machines are equivalent to machines that have an
unlimited amount of storage space for their computations. As a matter
of fact, Turing machines are not intended to model computers, but
rather they are intended to model computation itself. Historically, A Turing machine realisation in LEGO

computers, which compute only on their (fixed) internal storage, were

developed only later.

There are a number of ways to explain why Turing machines are useful models of real computers:
1. Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine
can simulate any type of subroutine found in programming languages, including recursive procedures and any of
the known parameter-passing mechanisms" (Hopcroft and Ullman p. 157). A large enough FSA can also model
any real computer, disregarding IO. Thus, a statement about the limitations of Turing machines will also apply to
real computers.
2. The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data.
However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite
amount of data.
3. Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or
other storage media. If the supply of these runs short, the Turing machine may become less useful as a model. But
the fact is that neither Turing machines nor real machines need astronomical amounts of storage space in order to
Turing machine 43

perform useful computation. The processing time required is usually much more of a problem.
4. Descriptions of real machine programs using simpler abstract models are often much more complex than
descriptions using Turing machines. For example, a Turing machine describing an algorithm may have a few
hundred states, while the equivalent deterministic finite automaton (DFA) on a given real machine has
quadrillions. This makes the DFA representation infeasible to analyze.
5. Turing machines describe algorithms independent of how much memory they use. There is a limit to the memory
possessed by any current machine, but this limit can rise arbitrarily in time. Turing machines allow us to make
statements about algorithms which will (theoretically) hold forever, regardless of advances in conventional
computing machine architecture.
6. Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract
machines are usually more general than their counterparts running on real machines, because they have
arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not
limited to, running out of memory).
One way in which Turing machines are a poor model for programs is that many real programs, such as operating
systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing
machines do not model such ongoing computation well (but can still model portions of it, such as individual
procedures).

Limitations of Turing machines

Computational complexity theory

A limitation of Turing machines is that they do not model the strengths of a particular arrangement well. For
instance, modern stored-program computers are actually instances of a more specific form of abstract machine
known as the random access stored program machine or RASP machine model. Like the Universal Turing machine
the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the universal
Turing machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory
"cells" that can contain any integer (cf. Elgot and Robinson (1964), Hartmanis (1971), and in particular
Cook-Rechow (1973); references at random access machine). The RASP's finite-state machine is equipped with the
capability for indirect addressing (e.g. the contents of one register can be used as an address to specify another
register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction
is that there are computational optimizations that can be performed based on the memory indices, which are not
possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a
'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a
Turing machine). An example of this is binary search, an algorithm that can be shown to perform more quickly when
using the RASP model of computation rather than the Turing machine model.

Concurrency
Another limitation of Turing machines is that they do not model concurrency well. For example, there is a bound on
the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank
tape. (See article on unbounded nondeterminism.) By contrast, there are always-halting concurrent systems with no
inputs that can compute an integer of unbounded size. (A process can be created with local storage that is initialized
with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it
increments its count by 1 and sends itself a go message. When it receives a stop message, it stops with an unbounded
number in its local storage.)
Turing machine 44

History
They were described in 1936 by Alan Turing.

Historical background: computational machinery

Robin Gandy (1919–1995)—a student of Alan Turing (1912–1954) and his lifelong friend—traces the lineage of the
notion of "calculating machine" back to Babbage (circa 1834) and actually proposes "Babbage's Thesis":
That the whole of development and operations of analysis are now capable of being executed by machinery.
—(italics in Babbage as cited by Gandy, p. 54)
Gandy's analysis of Babbage's Analytical Engine describes the following five operations (cf p. 52–53):
1. The arithmetic functions +, −, × where − indicates "proper" subtraction x − y = 0 if y ≥ x
2. Any sequence of operations is an operation
3. Iteration of an operation (repeating n times an operation P)
4. Conditional iteration (repeating n times an operation P conditional on the "success" of test T)
5. Conditional transfer (i.e. conditional "goto").
Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing
computable." (p. 53). He cites other proposals for "universal calculating machines" included those of Percy Ludgate
(1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush
(1936), Howard Aiken (1937). However:
... the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental
importance of conditional iteration and conditional transfer for a general theory of calculating machines is not
recognized ...
—Gandy p. 55

The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900

With regards to Hilbert's problems posed by the famous mathematician David Hilbert in 1900, an aspect of problem
#10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for #10
is as follows:
10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any
number of unknown quantities and with rational integral coefficients: To devise a process according to which
it can be determined in a finite number of operations whether the equation is solvable in rational integers.
The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that
allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The
Entscheidungsproblem must be considered the main problem of mathematical logic.
—quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008
By 1922, this notion of "Entscheidungsproblem" had developed a bit, and H. Behmann stated that
... most general form of the Entscheidungsproblem [is] as follows:
A quite definite generally applicable prescription is required which will allow one to decide in a finite
number of steps the truth or falsity of a given purely logical assertion ...
—Gandy p. 57, quoting Behmann
Behmann remarks that ... the general problem is equivalent to the problem of deciding which mathematical
propositions are true.
—ibid.
Turing machine 45

If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or
even all) mathematical problems".
—ibid., p. 92
By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was
mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics decidable?" (Hodges
p. 91, Hawking p. 1121). The first two questions were answered in 1930 by Kurt Gödel at the very same meeting
where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the
Entscheidungsproblem—had to wait until the mid-1930s.
The problem was that an answer first required a precise definition of "definite general applicable prescription",
which Princeton professor Alonzo Church would come to call "effective calculability", and in 1928 no such
definition existed. But over the next 6–7 years Emil Post developed his definition of a worker moving from room to
room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students Stephen
Kleene and J. B. Rosser by use of Church's lambda-calculus and Gödel's recursion theory (1934). Church's paper
(published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the
punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil
Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed
Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that
Church's lambda-calculus and his machines would compute the same functions.
But what Church had done was something rather different, and in a certain sense weaker. ... the Turing
construction was more direct, and provided an argument from first principles, closing the gap in Church's
demonstration.
—Hodges p. 112
And Post had only proposed a definition of calculability and criticized Church's "definition", but had proved nothing.

Alan Turing's a- (automatic-)machine

In the spring of 1935, Turing as a young Master's student at King's College Cambridge, UK, took on the challenge;
he had been stimulated by the lectures of the logician M. H. A. Newman "and learned from them of Gödel's work
and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman
writes:
To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that
can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a
computing machine.
—Gandy, p. 74
Gandy states that:
I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the
undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he
was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis
of computation or his realization that there was a universal machine, and so a diagonal argument to prove
unsolvability.
—ibid., p. 76
While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a
lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a
typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'"
(Hodges p. 96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD
thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":
Turing machine 46

It was stated above that 'a function is effectively calculable if its values can be found by some purely
mechanical process'. We may take this statement literally, understanding by a purely mechanical process one
which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal
form, of the structures of these machines. The development of these ideas leads to the author's definition of a
computable function, and to an identification of computability with effective calculability. It is not difficult,
though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.
—Turing (1939) in The Undecidable, p. 160
When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes
created by encryption machines called "The Enigma"; he also became involved in the design of the ACE (Automatic
Computing Engine), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the EDVAC
[the USA's initiative], but in his own universal machine" (Hodges p. 318). Arguments still continue concerning the
origin and nature of what has been named by Kleene (1952) Turing's Thesis. But what Turing did prove with his
computational-machine model appears in his paper On Computable Numbers, With an Application to the
Entscheidungsproblem (1937):
[that] the Hilbert Entscheidungsproblem can have no solution ... I propose, therefore to show that there can be
no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that
there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is
provable.
—from Turing's paper as reprinted in The Undecidable, p. 145
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print
0", the question is "undecidable".

1937–1970: The "digital computer", the birth of "computer science"

In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch,
making his own electromechanical relays (Hodges p. 138). "Alan's task was to embody the logical design of a Turing
machine in a network of relay-operated switches ..." (Hodges p. 138). While Turing might have been just initially
curious and experimenting, quite-earnest work in the same direction was going in Germany (Konrad Zuse (1938)),
and in the United States (Howard Aiken) and George Stibitz (1937); the fruits of their labors were used by the Axis
and Allied military in World War II (cf Hodges p. 298–299). In the early to mid-1950s Hao Wang and Marvin
Minsky reduced the Turing machine to a simpler form (a precursor to the Post-Turing machine of Martin Davis);
simultaneously European researchers were reducing the new-fangled electronic computer to a computer-like
theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s,
the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and
Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like
abstract model called the counter machine; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow
(1973) carried this work even further with the register machine and random access machine models—but basically
all are just multi-tape Turing machines with an arithmetic-like instruction set.
Turing machine 47

1970–present: the Turing machine as a model of computation

Today, the counter, register and random-access machines and their sire the Turing machine continue to be the
models of choice for theorists investigating questions in the theory of computation. In particular, computational
complexity theory makes use of the Turing machine:
Depending on the objects one likes to manipulate in the computations (numbers like nonnegative
integers or alphanumeric strings), two models have obtained a dominant position in machine-based
complexity theory:
the off-line multitape Turing machine..., which represents the standard model for string-oriented
computation, and
the random access machine (RAM) as introduced by Cook and Reckhow ..., which models the idealized
Von Neumann style computer.
—van Emde Boas 1990:4
Only in the related area of analysis of algorithms this role is taken over by the RAM model.
—van Emde Boas 1990:16

Notes
[1] http:/ / en. wikipedia. org/ w/ index. php?title=Template:Turing& action=edit
[2] The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures:
"Was there a definite method, or as Newman put it, a mechanical process which could be applied to a mathematical statement, and which
would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London
Mathematical Society for its Proceedings (cf Hodges 1983:112), but it was published in early 1937 and offprints were available in February
1937 (cf Hodges 1983:129).
[3] See the definition of "innings" on Wiktionary

References

Primary literature, reprints, and compilations

• B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial
Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford
UK, ISBN 0-19-825079-7. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's
convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine
• Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY.
• Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936.
Reprinted in The Undecidable pp. 289ff.
• Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12, pp. 1–11.
Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to
Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing
machine coding and footnote 14 with comments on Turing's first and second proofs.
• Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungs problem".
Proceedings of the London Mathematical Society. 2 (1937) 42: 230–265. doi: 10.1112/plms/s2-42.1.230 (http://
[Link]/10.1112/plms/s2-42.1.230). (and Turing, A.M. (1938). "On Computable Numbers, with an
Application to the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. 2
(1937) 43 (6): 544–6. doi: 10.1112/plms/s2-43.6.544 ([Link]
Reprinted in many collections, e.g. in The Undecidable pp. 115–154; available on the web in many places, e.g. at
Scribd ([Link]
Turing machine 48

• Alan Turing, 1948, "Intelligent Machinery." Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J.
Robertson. Baltimore: University Park Press, 1968. p. 31.
• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, 13(4):533–546, 1966.

Computability theory
• Boolos, George; Richard Jeffrey (1989, 1999). Computability and Logic (3rd ed.). Cambridge UK: Cambridge
University Press. ISBN 0-521-20402-X.
• Boolos, George; John Burgess, Richard Jeffrey, (2002). Computability and Logic (4th ed.). Cambridge UK:
Cambridge University Press. ISBN 0-521-00758-5 (pb.) Check |isbn= value (help). Some parts have been
significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf
Register machine) and recursive functions, showing their equivalence.
• Taylor L. Booth (1967), Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York.
Graduate level engineering text; ranges over a wide variety of topics, Chapter IX Turing Machines includes some
recursion theory.
• Martin Davis (1958). Computability and Unsolvability. McGraw-Hill Book Company, Inc, New York.. On pages
12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper
Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
• Davis, Martin; Ron Sigal, Elaine J. Weyuker (1994). Computability, Complexity, and Languages and Logic:
Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace &
Company. ISBN 0-12-206382-1.
• Hennie, Fredrick (1977). Introduction to Computability. Addison–Wesley, Reading, Mass. Unknown parameter
|unused_data= ignored (help). On pages 90–103 Hennie discusses the UTM with examples and flow-charts,
but no actual 'code'.
• John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation (1st
ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X. Check |isbn= value (help). A difficult book.
Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.
• Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and
Computation (2nd ed.). Reading Mass: Addison–Wesley. ISBN 0-201-44124-1. Distinctly different and less
intimidating than the first edition.
• Stephen Kleene (1952), Introduction to Metamathematics, North–Holland Publishing Company, Amsterdam
Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII
Computable functions is on Turing machine proofs of computability of recursive functions, etc.
• Knuth, Donald E. (1973). Volume 1/Fundamental Algorithms: The Art of computer Programming (2nd ed.).
Reading, Mass.: Addison–Wesley Publishing Company.. With reference to the role of Turing machines in the
development of computation (both hardware and software) see 1.4.5 History and Bibliography pp. 225ff and 2.6
History and Bibliographypp. 456ff.
• Zohar Manna, 1974, Mathematical Theory of Computation. Reprinted, Dover, 2003. ISBN 978-0-486-43238-0
• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8,
Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1.
Chapter 2: Turing machines, pp. 19–56.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.
Chapter 3: The Church–Turing Thesis, pp. 125–149.
• Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1st ed.). New York:
McGraw–Hill Book Company. ISBN 0-07-061726-0.
• Peter van Emde Boas 1990, Machine Models and Simulations, pp. 3–66, in Jan van Leeuwen, ed., Handbook of
Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, [place?], ISBN
Turing machine 49

0-444-88071-2 (Volume A). QA76.H279 1990. Valuable survey, with 141 references.

Church's thesis
• Nachum Dershowitz; Yuri Gurevich (September 2008). "A natural axiomatization of computability and proof of
Church's Thesis" ([Link] Bulletin of
Symbolic Logic 14 (3). Retrieved 2008-10-15.
• Roger Penrose (1989, 1990). The Emperor's New Mind (2nd ed.). Oxford University Press, New York.
ISBN 0-19-851973-7.

Small Turing machines

• Rogozhin, Yurii, 1998, " A Universal Turing Machine with 22 States and 2 Symbols ([Link]
web/20050308141040/[Link] Romanian Journal Of
Information Science and Technology, 1(3), 259–265, 1998. (surveys known results about small universal Turing
machines)
• Stephen Wolfram, 2002, A New Kind of Science ([Link]
Wolfram Media, ISBN 1-57955-008-8
• Brunfiel, Geoff, Student snags maths prize ([Link]
[Link]), Nature, October 24. 2007.
• Jim Giles (2007), Simplest 'universal computer' wins student $25,000 ([Link]
article/[Link]), New Scientist, October 24, 2007.
• Alex Smith, Universality of Wolfram’s 2, 3 Turing Machine ([Link]
[Link]), Submission for the Wolfram 2, 3 Turing Machine Research Prize.
• Vaughan Pratt, 2007, " Simple Turing machines, Universality, Encodings, etc. ([Link]
fom/2007-October/[Link])", FOM email list. October 29, 2007.
• Martin Davis, 2007, " Smallest universal machine ([Link]
html)", and Definition of universal Turing machine ([Link]
html) FOM email list. October 26–27, 2007.
• Alasdair Urquhart, 2007 " Smallest universal machine ([Link]
[Link])", FOM email list. October 26, 2007.
• Hector Zenil (Wolfram Research), 2007 " smallest universal machine ([Link]
2007-October/[Link])", FOM email list. October 29, 2007.
• Todd Rowland, 2007, " Confusion on FOM ([Link]
threadid=1472)", Wolfram Science message board, October 30, 2007.

Other
• Martin Davis (2000). Engines of Logic: Mathematicians and the origin of the Computer (1st ed.). W. W. Norton
& Company, New York. ISBN 0-393-32229-7 pbk. Check |isbn= value (help).
• Robin Gandy, "The Confluence of Ideas in 1936", pp. 51–102 in Rolf Herken, see below.
• Stephen Hawking (editor), 2005, God Created the Integers: The Mathematical Breakthroughs that Changed
History, Running Press, Philadelphia, ISBN 978-0-7624-1922-7. Includes Turing's 1936–1937 paper, with brief
commentary and biography of Turing as written by Hawking.
• Rolf Herken (1995). The Universal Turing Machine—A Half-Century Survey. Springer Verlag.
ISBN 3-211-82637-8.
• Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for
a history leading to, and a discussion of, his proof.
Turing machine 50

• Ivars Peterson (1988). The Mathematical Tourist: Snapshots of Modern Mathematics (1st ed.). W. H. Freeman
and Company, New York. ISBN 0-7167-2064-7 (pbk.) Check |isbn= value (help).
• Paul Strathern (1997). Turing and the Computer—The Big Idea. Anchor Books/Doubleday.
ISBN 0-385-49243-X.
• Hao Wang, "A variant to Turing's theory of computing machines", Journal of the Association for Computing
Machinery (JACM) 4, 63–92 (1957).
• Charles Petzold, Petzold, Charles, The Annotated Turing ([Link] John Wiley &
Sons, Inc., ISBN 0-470-22905-5
• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach" ([Link]
theory/complexity/), Cambridge University Press, 2009, ISBN 978-0-521-42426-4, section 1.4, "Machines as
strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
• A Note On Turing Machine Computability Of Rule Driven Systems, SIGACT News December 2005

External links
• Hazewinkel, Michiel, ed. (2001), "Turing machine" ([Link]
t094460), Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Turing Machine on Stanford Encyclopedia of Philosophy ([Link]
• Detailed info on the Church–Turing Hypothesis ([Link] (Stanford
Encyclopedia of Philosophy)
• Turing Machine-Like Models ([Link]
html) in Molecular Biology, to understand life mechanisms with a DNA-tape processor.
• The Turing machine ([Link]
php)—Summary about the Turing machine, its functionality and historical facts
• The Wolfram 2,3 Turing Machine Research Prize ([Link]
Wolfram's $25,000 prize for the proof or disproof of the universality of the potentially smallest universal Turing
Machine. The contest has ended, with the proof affirming the machine's universality.
• " Turing Machine Causal Networks ([Link]
by Enrique Zeleny, Wolfram Demonstrations Project.
• Turing Machines ([Link]
Turing_Machines/) on the Open Directory Project
• Purely mechanical Turing Machine ([Link]
ChurchTuring thesis 51

Church–Turing thesis
In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the
Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined
hypothesis ("thesis") about the nature of functions whose values are effectively calculable; or, in more modern terms,
functions whose values are algorithmically computable. In simple terms, the Church–Turing thesis states that a
function is algorithmically computable if and only if it is computable by a Turing machine.
Several independent attempts were made in the first half of the 20th century to formalize the notion of computability:
• American mathematician Alonzo Church created a method for defining functions called the λ-calculus,
• British mathematician Alan Turing created a theoretical model for machines, now called Turing machines, that
could carry out calculations from inputs,
• Kurt Gödel, with Jacques Herbrand, created a formal definition of a class of functions whose values could be
calculated by recursion.
All three computational processes (recursion, the λ-calculus, and the Turing machine) were shown to be
equivalent—all three approaches define the same class of functions.[1][2] This has led mathematicians and computer
scientists to believe that the concept of computability is accurately characterized by these three equivalent processes.
Informally, the Church–Turing thesis states that if some method (algorithm) exists to carry out a calculation, then the
same calculation can also be carried out by a Turing machine (as well as by a recursively definable function, and by
a λ-function).
Even though the three processes mentioned above proved to be equivalent, the fundamental premise behind the
thesis — the notion of what it means for a function to be effectively calculable — is "a somewhat vague intuitive
one".[3] Thus, the thesis, although it has near-universal acceptance, cannot be formally proven.

Formal statement
J.B. Rosser 1939 addresses the notion of "effective computability" as follows: "Clearly the existence of CC and RC
(Church's and Rosser's proofs) presupposes a precise definition of 'effective'. 'Effective method' is here used in the
rather special sense of a method each step of which is precisely predetermined and which is certain to produce the
answer in a finite number of steps".[4] Thus the adverb-adjective "effective" is used in a sense of "1a: producing a
decided, decisive, or desired effect", and "capable of producing a result".[5]
In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means
whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical
device". Turing's "definitions" given in a footnote in his 1939 Ph.D. thesis Systems of Logic Based on Ordinals,
supervised by Church, are virtually the same:
"† We shall use the expression 'computable function' to mean a function calculable by a machine, and let
'effectively calculable' refer to the intuitive idea without particular identification with any one of these
definitions."[6]
The thesis can be stated as follows:
Every effectively calculable function is a computable function.[7]
Turing stated it this way:
"It was stated ... that 'a function is effectively calculable if its values can be found by some purely mechanical
process.' We may take this literally, understanding that by a purely mechanical process one which could be
carried out by a machine. The development ... leads to ... an identification of computability† with effective
calculability." († is the footnote above, ibid.)
ChurchTuring thesis 52

History
One of the important problems for logicians in the 1930s was David Hilbert's Entscheidungsproblem, which asked
whether there was a mechanical procedure for separating mathematical truths from mathematical falsehoods. This
quest required that the notion of "algorithm" or "effective calculability" be pinned down, at least well enough for the
quest to begin.[8] But from the very outset Alonzo Church's attempts began with a debate that continues to this day.[9]
Was the notion of "effective calculability" to be (i) an "axiom or axioms" in an axiomatic system, or (ii) merely a
definition that "identified" two or more propositions, or (iii) an empirical hypothesis to be verified by observation of
natural events, or (iv) or just a proposal for the sake of argument (i.e. a "thesis").

Circa 1930–1952
In the course of studying the problem, Church and his student Stephen Kleene introduced the notion of λ-definable
functions, and they were able to prove that several large classes of functions frequently encountered in number
theory were λ-definable.[10] The debate began when Church proposed to Gödel that one should define the
"effectively computable" functions as the λ-definable functions. Gödel, however, was not convinced and called the
proposal "thoroughly unsatisfactory".[11] Rather, in correspondence with Church (ca 1934–5), Gödel proposed
axiomatizing the notion of "effective calculability"; indeed, in a 1935 letter to Kleene, Church reported that:
"His [Gödel's] only idea at the time was that it might be possible, in terms of effective calculability as an
undefined notion, to state a set of axioms which would embody the generally accepted properties of this
notion, and to do something on that basis".
But Gödel offered no further guidance. Eventually, he would suggest his (primitive) recursion, modified by
Herbrand's suggestion, that Gödel had detailed in his 1934 lectures in Princeton NJ (Kleene and another student
Rosser transcribed the notes). But "he did not think that the two ideas could be satisfactorily identified "except
heuristically".[12]
Next, it was necessary to identify and prove the equivalence of two notions of effective calculability. Equipped with
the λ-calculus and "general" recursion, Stephen Kleene with help of Church and J. B. Rosser produced proofs (1933,
1935) to show that the two calculi are equivalent. Church subsequently modified his methods to include use of
Herbrand–Gödel recursion and then proved (1936) that the Entscheidungsproblem is unsolvable: There is no
generalized "effective calculation" (method, algorithm) that can determine whether or not a formula in either the
recursive- or λ-calculus is "valid" (more precisely: no method to show that a well formed formula has a "normal
form").[13]
Many years later in a letter to Davis (ca 1965), Gödel would confess that "he was, at the time of these [1934]
lectures, not at all convinced that his concept of recursion comprised all possible recursions".[14] By 1963–4 Gödel
would disavow Herbrand–Gödel recursion and the λ-calculus in favor of the Turing machine as the definition of
"algorithm" or "mechanical procedure" or "formal system".[15]
A hypothesis leading to a natural law?: In late 1936 Alan Turing's paper (also proving that the
Entscheidungsproblem is unsolvable) was delivered orally, but had not yet appeared in print. On the other hand,
Emil Post's 1936 paper had appeared and was certified independent of Turing's work.[16] Post strongly disagreed
with Church's "identification" of effective computability with the λ-calculus and recursion, stating:
"Actually the work already done by Church and others carries this identification considerably beyond the
working hypothesis stage. But to mask this identification under a definition . . . blinds us to the need of its
continual verification."[17]
Rather, he regarded the notion of "effective calculability" as merely a "working hypothesis" that might lead by
inductive reasoning to a "natural law" rather than by "a definition or an axiom".[18] This idea was "sharply" criticized
by Church.[19]
ChurchTuring thesis 53

Thus Post in his 1936[] paper was also discounting Kurt Gödel's suggestion to Church in 1934–5 that the thesis might
be expressed as an axiom or set of axioms.
Turing adds another definition, Rosser equates all three: Within just a short time, Turing's 1936–37 paper "On
Computable Numbers, with an Application to the Entscheidungsproblem" appeared. In it he stated another notion of
"effective computability" with the introduction of his a-machines (now known as the Turing machine abstract
computational model). And in a proof-sketch added as an "Appendix" to his 1936–37 paper, Turing showed that the
classes of functions defined by λ-calculus and Turing machines coincided.[20]
In a few years (1939) Turing would propose, like Church and Kleene before him, that his formal definition of
mechanical computing agent was the correct one.[21] Thus, by 1939, both Church (1934) and Turing (1939), neither
having knowledge of the other's efforts, had individually proposed that their "formal systems" should be definitions
of "effective calculability";[22] neither framed their statements as theses.
Rosser (1939) formally identified the three notions-as-definitions:
"All three definitions are equivalent, so it does not matter which one is used."[23]
Kleene proposes Church's Thesis: This left the overt expression of a "thesis" to Kleene. In his 1943 paper
Recursive Predicates and Quantifiers Kleene proposed his "THESIS I":
"This heuristic fact [general recursive functions are effectively calculable]...led Church to state the following
thesis(22). The same thesis is implicit in Turing's description of computing machines(23).
"THESIS I. Every effectively calculable function (effectively decidable predicate) is general[24]
recursive [Kleene's italics]
"Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been
wanting, we can take this thesis ... as a definition of it..."[25]
"(22) references Church 1936
"(23) references Turing 1936–7
Kleene goes on to note that:
"...the thesis has the character of an hypothesis—a point emphasized by Post and by Church(24). If we consider
the thesis and its converse as definition, then the hypothesis is an hypothesis about the application of the
mathematical theory developed from the definition. For the acceptance of the hypothesis, there are, as we have
suggested, quite compelling grounds."
"(24) references Post 1936 of Post and Church's Formal definitions in the theory of ordinal
numbers, Fund. Math. vol 28 (1936) pp.11–21 (see ref. #2, Davis 1965:286).
Kleene's Church–Turing Thesis: A few years later (1952) Kleene would overtly name, defend, and express the two
"theses" and then "identify" them (show equivalence) by use of his Theorem XXX:
"Heuristic evidence and other considerations led Church 1936 to propose the following thesis.
Thesis I. Every effectively calculable function (effectively decidable predicate) is general recursive.[26]
Theorem XXX: "The following classes of partial functions are coextensive, i.e. have the same members: (a)
the partial recursive functions, (b) the computable functions. . . ".[27]
Turing's thesis: "Turing's thesis that every function which would naturally be regarded as computable is
computable under his definition, i.e. by one of his machines, is equivalent to Church's thesis by Theorem
XXX."[28]
ChurchTuring thesis 54

Later developments
An attempt to understand the notion of "effective computability" better led Robin Gandy (Turing's student and
friend) in 1980 to analyze machine computation (as opposed to human-computation acted out by a Turing machine).
Gandy's curiosity about, and analysis of, "cellular automata", "Conway's game of life", "parallelism" and "crystalline
automata" led him to propose four "principles (or constraints) ... which it is argued, any machine must satisfy."[29]
His most-important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and
signals; contemporary physics rejects the possibility of instantaneous action at a distance."[30] From these principles
and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper
bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic
behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is
computable.[31] ".
In the late 1990s Wilfried Sieg analyzed Turing's and Gandy's notions of "effective calculability" with the intent of
"sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic
framework".[32] In his 1997 and 2002 Sieg presents a series of constraints on the behavior of a computor—"a human
computing agent who proceeds mechanically"; these constraints reduce to:
• "(B.1) (Boundedness) There is a fixed bound on the number of symbolic configurations a computor can
immediately recognize.
• "(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in.
• "(L.1) (Locality) A computor can change only elements of an observed symbolic configuration.
• "(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new
observed configurations must be within a bounded distance of the immediately previously observed configuration.
• "(D) (Determinacy) The immediately recognizable (sub-)configuration determines uniquely the next computation
step (and id [instantaneous description] )"; stated another way: "A computor's internal state together with the
observed configuration fixes uniquely the next computation step and the next internal state."[33]
The matter remains in active discussion within the academic community.[34]

The thesis as a definition

The thesis can be viewed as nothing but an ordinary mathematical definition. Comments by Gödel on the subject
suggest this view, e.g. "the correct definition of mechanical computability was established beyond any doubt by
Turing".[35] The case for viewing the thesis as nothing more than a definition is made explicitly by Robert I. Soare in
[36]
where it is also argued that Turing's definition of computability is no less likely to be correct than the
epsilon-delta definition of a continuous function.

Success of the thesis

Other formalisms (besides recursion, the λ-calculus, and the Turing machine) have been proposed for describing
effective calculability/computability. Stephen Kleene (1952) adds to the list the functions "reckonable in the system
S1" of Kurt Gödel 1936, and Emil Post's (1943, 1946) "canonical [also called normal] systems".[37] In the 1950s Hao
Wang and Martin Davis greatly simplified the one-tape Turing-machine model (see Post–Turing machine). Marvin
Minsky expanded the model to two or more tapes and greatly simplified the tapes into "up-down counters", which
Melzak and Lambek further evolved into what is now known as the counter machine model. In the late 1960s and
early 1970s researchers expanded the counter machine model into the register machine, a close cousin to the modern
notion of the computer. Other models include combinatory logic and Markov algorithms. Gurevich adds the pointer
machine model of Kolmogorov and Uspensky (1953, 1958): "...they just wanted to ... convince themselves that there
is no way to extend the notion of computable function."[38]
ChurchTuring thesis 55

All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such
models are said to be Turing complete. Because all these different attempts at formalizing the concept of "effective
calculability/computability" have yielded equivalent results, it is now generally assumed that the Church–Turing
thesis is correct. In fact, Gödel (1936) proposed something stronger than this; he observed that there was something
"absolute" about the concept of "reckonable in S1":
"It may also be shown that a function which is computable ['reckonable'] in one of the systems Si, or even in a
system of transfinite type, is already computable [reckonable] in S1. Thus the concept 'computable'
['reckonable'] is in a certain definite sense 'absolute', while practically all other familiar metamathematical
concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined"[39]

Informal usage in proofs

Proofs in computability theory often invoke[40] the Church–Turing thesis in an informal way to establish the
computability of functions while avoiding the (often very long) details which would be involved in a rigorous,
formal proof. To establish that a function is computable by Turing machine, it is usually considered sufficient to give
an informal English description of how the function can be effectively computed, and then conclude "By the
Church–Turing thesis" that the function is Turing computable (equivalently partial recursive).
Dirk van Dalen (in Gabbay 2001:284[41]) gives the following example for the sake of illustrating this informal use of
the Church–Turing thesis:
EXAMPLE: Each infinite RE set contains an infinite recursive set.
Proof: Let A be infinite RE. We list the elements of A effectively, n0, n1, n2, n3, ...
From this list we extract an increasing sublist: put m0=n0, after finitely many steps we find an nk such that nk >
m0, put m1=nk. We repeat this procedure to find m2 > m1, etc. this yields an effective listing of the subset
B={m0,m1,m2,...} of A, with the property mi < mi+1.
Claim. B is decidable. For, in order to test k in B we must check if k=mi for some i. Since the sequence of mi's
is increasing we have to produce at most k+1 elements of the list and compare them with k. If none of them is
equal to k, then k not in B. Since this test is effective, B is decidable and, by Church's thesis, recursive.
(Emphasis added). In order to make the above example completely rigorous, one would have to carefully construct a
Turing Machine, or λ-function, or carefully invoke recursion axioms, or at best, cleverly invoke various theorems of
computability theory. But because the computability theorist believes that Turing computability correctly captures
what can be computed effectively, and because an effective procedure is spelled out in English for deciding the set
B, the computability theorist accepts this as proof that the set is indeed recursive.
As a rule of thumb, the Church–Turing thesis should only be invoked to simplify proofs in cases where the writer
would be capable of, and expects the readers also to be capable of, easily (but not necessarily without tedium)
producing a rigorous proof if one were demanded.

Variations
The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the Physical
Church–Turing thesis (PCTT) states:
"According to Physical CTT, all physically computable functions are Turing-computable"[42]
The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate
another. It has been proved for instance that a (multi-tape) universal Turing machine only suffers a logarithmic
slowdown factor in simulating any Turing machine.[43] No such result has been proved in general for an arbitrary but
reasonable model of computation. A variation of the Church–Turing thesis that addresses this issue is the Feasibility
Thesis[44] or (Classical) Complexity-Theoretic Church–Turing Thesis (SCTT), which is not due to Church or
ChurchTuring thesis 56

Turing, but rather was realized gradually in the development of complexity theory. It states:[45]
"A probabilistic Turing machine can efficiently simulate any realistic model of computation."
The word 'efficiently' here means up to polynomial-time reductions. This thesis was originally called Computational
Complexity-Theoretic Church–Turing Thesis by Ethan Bernstein and Umesh Vazirani (1997). The
Complexity-Theoretic Church–Turing Thesis, then, posits that all 'reasonable' models of computation yield the same
class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial
time (BPP) equals deterministic polynomial time (P), the word 'probabilistic' is optional in the Complexity-Theoretic
Church–Turing Thesis. A similar thesis, called the Invariant Thesis, was introduced by Cees F. Slot and Peter van
Emde Boas. It states: "Reasonable" machines can simulate each other within a polynomially bounded overhead in
time and a constant-factor overhead in space.[46] The thesis originally appeared in a paper at STOC'84, which was
the first paper to show that polynomial-time overhead and constant-space overhead could be simultaneously
achieved for a simulation of a Random Access Machine on a Turing machine.[47]
If BQP is shown to be a strict superset of BPP, it would invalidate the Complexity-Theoretic Church–Turing Thesis.
In other words, there would be efficient quantum algorithms that perform tasks that do not have efficient
probabilistic algorithms. This would not however invalidate the original Church–Turing thesis, since a quantum
computer can always be simulated by a Turing machine, but it would invalidate the classical Complexity-Theoretic
Church–Turing thesis for efficiency reasons. Consequently, the Quantum Complexity-Theoretic Church–Turing
thesis states:
"A quantum Turing machine can efficiently simulate any realistic model of computation."
Eugene Eberbach and Peter Wegner[48] claim that the Church–Turing thesis is sometimes interpreted too broadly,
stating "the broader assertion that algorithms precisely capture what can be computed is invalid". They claim that
forms of computation not captured by the thesis are relevant today, terms which they call super-Turing computation.

Philosophical implications
Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind; however,
many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement.[49]
B. Jack Copeland states that it's an open empirical question whether there are actual deterministic physical processes
that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical
question whether any such processes are involved in the working of the human brain.[50] There are also some
important open questions which cover the relationship between the Church–Turing thesis and physics, and the
possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:
1. The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically
impossible. This has been termed the Strong Church–Turing thesis and is a foundation of digital physics.
2. The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but
incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a
universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
The assumption that incomputable physical events are not "harnessable" has been challenged, however,[51] by a
proposed computational process that uses quantum randomness together with a computational machine to hide the
computational steps of a Universal Turing Machine with Turing-incomputable firing patterns.
3. The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate
non-recursive functions. For example, it is an open question whether all quantum mechanical events are
Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to
deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and Roger
Penrose[52] have suggested that the human mind might be the result of some kind of quantum-mechanically
enhanced, "non-algorithmic" computation, although there is no scientific evidence for this proposal.
ChurchTuring thesis 57

There are many other technical possibilities which fall outside or between these three categories, but these serve to
illustrate the range of the concept.

Non-computable functions
One can formally define functions that are not computable. A well-known example of such a function is the Busy
Beaver function. This function takes an input n and returns the largest number of symbols that a Turing machine
with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is
equivalent to solving the halting problem, a problem known to be unsolvable by Turing machines. Since the busy
beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot
be effectively computed by any method.
Several computational models allow for the computation of (Church-Turing) non-computable functions. These are
known as hypercomputers. Mark Burgin[53] argues that super-recursive algorithms such as inductive Turing
machines disprove the Church–Turing thesis. His argument relies on a definition of algorithm broader than the
ordinary one, so that non-computable functions obtained from some inductive Turing machines are called
computable. This interpretation of the Church–Turing thesis differs from the interpretation commonly accepted in
computability theory, discussed above. The argument that super-recursive algorithms are indeed algorithms in the
sense of the Church–Turing thesis has not found broad acceptance within the computability research
community.[citation needed]

Footnotes
[1] Church 1934:90 footnote in Davis 1952
[2] Turing 1936–7 in Davis 1952:149
[3] Kleene 1952:317
[4] Rosser 1939 in Davis 1965:225
[5] Merriam Webster's Ninth New Collegiate Dictionary
[6] A. M. Turing (1939), Systems of Logic Based on Ordinals (https:/ / webspace. princeton. edu/ users/ jedwards/ Turing Centennial 2012/ Mudd
Archive files/ 12285_AC100_Turing_1938. pdf) (Ph.D. thesis). Princeton University. p. 8.
[7] Gandy (Gandy 1980 in Barwise 1980:123) states it this way: What is effectively calculable is computable. He calls this "Church's Thesis", a
peculiar choice of moniker.
[8] Davis's commentary before Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:88. Church uses the words
"effective calculability" on page 100ff.
[9] In his review of Church's Thesis after 70 Years edited by Adam Olszewski et al. 2006, Peter Smith's criticism of a paper by Muraswski and
Wolenski suggests 4 "lines" re the status of the Church–Turing Thesis: (1) empirical hypothesis (2) axiom or theorem, (3) definition, (4)
explication. But Smith opines that (4) is indistinguishable from (3), cf Smith (July 11, 2007) Church's Thesis after 70 Years at http:/ / www.
logicmatters. net/ resources/ pdfs/ CTT. pdf
[10] cf footnote 3 in Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:89
[11] Dawson 1997:99
[12] Sieg 1997:160 quoting from the 1935 letter written by Church to Kleene, cf Footnote 3 in Gödel 1934 in Davis 1965:44
[13] cf Church 1936 in Davis 1965:105ff
[14] Davis's commentary before Gödel 1934 in Davis 1965:40
[15] For a detailed discussion of Gödel's adoption of Turing's machines as models of computation, see Shagrir date TBD at http:/ / edelstein. huji.
ac. il/ staff/ shagrir/ papers/ Goedel_on_Turing_on_Computability. pdf
[16] cf. Editor's footnote to Post 1936 Finite Combinatory Process. Formulation I. at Davis 1965:289.
[17] Post 1936 in Davis 1965:291 footnote 8
[18] Post 1936 in Davis 1952:291
[19] Sieg 1997:171 and 176–7
[20] Turing 1936–7 in Davis 1965:263ff
[21] Turing 1939 in Davis:160
[22] cf. Church 1934 in Davis 1965:100, also Turing 1939 in Davis 1965:160
[23] italics added, Rosser 1939 in Davis 1965:226
[24] An archaic usage of Kleene et al. to distinguish Gödel's (1931) "rekursiv" (a few years later named primitive recursion by Rózsa Péter (cf
Gandy 1994 in Herken 1994–5:68)) from Herbrand–Gödel's recursion of 1934 i.e. primitive recursion equipped with the additional mu
operator; nowadays mu-recursion is called, simply, "recursion".
ChurchTuring thesis 58

[25] Kleene 1943 in Davis 1965:274

[26] Kleene 1952:300
[27] Kleene 1952:376
[28] Kleene 1952:376)
[29] Gandy 1980 in Barwise 1980:123ff)
[30] Gandy 1980 in Barwise 1980:135
[31] Gandy 1980 in Barwise:126
[32] (Sieg 1998–9 in Sieg–Somner–Talcott 2002:390ff; also Sieg 1997:154ff)
[33] In a footnote Sieg breaks Post's 1936 (B) into (B.1) and (B.2) and (L) into (L.1) and (L.2) and describes (D) differently. With respect to his
proposed Gandy machine he later adds LC.1, LC.2, GA.1 and GA.2. These are complicated; see Sieg 1998–9 in Sieg–Somner–Talcott
2002:390ff.
[34] A collection of papers can be found at Church's Thesis after 70 Years edited by Adam Olszewski et al. 2006. Also a review of this collection
by Peter Smith (July 11, 2007) Church's Thesis after 70 Years at http:/ / www. logicmatters. net/ resources/ pdfs/ CTT. pdf
[35] Gödel, K. [193?], “Undecidable Diophantine Propositions”, in Collected Works, III, p. 168.
[36] R. I. Soare, 1996, Computability and Recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321.
[37] Kleene 1952:320
[38] Gurevich 1988:2
[39] translation of Gödel (1936) by Davis in The Undecidable p. 83, differing in the use of the word 'reckonable' in the translation in Kleene
(1952) p. 321
[40] Horsten in Olszewski 2006:256
[41] Gabbay 2001:284
[42] Piccinini 2007:101 "Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy" (http:/ / www. umsl. edu/ ~piccininig/
Computationalism_Church-Turing_Thesis_Church-Turing_Fallacy. pdf). . in Synthese (2007) 154:97–120.
[43] Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach" (http:/ / www. cs. princeton. edu/ theory/ complexity/ ),
Cambridge University Press, 2009, ISBN 978-0-521-42426-4, section 1.4, "Machines as strings and the universal Turing machine" and 1.7,
"Proof of theorem 1.9"
[44] http:/ / www. claymath. org/ millennium/ P_vs_NP/ Official_Problem_Description. pdf
[45] Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN
0-19-857049-X, pp. 5–6
[46] Peter van Emde Boas's, Machine Models and Simulations, in Handbook of Theoretical Computer Science A, Elsevier, 1990, p. 5
[47] C. Slot, P. van Emde Boas, On tape versus core: an application of space efficient perfect hash functions to the invariance of space, STOC,
December 1984
[48] Eberbach and Wegner, 2003
[49] In particular, see the numerous examples (of errors, of misappropriation of the thesis) at the entry in the Stanford Encyclopedia of
Philosophy. For a good place to encounter original papers see David J. Chalmers, ed. 2002, Philosophy of Mind: Classical and Contemporary
Readings, Oxford University Press, New York.
[50] B. Jack Copeland, Computation in Luciano Floridi (ed.), The Blackwell guide to the philosophy of computing and information,
Wiley-Blackwell, 2004, ISBN 0-631-22919-1, p. 15
[51] Michael Fiske, "Turing Incomputable Computation" in Turing-100 proceedings, The Alan Turing Centenary. http:/ / www. easychair. org/
publications/ ?page=1303694832.
[52] cf his subchapter "The Church–Turing Thesis" (p. 47–49) in his chapter "Algorithms and Turing machines" in his 1990 (2nd edition)
Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, Oxford UK. Also his a final chapter
titled "Where lies the physics of mind?" where, in a subsection he describes "The non-algorithmic nature of mathematical insight" (p. 416–8).
[53] Super-Recursive Algorithms (Monographs in Computer Science), Springer, 2005. ISBN 0-387-95569-0

References
• Ben-Amram, A.M. (2005). "The Church-Turing Thesis and its Look-Alikes". SIGACT News 36 (3): 113–116.
doi: 10.1145/1086649.1086651 ([Link]
• Bernstein, E; Vazirani, U. (1997). "Quantum complexity theory". SIAM Journal on Computing 26 (5):
1411–1473. doi: 10.1137/S0097539796300921 ([Link]
• Blass, Andreas; Yuri Gurevich (2003). "Algorithms: A Quest for Absolute Definitions" ([Link]
[Link]/~gurevich/Opera/[Link]). Bulletin of European Association for Theoretical Computer Science
(81).
• Burgin, Mark (2005). "Super-recursive algorithms". Monographs in computer science. Springer.
ISBN 0-387-95569-0.
ChurchTuring thesis 59

• Church, Alonzo (1932). "A set of Postulates for the Foundation of Logic". Annals of Mathematics 33 (2):
346–366. doi: 10.2307/1968337 ([Link] JSTOR 1968337 ([Link]
org/stable/1968337).
• Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of
Mathematics 58 (58): 345–363. doi: 10.2307/2371045 ([Link] JSTOR 2371045
([Link]
• Church, Alonzo (1936). "A Note on the Entscheidungsproblem". Journal of Symbolic Logic (1): 40–41.
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper & S. S. Goncharov.
Computability and Models: Perspectives East and West. Kluwer Academic/Plenum Publishers. pp. 137–160.
• Martin Davis, ed. (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems
And Computable Functions. New York: Raven Press. Includes original papers by Gödel, Church, Turing, Rosser,
Kleene, and Post mentioned in this section.
• Eberbach, E.; Wegner, P. (October 2003). "Beyond Turing Machines". Bulletin of the European Association for
Theoretical Computer Science (81): 279–304.
• Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H.J. Barwise, H.J. Keisler, and K.
Kunen. The Kleene Symposium. North-Holland Publishing Company. pp. 123–148.
• Gandy, Robin (1994–5). Rolf Herken, ed. The universal Turing Machine: A Half-Century Survey. New York:
Wien Springer–Verlag. pp. 51ff. ISBN 3-211-82637-8.
• Gödel, Kurt (1965) [1934]. "On Undecidable Propositions of Formal Mathematical Systems". In Davis, M. The
Undecidable. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). New York:
Raven Press.
• Gödel, Kurt (1936). "On The Length of Proofs". Ergenbnisse eines mathematishen Kolloquiums (in German)
(Heft) (7): 23–24. Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll,
etc.
• Gurevich, Yuri (June 1988). "On Kolmogorov Machines and Related Issues". Bulletin of European Association
for Theoretical Computer Science (35): 71–82.
• Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms" (http://
[Link]/~gurevich/Opera/[Link]). ACM Transactions on Computational Logic 1 (1): 77–111.
doi: 10.1145/343369.343384 ([Link]
• Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal fur die reine und angewandte
Mathematik (166): 1–8.
• Hofstadter, Douglas R.. "Chapter XVII: Church, Turing, Tarski, and Others". Gödel, Escher, Bach: an Eternal
Golden Braid.
• Kleene, Stephen Cole (1935). "A Theory of Positive Integers in Formal Logic". American Journal of Mathematics
57 (57): 153–173 & 219–244. doi: 10.2307/2372027 ([Link] JSTOR 2372027
([Link]
• Kleene, Stephen Cole (1936). "Lambda-Definability and Recursiveness". Duke Mathematical Journal (2):
340–353.
• Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". American Mathematical Society
Transactions (Transactions of the American Mathematical Society, Vol. 53, No. 1) 54 (1): 41–73. doi:
10.2307/1990131 ([Link] JSTOR 1990131 ([Link]
1990131). Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and
proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis
(in Kleene 1952:300) and name it "Church's Thesis" (Kleene 1952:317) (i.e., the Church thesis).
• Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. OCLC 523942 ([Link]
[Link]/oclc/523942).
ChurchTuring thesis 60

• Knuth, Donald (1973). The Art of Computer Programming. 1/Fundamental Algorithms (2nd ed.).
Addison–Wesley.
• Kugel, Peter (November 2005). "Communications of the ACM". It's time to think outside the computational box
48 (11).
• Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Upper Saddle River, NJ, USA:
Prentice-Hall.
• Manna, Zohar (1974) [2003]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0.
• Markov, A.A. (1960) [1954]. "The Theory of Algorithms". American Mathematical Society Translations 2 (15):
1–14.
• Pour-El, M.B.; Richards, J.I. (1989). Computability in Analysis and Physics. Springer Verlag.
• Rosser, J. B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". The Journal
of Symbolic Logic (The Journal of Symbolic Logic, Vol. 4, No. 2) 4 (2): 53–60. doi: 10.2307/2269059 ([Link]
[Link]/10.2307/2269059). JSTOR 2269059 ([Link]
• Soare, Robert (1996). "Computability and Recursion". Bulletin of Symbolic Logic (2): 284–321.
• Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church–Turing Barrier. Springer.
ISBN 9780-387308869.
• Turing, A. M. (1937) [Delivered to the Society November 1936], "On Computable Numbers, with an Application
to the Entscheidungsproblem" ([Link]
Proceedings of the London Mathematical Society, 2 42: 230–65, doi: 10.1112/plms/s2-42.1.230 ([Link]
org/10.1112/plms/s2-42.1.230) and Turing, A.M. (1938). "On Computable Numbers, with an Application to
the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. 2 43 (1937).
pp. 544–6. doi: 10.1112/plms/s2-43.6.544 ([Link] (See also: Davis
1965:115ff)
• Olszewski, Adam (2006). Church's Thesis After 70 Years.
• Gabbay, D.M. (2001). Handbook of Philosophical Logic 1 (2nd ed.).

External links
• The Church–Turing Thesis ([Link] entry by B. Jack Copeland in the
Stanford Encyclopedia of Philosophy.
• Computation in Physical Systems ([Link] A
comprehensive philosophical treatment of relevant issues.
Theoretical computer science 61

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses
on more abstract or mathematical aspects of computing and includes the theory of computation.

Scope
It is not easy to circumscribe the theory areas precisely and the ACM's Special Interest Group on Algorithms and
Computation Theory (SIGACT) describes its mission as the promotion of theoretical computer science and notes:
The field of theoretical computer science is interpreted broadly so as to include algorithms, data
structures, computational complexity theory, distributed computation, parallel computation, VLSI,
machine learning, computational biology, computational geometry, information theory, cryptography,
quantum computation, computational number theory and algebra, program semantics and verification,
automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis
on mathematical technique and rigor.
To this list, the ACM's journal Transactions on Computation Theory adds coding theory, computational learning
theory and theoretical computer science aspects of areas such as databases, information retrieval, economic models
and networks. Despite this broad scope, the "theory people" in computer science self-identify as different from the
"applied people." Some characterize themselves as doing the "(more fundamental) 'science(s)' underlying the field of
computing." Other "theory-applied people" suggest that it is impossible to separate theory and application. This
means, the so-called "theory people" regularly use experimental science(s) done in less-theoretical areas such as
software system research. This also means, there is more cooperation than mutually exclusive competition between
theory and application.

P = NP ?

Mathematical logic Automata Number theory Graph theory Computability theory Computational complexity
theory theory

GNITIRW-TERCES

Cryptography Type theory Category Computational Quantum computing

theory geometry theory

History
While formal algorithms have existed for millennia (Euclid's algorithm for determining the greatest common divisor
of two numbers is still used in computation), it was not until 1936 that Alan Turing, Alonzo Church and Stephen
Kleene formalized the definition of an algorithm in terms of computation. While binary and logical systems of
mathematics had existed before 1703, when Gottfried Leibniz formalized logic with binary values for true and false.
While logical inference and mathematical proof had existed in ancient times, in 1931 Kurt Gödel proved with his
incompleteness theorem that there were fundamental limitations on what statements could be proved or disproved.
These developments have led to the modern study of logic and computability, and indeed the field of theoretical
computer science as a whole. Information theory was added to the field with a 1948 mathematical theory of
Theoretical computer science 62

communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of learning
in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural
networks and parallel distributed processing were established. In 1971, Stephen Cook and, working independently,
Leonid Levin, proved that there exist practically relevant problems that are NP-complete – a landmark result in
computational complexity theory.
With the development of quantum mechanics in the beginning of the 20th century came the concept that
mathematical operations could be performed on an entire particle wavefunction. In other words, one could compute
functions on multiple states simultaneously. This led to the concept of a quantum computer in the latter half of the
20th century that took off in the 1990s when Peter Shor showed that such methods could be used to factor large
numbers in polynomial time, which, if implemented, would render most modern public key cryptography systems
uselessly insecure.
Modern theoretical computer science research is based on these basic developments, but includes many other
mathematical and interdisciplinary problems that have been posed.

Organizations
• European Association for Theoretical Computer Science
• SIGACT

Journals and newsletters

• Information and Computation
• Theory of Computing (open access journal)
• Formal Aspects of Computing
• Journal of the ACM
• SIAM Journal on Computing (SICOMP)
• SIGACT News
• Theoretical Computer Science
• Theory of Computing Systems
• International Journal of Foundations of Computer Science
• Chicago Journal of Theoretical Computer Science (open access journal)
• Foundations and Trends in Theoretical Computer Science
• Journal of Automata, Languages and Combinatorics
• Acta Informatica
• Fundamenta Informaticae
• ACM Transactions on Computation Theory
• ACM Transactions on Algorithms
• Information Processing Letters
Theoretical computer science 63

Conferences
• Annual ACM Symposium on Theory of Computing (STOC)[1]
• Annual IEEE Symposium on Foundations of Computer Science (FOCS)
• ACM–SIAM Symposium on Discrete Algorithms (SODA)
• Annual Symposium on Computational Geometry (SoCG)[2]
• International Colloquium on Automata, Languages and Programming (ICALP)
• Symposium on Theoretical Aspects of Computer Science (STACS)
• International Conference on Theory and Applications of Models of Computation (TAMC)
• European Symposium on Algorithms (ESA)
• IEEE Symposium on Logic in Computer Science (LICS)
• International Symposium on Algorithms and Computation (ISAAC)
• Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
• Workshop on Randomization and Computation (RANDOM)
• Computational Complexity Conference (CCC)
• ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
• ACM Symposium on Principles of Distributed Computing (PODC)
• International Symposium on Fundamentals of Computation Theory (FCT)[3]

Notes
[1] The 2007 Australian Ranking of ICT Conferences (http:/ / www. core. edu. au/ rankings/ Conference Ranking Main. html): tier A+.
[2] The 2007 Australian Ranking of ICT Conferences (http:/ / www. core. edu. au/ rankings/ Conference Ranking Main. html): tier A.
[3] FCT 2011 (http:/ / fct11. ifi. uio. no/ ) (retrieved 2013-06-03)

Further reading
• Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of
theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1. Covers theory of
computation, but also program semantics and quantification theory. Aimed at graduate students.

External links
• Theoretical Computer Science at PSG College of Technology, Coimbatore ([Link]
department/appmaths)
• SIGACT directory of additional theory links ([Link]
• Theory Matters Wiki ([Link] Theoretical Computer Science (TCS) Advocacy Wiki
• [ne[Link] Usenet [Link]]
• List of academic conferences in the area of theoretical computer science ([Link]
confsearch/faces/pages/[Link]?topic=Theory&sortMode=1&graphicView=1) at confsearch ([Link]
[Link])
• Theoretical Computer Science - StackExchange ([Link] a Question and Answer
site for researchers in theoretical computer science
• Computer Science Animated ([Link]
• [Link] Massachusetts Institute of Technology
Article Sources and Contributors 64

Article Sources and Contributors

Run time (program lifecycle phase) Source: [Link] Contributors: A. B., Abarnea 2000, Abdull, AlFReD-NSH, Amtiss, Ancheta Wis, Anvish,
Anwar saadat, Atfin, Babbage, Btyner, Bwbaugh, [Link], CatherineMunro, Comexpert1, Comvert, Conmiro, Creidieki, Cybercobra, DerHexer, DexDor, Dfletter, Diego Moya, Dsimic,
Dysprosia, Edupedro, FcxSanya, Forderud, Galoubet, Giftlite, Glenn, Greenrd, Grstain, Isnow, Jamesday, Jfmantis, Jjk, JonHarder, Jonemerson, Jorge Stolfi, Jsmethers, Juzeris, Krallja, Lampak,
Luís Felipe Braga, MER-C, MIT Trekkie, Magioladitis, Maury Markowitz, Melody Lavender, Mhrk, Mikeblas, Minghong, Mk*, NapoliRoma, OlEnglish, Peterwhy, Petri Krohn, [Link],
Pnm, Retodon8, Sae1962, Sam Pointon, Samsara, Seanhalle, Seano1, Simian1k, Soumyasch, Sp33dyphil, Stevenrasnick, TMN, TakuyaMurata, Tarotcards, Three-quarter-ten, Tobias Bergemann,
Toussaint, UnitedStatesian, Vald, Whaa?, Wik, William Avery, Wnissen, Writtenonsand, Yuval madar, Yvwv, Zoicon5, Zundark, 76 anonymous edits

Best, worst and average case Source: [Link] Contributors: [Link], AdSR, Altenmann, Andreas Kaufmann, Angela,
Beekeepingschool, Brazzy, Brighterorange, Brycehughes, Cedar101, Charles Matthews, Charvest, DWay, Dark Silver Crow, Dcoetzee, DevastatorIIC, Dfletter, Dieter Simon, EagleFan, Ed Poor,
Fasten, Gardar Rurak, Gautham tpsz, Grinning Fool, Ianb1469, Jacobko, JavierMC, Kgautam28, Lee Daniel Crocker, Liso, Localh77, Malcohol, Materialscientist, Michael Hardy, Mike Rosoft,
Mostargue, Muro de Aguas, Nard the Bard, Nayuki, Octalc0de, Ohnoitsjamie, Paul G, Pgan002, Phils, Pol098, Populus, Pownuk, Radagast83, Reinyday, RobinK, Rory096, Ruud Koot, Sabbut,
Scasa155, Some jerk on the Internet, Spidern, Spl, Taemyr, TakuyaMurata, The Anome, Timwi, [Link], Wolfkeeper, ‫ﻣﺎﻧﻲ‬, 54 anonymous edits

Big O notation Source: [Link] Contributors: [Link], 4v4l0n42, A-Ge0, A. Pichler, ABCD, Abdull, Adashiel, Addps4cat, Aelvin,
Ahmad Faridi, Ahoerstemeier, Alan smithee, Alex Selby, Algoman101, Alksentrs, AllanBz, Altenmann, AnOddName, Andre Engels, Andreas Kaufmann, Andyhowlett, Ankit Maity, Anonymous
Dissident, Anthony Appleyard, Apanag, Arjayay, Arno Matthias, Arthur Rubin, Arunmoezhi, Arvindn, Ascánder, AvicAWB, AxelBoldt, B4hand, BMB, Bagsc, Barak Sh, Baronjonas, Ben pcc,
BenFrantzDale, Bergstra, Bhny, Bird of paradox, Bkell, Bomazi, Booyabazooka, Borgx, Brad7777, Breno, Brion VIBBER, Btyner, Bubba73, Buster79, C45207, CBKAtTopsails, CRGreathouse,
Calculuslover, Cbarlow3, Charles Matthews, CharlesGillingham, ChazBeckett, ChrisForno, ChrisGualtieri, Colfulus, Compotatoj, Connelly, Conversion script, Cookie4869, CosineKitty, Curb
Chain, Curps, Cybercobra, CyborgTosser, Czar, D4g0thur, DFS454, Dachshund, Dadudadu, Damian Yerrick, Danakil, Danny, Dark Charles, David Eppstein, Davidwt, Dcljr, Dcoetzee, Dean p
foster, Deeparnab, Den fjättrade ankan, Derlay, Dhuss, Diberri, Diego diaz espinoza, Dionyziz, Dmr2, DniQ, Donfbreed, Doradus, Dr. Universe, DrHow, Draco flavus, Drpaule, Duagloth,
Dysprosia, EconoPhysicist, Efnar, El C, Elephant in a tornado, Eleveneleven, Elias, EmilJ, Enochlau, Epachamo, Eric119, Ernie shoemaker, Eus Kevin, FauxFaux, Fayenatic london, Fede Reghe,
Felix Wiemann, Fennec, FiachraByrne, Fibonacci, FilipeS, Flouran, Foxjwill, Fredrik, Fvw, Gadig, Gene Ward Smith, GeordieMcBain, Giftlite, Gilliam, Gjd001, Glassmage, Glrx, Gracenotes,
Graham87, Gremagor, Gutza, [Link], Haham hanuka, Hans Adler, Hdante, Head, Headbomb, HenningThielemann, Henrygb, Hermel, Hlg, Ichernev, Intgr, InverseHypercube, Isis, Ixfd64,
JHMM13, JIP, Jacobolus, James.S, Jaredwf, Javit, Jeronimo, Jim1138, Jleedev, JoeKearney, JoergenB, JohnWStockwell, Jolsfa123, Jonathanzung, Josephjeevan, JoshuaZ, Jowan2005, Jpkotta,
Jthillik, Justin W Smith, Jwh335, Kan8eDie, Katsushi, KneeLess, KoenDelaere, Koertefa, Koffieyahoo, Kri, LC, LOL, Lambiam, Lamro, Leithp, Leonard G., LeonardoGregianin, Leycec, Linas,
[Link], Lugnad, Luqui, MFH, MIT Trekkie, Macrakis, Mad Jaqk, Maksim-e, Manmanmamamamama, Marc van Leeuwen, MarkOlah, MathMartin, Matiasholte, Mattbuck, McKay, Mcstrother,
Melcombe, Meldraft, Michael Hardy, Michael Rogers, Michael Slone, Miguel, Mike Schwartz, Mindmatrix, Mitchoyoshitaka, Miym, Mobius, Modeha, Mpagano, Mrypsilon, Mstuomel, Mxn,
Najeeb1010, Nbarth, NehpestTheFirst, Neilc, Nejko, NeoUrfahraner, Netheril96, Ngorade, Nils Grimsmo, NovaDog, O Pavlos, Oleg Alexandrov, Oliphaunt, Opelio, Optikos, Ott2, PGWG,
PL290, Patrick, Patrick Lucas, Paul August, PaulTanenbaum, Paxcoder, Pcuff, Pete4512, PhilKnight, Philip Trueman, Plutor, Poor Yorick, Prosfilaes, Prumpf, Quendus, Qwfp, R'n'B, R.e.b.,
R3m0t, Raknarf44, Rebroad, Reinderien, Retrolord, RexNL, Rfl, Rgiuly, Riceplaytexas, Rjwilmsi, RobertBorgersen, RobinK, Rockingravi, Rogerdpack, Rovenhot, Royote, Rschwieb, Ruud
Koot, Sabalka, Sameer0s, Sapphorain, SchfiftyThree, Sciurinæ, ScotsmanRS, Shalom Yechiel, Shellgirl, Shizhao, Shoessss, Shreevatsa, Simetrical, Simon Fenney, Skaraoke, Sligocki, Smjg,
Sophus Bie, Spitzak, [Link], Stephen Compall, Stevenj, Stevertigo, Stimpy, Suruena, Svick, Sydbarrett74, Syncategoremata, Szepi, TNARasslin, Taemyr, TakuyaMurata, Tardis,
Tarotcards, Taw, The Anome, TheBiggestFootballFan, TheSeven, Thenub314, Tide rolls, Timwi, Toby Bartels, Tony Fox, Tosha, Tritium6, [Link], Ultimus, Universalss, User A1,
Vanisheduser12a67, Vecter, Vedant, VictorAnyakin, Walrus068, WavePart, Wavelength, Whosyourjudas, Whouk, Widr, Wikibuki, Writer on wiki, Wtmitchell, Yarin Kaul, ZAB, Zack,
Zeitgeist2.718, Zero sharp, ZeroOne, ZiggyMo, Zowch, Zundark, Zvika, Île flottante, 711 anonymous edits

Computational complexity theory Source: [Link] Contributors: [Link], 16@r, [Link], [Link], [Link], APH,
Aaron Nitro Danielson, Abatasigh, Adavidb, AidaFernandaUFPE, Alexbrandts, Alotau, Altenmann, Andrei Stroe, Andris, Aphaia, ArnoldReinhold, Arthaey, Arthur Rubin, Arvindn, Ascánder,
Auminski, AvicAWB, AvnishIT, AxelBoldt, Barcex, Bassbonerocks, Battamer, Beland, Ben Standeven, Bethnim, Bgwhite, Bkell, Blokhead, Bo Jacoby, Booyabazooka, Bouke, Brad7777,
Braincricket, Brianbjparker, Bruno Unna, Bsotomay, Bubba73, C. lorenz, CRGreathouse, Calculuslover800, Carbo1200, Cesarsorm, Chalst, Charles Matthews, CharlesGillingham, Charvest,
Chealer, Chinju, Chowbok, [Link], Cngoulimis, ConceptExp, Contrasedative, Conversion script, Creidieki, D climacus, [Link], Daniel Quinlan, David Eppstein, David Gerard,
David Newton, [Link], DavidSJ, Dcoetzee, Decrease789, Deflagg, Deltahedron, DerGraph, Dissident, Djhulme, Dlu776, Dmcq, Dmitri pavlov, Dmyersturnbull, Docu, Doradus,
Dragonflare82, Drizzd, Droll, Déjà Vu, E23, Egriffin, Ehsan, Ekotkie, Epbr123, ErrantX, Erudecorp, [Link], Everyking, Flammifer, Four Dog Night, Fredrik, Fuujuhi, GPhilip, Gaius
Cornelius, Gdr, Getonyourfeet, Giftlite, GrEp, Graham87, GregorB, Groupthink, Grsbmd, GulDan, Harryboyles, Hazmat2, Headbomb, Hegariz, Henning Makholm, Henrygb, Hermel, Hfastedge,
Hiihammuk, Hmonroe, Huynl, Ink-Jetty, Intgr, InverseHypercube, Ixfd64, JRSpriggs, Jaksmata, Jamesd9007, Jeff Dahl, Jimbreed, Jitse Niesen, Jleedev, Jlpinar83, Jmencisom, John Vandenberg,
JohnBlackburne, Johnuniq, Julianiacoponi, Klausness, Knutux, Koavf, Konstable, Krishnachandranvn, Kurykh, LC, LJosil, Larry laptop, Leibniz, Linas, Little_guru, LokiClock, Looxix, Magmi,
Manway, MarcelB612, MassimoLauria, Mastergreg82, MathMartin, Maurice Carbonaro, Mav, McKay, Mdd, Michael Hardy, MichiHenning, Mik01aj, Mikeblas, Miym, Mpatel, Muditjai,
Multipundit, Mycer1nus, N12345n, Nixdorf, Nneonneo, Obradovic Goran, Oleg Alexandrov, Omicronpersei8, Orange Suede Sofa, OrgasGirl, Orz, [Link], Pcap, Pete142, Phil Boswell,
Philip Trueman, Pichpich, Policron, Populus, Postrach, Powo, PrologFan, Prumpf, Quackor, Quotient group, RainR, Readams, Rednas1234, Rend, RexNL, Rich Farmbrough, Ripper234,
Rjwilmsi, Robert Merkel, RobinK, Rogerdpack, Ruud Koot, Ryguasu, Ryulong, Sae1962, Scottcraig, Shenme, Siddhant, SimonTrew, Skippydo, SpaceMoose, Staszek Lem, Stevenmitchell,
Stevertigo, Talldean, Tarotcards, Tdgs, Tejas81, Template namespace initialisation script, The Anome, The Thing That Should Not Be, Themusicgod1, Tim32, Timwi, Tkgd2007, Tobias
Bergemann, Toddy1, Triwas, Trovatore, Twri, Van Parunak, VictorAnyakin, Walkerma, Waltnmi, Wavelength, Wernher, WikHead, WikiSlasher, Wikiklrsc, Wvbailey, Xiaoyang, Yill577, Ylloh,
Youandme, Young Pioneer, Zipcube, 242 ,‫ דוד שי‬anonymous edits

Computability Source: [Link] Contributors: 2ndMouse, Abatasigh, Aldur42, AshtonBenson, Ashutosh y0078, Bakilas, Ben Standeven,
BenRG, Bidabadi, CBM, CRGreathouse, Chaos, ChrisGualtieri, Dcoetzee, Disavian, Discospinster, Dmcq, [Link], Ewlyahoocom, Farzaneh, Giftlite, Haham hanuka, Hairy Dude, Hans
Adler, Harrigan, Hauke Pribnow, Javalenok, Jpvinall, Kbh3rd, Kizeral, Koavf, Ksyrie, Michael Hardy, Miym, Oleg Alexandrov, PJTraill, Pcap, Peter M Gerdes, Peterdjones, Readams, Ruud
Koot, Saforrest, Salgueiro, SamuelRiv, Sligocki, Steinsomers, Tachyon01, Timwi, Tobias Bergemann, Trevor Andersen, Trevor MacInnis, Trovatore, UKoch, Vectro, Waldir, Winston365,
Yill577, Yoderj, Zero sharp, 90 anonymous edits

Turing machine Source: [Link] Contributors: -Ril-, Abovechief, Abune, Accelerometer, Ad88110, AdamPeterman, Ahasn, Ahoerstemeier,
Ahpook, Alain Vey, Alamino, Alaniaris, Alejo2083, Alex Vinokur, Alexakh, Aliazimi, Allan McInnes, Altenmann, Altg20April2nd, Andre Engels, Anonymous Dissident, Antandrus, Anton203,
Apocalyps956, ArmadniGeneral, Artur adib, Arvindn, Ashutosh y0078, Ask123, Asmeurer, AxelBoldt, [Link], Barak, BearMachine, [Link], BenRG, Bensin, Bigmantonyd, BillyPreset,
Blahma, Blaxthos, Blehfu, BorgHunter, Brest, Brion VIBBER, Brouhaha, Bryan Derksen, Byrial, CBM, CRGreathouse, Cal 1234, Calibwam, Calliopejen1, Can't sleep, clown will eat me,
Carleas, Centrx, Cgay88, Chas zzz brown, Cheran, Cholmes75, Chridd, Chris Pressey, Chrsimon, Claygate, Cloversmate, Cocteau834, Cole Kitchen, Conversion script, Creidieki, CryptoDerk,
D6, DARTH SIDIOUS 2, DKqwerty, DYLAN LENNON, Dac04, Damian Yerrick, DanielCristofani, Davewho2, David Eppstein, David H Braun (1964), David Koller, DavisSta, Dcoetzee,
Derek Ross, Dicklyon, Diego Queiroz, Dominus, Doradus, Dratman, DroEsperanto, Droll, Drunkasian, [Link], Duxwing, Dzonatas, Ec5618, Edetic, Edward, Ehn, Ellywa, Ender2101,
ErikTheBikeMan, Eszett, Eubulides, Eus Kevin, Ewakened, False vacuum, Ferkel, Fleuryeric, Frap, Ftiercel, Fuzheado, GabrielF, Gachet, Gaius Cornelius, Gavia immer, Gdr, Gene Nygaard,
GermanX, Ggwine, Giftlite, Gioto, Glacialfox, Glome83, Golbez, GrafZahl, Graham87, GrahamDavies, Greenmatter, Grover cleveland, Gtxfrance, Gubbubu, Gwern, Gwythoff, Haeisen, Hairy
Dude, HamburgerRadio, HarisM, Harmil, Head, HenryCorp, Heooo, Heron, HeyStopThat, Howard McCay, Hu12, Hydrogen Iodide, Hzenilc, IMSoP, IShadowed, Iamfscked, Ieee8023, Ilia Kr.,
Iridescent, Isaac Rabinovitch, J. Spencer, JForget, JMK, JRSpriggs, JSimmonz, Jakenath, Jan Hidders, Jaredwf, Jauhienij, Jayc, Jeph paul, Jheiv, Jiawhein, Jidan, Jinwicked, Johnuniq, Jon
Awbrey, Jpbowen, Jpmelos, JpurvisUM, Jsorr, Jurvetson2, [Link], Kadin2048, Kaisershatner, Karl Dickman, Kevin143, Khym Chanur, King mike, Kirsted, Kku, Klickagent, Kne1p, Kntg,
Knutux, Krauss, Kris Schnee, L Kensington, LC, Laminatrix, LarryLACa, Ld100, Liftarn, Lingwitt, LittleDan, Loisel, Lokentaren, LoopZilla, Lotje, Lousyd, LucasVB, MDoggNoGFresh, MSGJ,
Machine Elf 1735, Maester mensch, Malleus Fatuorum, [Link], Martynas Patasius, Materialscientist, MathMartin, Matman132, MattGiuca, Merzbow, Metaeducation, Meursault2004,
Michael Hardy, Mitch Ames, Miym, Mmernex, MoraSique, Mormegil, Mousomer, Mrengy, Mvanveen, Nagato, Nanshu, Napoleon Dynamite42, NapoliRoma, Nikitadanilov, Nitishkorula, Nuno
Tavares, Nynexman4464, Obradovic Goran, Oleg Alexandrov, Olivier, Oneiros, Opticon, OrgasGirl, Ott2, P.L.A.R., Pagw, Parhamr, [Link], Patrick, Paul Stansifer, Pcap, Penumbra2000,
Pet5, Pexatus, Pfhyde, Phil Boswell, Philip Trueman, Pinethicket, Pleasantville, Plumpy, Policron, Polymath69, Populus, Pritamworld, Prolog, Psinu, Punctilius, Q17, QuiteUnusual, R.e.s., RCX,
Ramesh Chandra, Raul654, Rbkillea, Readams, Reedy, Reinderien, Rjpryan, Rjwilmsi, Roadrunner, Rob-nick, Robert Merkel, RobertG, RossPatterson, Rp, Ruud Koot, Saforrest, Satyr9, Schadel,
ScottSteiner, Sheerfirepower, Shell Kinney, Shizhao, Shreevatsa, SimonP, Sligocki, Slike2, Slowking Man, Smimram, Smmurphy, Snoyes, SpNeo, Spikey, Stevertigo, Strangethingintheland,
Streakofhope, Sun Creator, Sundar, Supertouch, Svick, Sviemeister, Syko, Szhu008, TShilo12, TakuyaMurata, Tarcieri, Tarotcards, TedColes, That Guy, From That Show!, The Anome,
Thecheesykid, Themfromspace, Therebelcountry, Theroadislong, Three887, Tide rolls, Tillwe, Timwi, TobiasKlaus, Tom-, TomT0m, Topbanana, Tristanb, Trovatore, UberScienceNerd,
Vasyaivanov, Ventolin, Verne Equinox, VictorAnyakin, Vineetgupta, Vrenator, Wavelength, Wednesday Next, Wenzchen, WikiTony999, Wikiwikifast, Wolfrock, Wshun, Wuffe, Wvbailey,
XJaM, Yan Kuligin, Yipdw, Yourmomblah, Zbxgscqf, Zeno Gantner, Александър, ‫ﺳﻌﯽ‬, 524 anonymous edits

Church–Turing thesis Source: [Link] Contributors: "alyosha", [Link], Alan Liefting, Aldux, Allan McInnes, AmirOnWiki, Anthony,
Arthur Rubin, AshtonBenson, Auntof6, AxelBoldt, BMF81, Ben Standeven, Bender235, Benplowman, Bkell, Bluewaves, Brighterorange, C. A. Russell, [Link], CBM, CRGreathouse, Caesura,
Article Sources and Contributors 65

Charles Matthews, CharlesGillingham, Chinju, Chris the speller, Christofurio, Claygate, Cole Kitchen, Connelly, Conversion script, Cornflake pirate, Costyn, Crowsnest, Cybercobra, Cyfal,
DA3N, DanielVallstrom, Danski14, Daran, Davehi1, David Eppstein, Dbenbenn, Dcattell, Dmd, Download, DrDnar, Dratman, Drilnoth, Dvgrn, Edward, Electron9, Elmiguel409, False vacuum,
Frankman, Fredkinfollower, Fromageestciel, Fsiler, Gavia immer, Gdr, Gene Nygaard, Giftlite, Gioto, GlaedrH, Gpgra, Greg Kuperberg, Gregbard, GregorB, Hairy Dude, Hans Adler,
Headbomb, HenryHRich, Heooo, Hkmaly, Htkym, Icek, Imz, InverseHypercube, Ivoras, Jaxad0127, Jerzy, Jonesey95, Jordgette, Jouster, Jpgordon, Julesd, Jushi, Kavya Manohar,
Kazkaskazkasako, Kizeral, Kjell André, Kntg, Knutux, Kurykh, Lambiam, Larry V, Leibniz, Lockfoot, Lollerskates, MER-C, Machine Elf 1735, Markhurd, Marq91, MartinHarper,
Marudubshinki, MathMartin, Mathias Barra, Matrixnaz, MattGiuca, MatthewIreland, Mav, Maxim Razin, Mdebets, Michael Hardy, Michael Slone, MichaelBillington, Miserlou, Miym, Mo ainm,
Morton Shumway, Multipundit, Mwaisberg, Neilc, NekoDaemon, Neocapitalist, Nihiltres, Ninly, Nk, Ocolon, Oliver Pereira, OrgasGirl, [Link], Pcap, Pde, Pgr94, Philip Trueman, Pierre
de Lyon, Pmt6sbc, Prometheus00, Psychonaut, Qaem, Quest for Truth, RP88, Rapsar, Rcaetano, Rich Farmbrough, Rjwilmsi, Roadrunner, RobinK, Robma, Ross Fraser, Ruud Koot, S Chapin,
Salvar, Sam Douglas, Sam Staton, Sampletalk, Schneelocke, SeeNoEvil, Sep102, Serketan, Shreevatsa, Simetrical, SimonP, Skeptical scientist, Skomorokh, Smimram, Smyth, Softtest123,
Soler97, Spellchecker, StN, Sunrise, Tabletop, Tagib, Tassedethe, TedColes, Tesi1700, Tigga, Timeroot, Timwi, Trovatore, Tygrrr, Wavelength, Widr, Wragge, Wvbailey, Xamuel, Yuriz,
Zemoxian, Zundark, ‫ﺳﻌﯽ‬, 143 anonymous edits

Theoretical computer science Source: [Link] Contributors: Arapajoe, Arbor, Arindamp, Balamurugan Kanakaraj, Ben1220, Brianbjparker,
Bsod2, Chricho, Christian75, Cic, Cogiati, Computhematics, David Eppstein, [Link], Dv82matt, EoGuy, Fortnow, GPhilip, GeorgeLouis, Giftlite, Gregbard, HRV, Haon, Hermel, Ian
Rastall, Ideogram, Impaciente, Intgr, Irwangatot, Ivan Štambuk, JLaTondre, Jaime v torres heredia, Jeff Erickson, Jimmaths, [Link], Kilva, Lmatt, Mahanga, Maurice Carbonaro,
[Link], Mejoribus, Merzul, Miym, Mrseacow, Neutral current, OrangeDog, Palaeovia, Papppfaffe, [Link], Pcap, Powo, Prari, Protez, RekishiEJ, Renku, Robertekraut,
RobinK, Rodrigo Folha, Ruud Koot, SLi, Salt Yeung, SamuelRiv, Sarimurat, Sbshah25, SchreyP, SpyMagician, Squids and Chips, Stan Shebs, Surlyduff50, Thore Husfeldt, Tobias Bergemann,
Zedoul, Zhoadon, Лев Дубовой, 82 anonymous edits
Image Sources, Licenses and Contributors 66

Image Sources, Licenses and Contributors

File:[Link] Source: [Link] License: GNU General Public License Contributors: Fede Reghe, Razorbliss
Image:TSP Deutschland [Link] Source: [Link] License: Public Domain Contributors: Original uploader was Kapitän Nemo at
[Link]. Later version(s) were uploaded by MrMonstar at [Link].
Image:Decision [Link] Source: [Link] License: GNU Free Documentation License Contributors: Hazmat2
Image:[Link] Source: [Link] License: Public Domain Contributors: Schadel ([Link]
File:Sorting quicksort [Link] Source: [Link] License: Creative Commons Attribution-ShareAlike 3.0 Unported
Contributors: Wikipedia:en:User:RolandH
Image:Complexity subsets [Link] Source: [Link] License: Public Domain Contributors: Hand drawn in Inkscape
Qef
Image:Complexity [Link] Source: [Link] License: Public Domain Contributors: Booyabazooka, Fæ, Mdd, Mike1024,
NeverDoING, 1 anonymous edits
Image:Theoretical computer [Link] Source: [Link] License: GNU Free Documentation License Contributors:
RobinK (talk) (Uploads)
Image:Turing machine [Link] Source: [Link] License: GNU Free Documentation License Contributors: User:Nynexman4464
Image:Turing machine [Link] Source: [Link] License: Public Domain Contributors: User:Nynexman4464. Original uploader
was Nynexman4464 at [Link]
Image:State diagram 3 state busy beaver [Link] Source: [Link] License: Creative Commons
Attribution-Sharealike 3.0 Contributors: Diego Queiroz
Image:State diagram 3 state busy beaver 4 .JPG Source: [Link] License: GNU Free Documentation
License Contributors: User:Wvbailey
File:Model of a Turing [Link] Source: [Link] License: Creative Commons Attribution-Sharealike 3.0
Contributors: User:GabrielF
File:Lego Turing [Link] Source: [Link] License: Creative Commons Attribution 3.0 Contributors: TomT0m
File:[Link] Source: [Link] License: Public Domain Contributors: Cepheus
File:Elliptic curve [Link] Source: [Link] License: GNU Free Documentation License Contributors: Created by Sean κ.
+ 23:33, 27 May 2005 (UTC)
File:[Link] Source: [Link] License: Public Domain Contributors: User:AzaToth
File:Wang [Link] Source: [Link] License: Public Domain Contributors: Anomie, Blotwell, Ies, Maksim, Stannic
File:Commutative diagram for [Link] Source: [Link] License: Public Domain Contributors:
User:Cepheus
File:[Link] Source: [Link] License: Public Domain Contributors: Original uploader was
Gfonsecabr at [Link]. Later version(s) were uploaded by McLoaf at [Link].
File:[Link] Source: [Link] License: GNU Free Documentation License Contributors: Original uploader was
MuncherOfSpleens at [Link]
License 67

License
Creative Commons Attribution-Share Alike 3.0
//[Link]/licenses/by-sa/3.0/