文档介绍：Quantum theory, the Church-Turing principle and the universal
puter
DAV I D DEUTSCH
Appeared in Proceedings of the Royal Society of London A 400, pp. 97-117 (1985)y
(Communicated by R. Penrose, . — Received 13 July 1984)
Abstract
It is argued that underlying the Church-Turing hypothesis there is an implicit
physical assertion. Here, this assertion is presented explicitly as a physical prin-
ciple: ‘every finitely realizable physical system can be perfectly simulated by a
universal puting machine operating by finite means’. Classical physics
and the universal Turing machine, because the former is continuous and the latter
discrete, do not obey the principle, at least in the strong form above. A class of
puting machines that is the quantum generalization of the class of Tur-
ing machines is described, and it is shown that quantum theory and the ‘universal
puter’ patible with the principle. Computing machines re-
sembling the universal puter could, in principle, be built and would
have many remarkable properties not reproducible by any Turing machine. These
do not include putation of non-recursive functions, but they do include
‘quantum parallelism’, a method by which certain probabilistic tasks can be per-
formed faster by a universal puter than by any classical restriction
of it. The intuitive explanation of these properties places an intolerable strain on
all interpretations of quantum theory other than Everett’s. Some of the numerous
connections between the quantum theory putation and the rest of physics
are explored. plexity theory allows a physically more reasonable
definition of the ‘complexity’ or ‘knowledge’ in a physical system than does clas-
plexity theory.
Current address: Centre for putation, Clarendon Laboratory, Department of Physics, Parks Road,
OX1 3PU Oxford, United Kingdom. Email: @
y This version (Summer 1999) was edited and converted to LATEX by Wim van Dam at the Centre for