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.
History
A formulation of the principle was given by Stephen Wolfram in February 1985. In Undecidability and Intractability in Theoretical Physics, Wolfram wrote that
"[U]niversal computers are as powerful in their computational capacities as any physically realizable system can be, so that they can simulate any physical system."
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:
"All 'reasonable' computational models which add the resources of quantum mechanics (or quantum field theory) to classical computation yield (efficiently) inter-simulable classes: there is one quantum theory of computation."
This thesis differs from the Church–Turing–Deutsch-Wolfram thesis insofar as it is a statement about computational complexity, and not computability.