In computer science and quantum physics, the ChurchâÂÂTuringâÂÂDeutsch-Wolfram principle (CTDW principle) is a stronger, physical form of the Church–Turing thesis articulated in separate works by Stephen Wolfram and David Deutsch in 1985.
The principle states that a universal computing device can simulate every physical process.
A formulation of the principle was given by Stephen Wolfram in February 1985. In Undecidability and Intractability in Theoretical Physics , Wolfram wrote that
Wolfram states that such a principle would hold provided that physical systems have a finite density of information and that information can be transmitted only at a finite rate in a finite-dimensional space.
Later in 1985, David Deutsch stated the principle 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 obey the principle, assuming that the laws of quantum mechanics 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.
A similar thesis was later 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:
This thesis differs from the ChurchâÂÂTuringâÂÂDeutsch-Wolfram thesis insofar as it is a statement about computational complexity, and not computability.