Church–Turing–Deutsch principle

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 [1] and David Deutsch [2] 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 [3], 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.[4] 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.[5][6]

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:[7]

"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.

See also

Notes

  1. ^ Copeland, B. Jack; Shagrir, Oron (December 2018). "The Church-Turing Thesis". Communications of the ACM. 62 (1): 66–74. doi:10.1145/3198448. Retrieved 1 March 2026.
  2. ^ Nielsen, Michael (16 April 2004). "Interesting problems: The Church–Turing–Deutsch Principle". Retrieved 10 May 2014.
  3. ^ Wolfram, Stephen (25 February 1985). "Undecidability and Intractability in Theoretical Physics". Physical Review Letters. 54 (7): 735–738. doi:10.1103/PhysRevLett.54.735.
  4. ^ Deutsch, D. (8 July 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.{{cite journal}}: CS1 maint: date and year (link)
  5. ^ Gandy, R. (1980). Church’s thesis and principles for mechanisms. Studies in Logic and the Foundations of Mathematics (101), 123–148
  6. ^ Kaznatcheev, Artem (2014). "Falsifiability and Gandy's variant of the Church-Turing thesis". Theory, Evolution, and Games Group Blog. Retrieved 23 July 2018.
  7. ^ Freedman, Michael H.; Kitaev, Alexei; Larsen, Michael J.; Wang, Zhenghan (2002-09-20). "Topological Quantum Computation". arXiv:quant-ph/0101025.

References

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
This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.