Church–Turing–Deutsch principle

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 numbers, cannot be simulated by a Turing machine, which can only represent computable reals. Deutsch proposed that quantum computers may actually obey CTD, assuming that the laws of quantum physics can completely describe every physical process.

See also

• Quantum complexity theory
• Digital physics
• Holographic principle and Bekenstein bound, which prohibit unlimited precision real numbers in the physical universe

References

• Deutsch, D. (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer". Proceedings of the Royal Society (London) (400): 97–117. http://www.cs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf. 

Further reading

• Deutsch, D. (1997). "6: Universality and the Limits of Computation". The Fabric of Reality. New York: Allan Lane. ISBN 014027541X. 
• 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

External links

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

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Theoretical computer science stubs Alan Turing Principles Computability theory Theory of computation Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Archivolt Gymnure Look at other dictionaries: Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… …   Wikipedia David Deutsch — Born 1953 (age 58) Haifa, Israel Fields Theoretical physics Quantum information science …   Wikipedia Alonzo Church — This article is about the mathematician and logician. For the president of the University of Georgia, see Alonzo S. Church. Alonzo Church Alonzo Church (1903–1995) …   Wikipedia Deutsch–Jozsa algorithm — The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992[1] with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998.[2] Although it is of little practical use …   Wikipedia Deutsch-Jozsa-Algorithmus — Der Algorithmus von Deutsch ist ein Algorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der… …   Deutsch Wikipedia Deutsch-Jozsa algorithm — The Deutsch Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca in 1998.cite journal author = David Deutsch and Richard Jozsa title =… …   Wikipedia Thèse de Church — La thèse de Church du nom du mathématicien Alonzo Church est une hypothèse ( thèse ) concernant la définition de la notion de calculabilité. Dans une forme dite physique [1], elle affirme que la notion physique de la calculabilité, définie comme… …   Wikipédia en Français David Deutsch — Saltar a navegación, búsqueda David Elieser Deutsch (nacido en 1953 en Haifa, Israel) es un físico de la Universidad de Oxford, miembro de la Royal Society. Es profesor visitante en el Department of Atomic and Laser Physics del Centre for Quantum …   Wikipedia Español Algorithme de Deutsch-Jozsa — L Algorithme de Deutsch Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998[1],[2]. Bien qu il ne soit pas d un grand intérêt… …   Wikipédia en Français Digital physics — In 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. Therefore, the universe can be conceived as either …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”