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 (includi ...
and
quantum physics, 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 of ...
in 1985. The principle states that a
universal
Universal is the adjective for universe.
Universal may also refer to:
Companies
* NBCUniversal, a media and entertainment company
** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal
** Universal TV, a ...
computing device
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These program ...
can
simulate
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of Conceptual model, models; the model represents the key characteristics or behaviors of the selected system or proc ...
every
physical process
Physical changes are changes affecting the form of a chemical substance, but not its chemical composition. Physical changes are used to separate mixtures into their component compounds, but can not usually be used to separate compounds into chem ...
.
History
The principle was stated by Deutsch in 1985 with respect to
finitary
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operation ...
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 measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
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 algori ...
, which can only represent
computable reals. Deutsch proposed that
quantum computers may actually obey the CTD principle, assuming that the laws of
quantum physics 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 c ...
*
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 p ...
*
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
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