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.[1] The principle states that a universal computing device can simulate every physical process.
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 numbers, cannot be simulated by a Turing machine, 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 in 1980.[2] [3]
A similar thesis was stated by Michael Freedman in an early review of topological quantum computing with Alexei Kitaev, Michael J. Larsen, and Zhenghan Wang, known as the Freedman-Church-Turing thesis[4] :
This thesis differs from the Church-Turing-Deutsch thesis insofar as it is a statement about computational complexity, and not computability.