In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
and
quantum physics
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, q ...
, the Church–Turing–Deutsch principle (CTD principle) is a stronger, physical form of the
Church–Turing thesis formulated by
David Deutsch
David Elieser Deutsch ( ; born 18 May 1953) is a British physicist at the University of Oxford. He is a Visiting Professor in the Department of Atomic and Laser Physics at the Centre for Quantum Computation (CQC) in the Clarendon Laboratory o ...
in 1985. The principle states that a
universal computing device can
simulate
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the ...
every
physical process.
History
The principle was stated by Deutsch in 1985 with respect to
finitary machines and processes. He observed that
classical physics, which makes use of the concept of
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s, cannot be simulated by a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...
, which can only represent
computable reals. Deutsch proposed that
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thoug ...
s may actually obey the CTD principle, assuming that the laws of
quantum physics
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, q ...
can completely describe every physical process.
An earlier version of this thesis for classical computers was stated by Alan Turing's friend and student
Robin Gandy
Robin Oliver Gandy (22 September 1919 – 20 November 1995) was a British mathematician and logician. He was a friend, student, and associate of Alan Turing, having been supervised by Turing during his PhD at the University of Cambridge, where ...
in 1980.
See also
*
Bekenstein bound
In physics, the Bekenstein bound (named after Jacob Bekenstein) is an upper limit on the thermodynamic entropy ''S'', or Shannon entropy ''H'', that can be contained within a given finite region of space which has a finite amount of energy—or co ...
*
Digital physics
Digital physics is a speculative idea that the universe can be conceived of as a vast, digital computation device, or as the output of a deterministic or probabilistic computer program. The hypothesis that the universe is a digital computer was ...
*
Holographic principle
The holographic principle is an axiom in string theories and a supposed property of quantum gravity that states that the description of a volume of space can be thought of as encoded on a lower-dimensional boundary to the region — such as a ...
*
Quantum complexity theory
Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems i ...
Notes
References
*
Further reading
*
* Christopher G. Timpson ''Quantum Computers: the Church-Turing Hypothesis Versus the Turing Principle'' in Christof Teuscher, Douglas Hofstadter (eds.) ''Alan Turing: life and legacy of a great thinker'', Springer, 2004, , pp. 213–240
External links
*
{{DEFAULTSORT:Church-Turing-Deutsch principle
Alan Turing
Principles
Computability theory
Theory of computation