# Church–Turing–Deutsch principle

__: Principle in computer science__

**Short description**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.

## History

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]}

## See also

## Notes

- ↑ Nielsen, Michael (16 April 2004). "Interesting problems: The Church–Turing–Deutsch Principle". http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle. Retrieved 10 May 2014.
- ↑ Gandy, R. (1980). Church’s thesis and principles for mechanisms.
*Studies in Logic and the Foundations of Mathematics*(101), 123–148 - ↑ Kaznatcheev, Artem (2014). "Falsifiability and Gandy's variant of the Church-Turing thesis".
*Theory, Evolution, and Games Group Blog*. https://egtheory.wordpress.com/2014/09/01/falsifiability-and-gandys-variant-of-the-church-turing-thesis/. Retrieved 23 July 2018.

## References

- Deutsch, D. (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer".
*Proceedings of the Royal Society***400**(1818): 97–117. doi:10.1098/rspa.1985.0070. Bibcode: 1985RSPSA.400...97D. http://www.cs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf. Retrieved 2011-08-17.

## Further reading

- Deutsch, D. (1997). "6: Universality and the Limits of Computation".
*The Fabric of Reality*. New York: Allan Lane. ISBN 978-0-14-027541-4. - 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:3-540-20020-7, pp. 213–240

## External links

- Nielsen, Michael (2004-04-16). "Interesting problems: The Church–Turing–Deutsch Principle". http://michaelnielsen.org/blog/?p=71.

Original source: https://en.wikipedia.org/wiki/Church–Turing–Deutsch principle.
Read more |