Turing produced the Turing machine in an effort to answer the question
``Is there a mechanical procedure by which the truth or falsity of any
mathematical conjecture can be decided?'' Turing reasoned that if
there was such a method, and if it were truly mechanical in nature and
requiring no creative effort, then it could be performed by a Turing
machine. The proof offered by Turing that there is no such procedure
is the same as the proof of Turing's Halting problem, which states
that no Turing machine *H* can in general be given any arbitrary
Turing machine *X* and its input (*I*_{x}) as its own (*H*'s) input, and
determine whether *X* will run to completion on *I*_{x}. The
demonstration by Turing of a problem which can not be solved by a
Turing machine suggests the division of functions into two groups:
those that can be computed by a Turing machine and those that can not.

By the Church-Turing thesis we can generally say that functions that
are not Turing computable are simply ``not computable.'' It should be
stressed at this point that this classification of a function that is
not Turing computable as not computable in a general sense is due to
the **definitional** aspect of the Church-Turing thesis. It is a
logical possibility that some future computing machine will indeed be
able to compute some function that a Turing machine can not - however
no such machine is known, and the development of such a machine would
be a large breakthrough. Arguments can be made that no such machine
would be physically possible - however this is not a settled
question.

Determining if a function is computable at all is interesting, but this
distinction is not fine enough to determine if a function can
realistically be solved by a physical computer in a reasonable amount
of time. If a computation will take billions of years to compute, it
may as well be uncomputable from the perspective of the pragmatist. A
algorithm can be characterized by the number of operations and amount
of memory it requires to compute an answer given an input of size *n*.
These characterizations of the algorithm determine what is called the
algorithm's *running time* or *time complexity*.
Specifically, the time complexity of an algorithm to compute a
function is determined by looking at how the number of operations of
the algorithm scale with the size of the input of the function it
computes. We'll take the size of the input to be the number of bits
needed to represent that number in binary.

An algorithm which computes its output for an input of size *n* using
resources (computational steps, memory, etc.) that is bounded above by
a polynomial function of *n* are said to be of *polynomial
time*. For example if an algorithm with an input size of 10 bits
took
10^{4} +7*10^{2} + 1001 operations to compute its answer it would
be considered a polynomial time algorithm.

Problems which can be solved in polynomial time or less are generally
deemed to be *tractable*. An algorithm which solves a problem in
polynomial time may be referred to as *efficient*. Problems which
require more than polynomial time are usually considered to be
*intractable*, for example an algorithm which would require 2^{n}
operations for an input size of *n* would be considered intractable,
as the number of operations grows exponentially with the input size,
not polynomially. Generally tractable problems are considered to be
those which may practically be solved in the real world. (Shor)

In complexity theory, problems are often restated in terms of a
*decision problem* - this means that the function of interest
takes in its input and produces a yes or no answer.

Computer Scientists have grouped problems into a variety of complexity classes, below are some of the more well known.

**P**- : The class of decision problems which can be answered in
polynomial time.
**NP**- : Nondeterministic polynomial time, the class of decision
problems where a candidate for an answer can be verified as a
correct answer or not in polynomial time.
**NP-complete**- : The ``hardest'' problems in NP, this set has the interesting property that if any NP-complete problem can be solved in polynomial time, then P and NP are in fact the same. Whether P equals NP is an outstanding problem in computer science and complexity theory.

Given these distinctions, to determine if an function may be
*efficiently* computed by a classical computer there are two
questions that must be answered. First, can a Turing machine compute
the function, if so then the function is called computable. Second
the time complexity of the algorithm to be used must by considered.
In general if an algorithm requires polynomial time or less to compute
it is considered to be tractable, and if not it is considered to be
intractable.

Accordingly, interest in quantum computing is twofold. First it is of interest if a quantum computer can compute functions which are uncomputable on a classical computer, and second it is of interest whether an algorithm which is intractable on a Turing machine may be tractable on a quantum computer.