Church–Turing–Deutsch principle
Encyclopedia
In computer science
and quantum physics, the Church–Turing–Deutsch principle (CTD principle) is a stronger, physical form of the Church–Turing thesis formulated by David Deutsch
in 1985. The principle states that a universal
computing device
can simulate
every physical process. The principle was originally stated by Deutsch with respect to finitary
machines and processes. He immediately observed that classical physics
, which makes use of the concept of real number
s, cannot be simulated by a Turing machine
, which can only represent computable reals. Deutsch proposed that quantum computer
s may actually obey CTD, assuming that the laws of quantum physics can completely describe every physical process.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 Deutsch
David Elieser Deutsch, FRS is an Israeli-British physicist at the University of Oxford. He is a non-stipendiary Visiting Professor in the Department of Atomic and Laser Physics at the Centre for Quantum Computation in the Clarendon Laboratory of the University of Oxford...
in 1985. The principle states that a universal
Universality (philosophy)
In philosophy, universalism is a doctrine or school claiming universal facts can be discovered and is therefore understood as being in opposition to relativism. In certain religions, universality is the quality ascribed to an entity whose existence is consistent throughout the universe...
computing device
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
can simulate
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
every physical process. The principle was originally stated by Deutsch with respect to finitary
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
machines and processes. He immediately observed that classical physics
Classical physics
What "classical physics" refers to depends on the context. When discussing special relativity, it refers to the Newtonian physics which preceded relativity, i.e. the branches of physics based on principles developed before the rise of relativity and quantum mechanics...
, which makes use of the concept of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, cannot be simulated by a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, which can only represent computable reals. Deutsch proposed that quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
s may actually obey CTD, assuming that the laws of quantum physics can completely describe every physical process.
See also
- Quantum complexity theoryQuantum complexity theoryQuantum complexity theory is a part of computational complexity theory in theoretical computer science. It studies complexity classes defined using quantum computers and quantum information which are computational models based on quantum mechanics...
- Digital physicsDigital physicsIn physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable...
- Holographic principleHolographic principleThe holographic principle is a property of quantum gravity and string theories which states that the description of a volume of space can be thought of as encoded on a boundary to the region—preferably a light-like boundary like a gravitational horizon...
and Bekenstein boundBekenstein boundIn physics, the Bekenstein bound is an upper limit on the entropy S, or information I, that can be contained within a given finite region of space which has a finite amount of energy—or conversely, the maximum amount of information required to perfectly describe a given physical system down to the...
, which prohibit unlimited precision real numbers in the physical universe
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, ISBN 3540200207, pp. 213–240