The Church-Turing Thesis

The basic idea of modern computing science is the view of
computation as a mechanical, rather than a purely mental
process.
A method, or procedure for achieving some desired
result is called *effective* or *mechanical* just
in case [17]

- is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
- will, if carried out without error, always produce the desired result in a finite number of steps;
- can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
- demands no insight or ingenuity on the part of the human being carrying it out.

Alan Turing and Alonzo Church both formalized the above definition
by introducing the concept of *computability by Turing machine*
and the mathematically equivalent concept of *recursive functions*
with the following conclusions:

Computing Machines

Despite its operationalistic approach, the above computability concept doesn't have much in common with the continuous nature of physics, so in order to build a computing machine , we have to introduce a labeling function which maps the analog physical states (e.g. the tension of a capacitor) to digital computational states (e.g. the value of a bit) The digital states have to be strings over some finite alphabet .

Since the above definition of computability requires a finite
number of both, symbols and instructions, the labeling function
only needs to apply on discrete intermediate machine states
so the temporal evolution of the
machine state is mapped onto a sequence of computational
states
where each transition
corresponds to one function
from a enumerable set
of (simple) instructions.^{2.1}The sequence
is called
*program*.

The states and are called the *input-* and the
*output-state*. The machine
thus implements the
function

(2.1) |

Computation as a Physical Process

The above definition of a computing machine poses severe restrictions on the interpretation of physical states. If we consider computation as a physical process, rather than a ``mechanical'' manipulation of symbols as defined in 2.1.1, we can drop all restrictions in the above definition which don't have a physical equivalent.

As we have showed in 1.3.2.3, the measurement of an observable with the according operator is only deterministic, if a system is in an eigenstate of . To account for the stochastic nature of quantum measurement, we have to replace the labeling function by a probabilistic operator which randomly chooses a string according to some probability distribution with .

Temporal Evolution

Since it is not possible to non-destructively measure a quantum system and we are only interested in the result of a computation, anyway, it is not necessary that a labeling is defined for the intermediate steps to of a computation i.e. it is not required to ``watch'' the temporal evolution of the system, as long as a labeling for the input- and output-state and is given.

While the transitions
still have
to correspond to (simple) operations from a enumerable
instruction set of quantum transformations,
the operators , don't have to directly correspond to
functions in .^{2.2}

In 1.3.2.6 we have shown that the temporal evolution
of a quantum system is mathematically described by unitary
operators, so a *quantum program*
is a composition of
elementary unitary transformations.

- ... instructions.
^{2.1} - For hypothetical machines with
unlimited memory, the instruction set might also be
infinitely which is not in accordance with Turing's original
definition of computability.
The Turing Machine avoids this problem by extending the computational states with an integer and using this ``head position'' as an additional parameter to the generated instructions. As (which can get arbitrary large) would be ``stored'' in the physical position of the head and not in the state of the head itself, it can still be claimed that the TM operates

*``by finite means''*.Even with our simpler model, we could avoid an infinitely instruction set, e.g. by interpreting a state with as the pair , and define the instructions as .

As we are discussing physical computers, which usually don't have unlimited memory, we can ignore this problem, and use the simpler and more general computer definition given above.

- ....
^{2.2} - Because of the reversibility of unitary operators, a direct correspondence would only be possible for bijective functions