Introduction

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 $\mathcal{M}$ for achieving some desired result is called effective or mechanical just in case [17]

1. $\mathcal{M}$ is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
2. $\mathcal{M}$ will, if carried out without error, always produce the desired result in a finite number of steps;
3. $\mathcal{M}$ can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
4. $\mathcal{M}$ 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:

Turing's thesis

LCMs [logical computing machines i.e. Turing machines] can do anything that could be described as "rule of thumb" or "purely mechanical". [19]

Church's thesis

A function of positive integers is effectively calculable only if recursive. [18]

.

As the above statements are equivalent, they are commonly referred to as the Church-Turing Thesis which defines the scope of classical computing science.

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 $\mathcal{M}$, we have to introduce a labeling function $m$ which maps the analog physical states $S(t)$ (e.g. the tension of a capacitor) to digital computational states $s=\mathit{(}S(t))$ (e.g. the value of a bit) The digital states have to be strings over some finite alphabet $\Sigma$.

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 $S(t_0), S(t_1), \ldots$ so the temporal evolution of the machine state $S(t)$ is mapped onto a sequence of computational states $\{s_0,s_1,\ldots s_n\}$ where each transition $s_i \to s_{i+1}$ corresponds to one function $I_i:\Sigma^*\to\Sigma^*$ from a enumerable set $\mathbf{I}$ of (simple) instructions.^2.1The sequence $\pi=\{I_0,I_1,\ldots I_{n-1}\}$ is called program.

The states $s_0$ and $s_n$ are called the input- and the output-state. The machine $\mathcal{M}=(S,m,\Sigma,\pi)$ thus implements the function

$$f(s_0)= (I_0 \circ I_1 \circ \ldots \circ I_{n-1}) (s_0) \quad\mathrm{with}\quad s_0=m(S(0))\in\Sigma^*$$ (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.

Indeterminism

As we have showed in 1.3.2.3, the measurement of an observable $O$ with the according operator $O$ is only deterministic, if a system is in an eigenstate of $O$. To account for the stochastic nature of quantum measurement, we have to replace the labeling function $m$ by a probabilistic operator $M: \mathcal{H}\to\Sigma^*$ which randomly chooses a string $s$ according to some probability distribution $\delta_{\Psi}: s\to [0,1]$ with $\sum_s \delta_{\Psi}(s)=1$.

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 $\Psi(t_1)$ to $\Psi(t_{n-1})$ 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 $\Psi_0$ and $\Psi_n$ is given.

While the transitions $\Psi(t_i)\to\Psi(t_{i+1})$ still have to correspond to (simple) operations $U_i$ from a enumerable instruction set of quantum transformations, the operators $U_i$, don't have to directly correspond to functions in $\Sigma^*$.^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 $\pi=\{U_0,U_1,\ldots U_{n-1}\}$ is a composition of elementary unitary transformations.

Footnotes

... instructions.^2.1

For hypothetical machines with unlimited memory, the instruction set $\mathbf{I}$ 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 $s_i$ with an integer $p$ and using this ``head position'' as an additional parameter to the generated instructions. As $p$ (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 $s=\underline{\mathbf{1}}^p\underline{\mathbf{0}}t$ with $t\in\Sigma^*$ as the pair $s=(p,t)$, and define the instructions as $I_i(p,t):\mathbf{N}_0\times\Sigma^*\to\mathbf{N}_0\times\Sigma^*$.

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 $f:\Sigma^*\to\Sigma^*$