Principio de Church-Turing-Deutsch

Principio en informática

En informática y física cuántica , el principio de Church-Turing-Deutsch ( principio CTD ) es una forma física más fuerte de la tesis de Church-Turing formulada por David Deutsch en 1985. ^[1] El principio establece que un dispositivo informático universal puede simular cualquier proceso físico .

Historia

El principio fue enunciado por Deutsch en 1985 con respecto a las máquinas y procesos finitarios . Observó que la física clásica , que hace uso del concepto de números reales , no puede ser simulada por una máquina de Turing , que solo puede representar números reales computables . Deutsch propuso que las computadoras cuánticas pueden realmente obedecer el principio CTD, suponiendo que las leyes de la física cuántica pueden describir completamente cada proceso físico.

Una versión anterior de esta tesis para las computadoras clásicas fue formulada por el amigo y alumno de Alan Turing, Robin Gandy, en 1980. ^{[2] [3]}

Michael Freedman formuló una tesis similar en una revisión temprana de la computación cuántica topológica con Alexei Kitaev , Michael J. Larsen y Zhenghan Wang , conocida como la tesis de Freedman-Church-Turing: ^[4]

"Todos los modelos computacionales 'razonables' que añaden los recursos de la mecánica cuántica (o teoría cuántica de campos) a la computación clásica producen clases intersimulables (eficientemente): hay una teoría cuántica de la computación".

Esta tesis se diferencia de la tesis de Church-Turing-Deutsch en que es una afirmación sobre la complejidad computacional y no sobre la computabilidad.

Véase también

• El límite de Bekenstein
• Física digital
• Principio holográfico
• Teoría de la complejidad cuántica
• El demonio de Laplace

Notas

1. Nielsen, Michael (16 de abril de 2004). «Problemas interesantes: el principio de Church-Turing-Deutsch» . Consultado el 10 de mayo de 2014 .
2. Gandy, R. (1980). Tesis y principios de Church para los mecanismos. Estudios de lógica y fundamentos de las matemáticas (101), 123-148
3. Kaznatcheev, Artem (2014). "Falsabilidad y variante de Gandy de la tesis de Church-Turing". Blog del grupo de teoría, evolución y juegos . Consultado el 23 de julio de 2018 .
4. Freedman, Michael H.; Kitaev, Alexei; Larsen, Michael J.; Wang, Zhenghan (20 de septiembre de 2002). "Computación cuántica topológica". arXiv : quant-ph/0101025 .

Referencias

• Deutsch, D. (1985). «Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal» (PDF) . Actas de la Royal Society . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX  10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID  1438116. Archivado desde el original (PDF) el 2016-03-09 . Consultado el 2011-08-17 .

Lectura adicional

• Deutsch, D. (1997). "6: Universalidad y límites de la computación". The Fabric of Reality . Nueva York: Allan Lane. ISBN. 978-0-14-027541-4.
• Christopher G. Timpson Computadoras cuánticas: la hipótesis de Church-Turing frente al principio de Turing en Christof Teuscher, Douglas Hofstadter (eds.) Alan Turing: vida y legado de un gran pensador , Springer, 2004, ISBN 3-540-20020-7 , pp. 213–240 

Enlaces externos

• Nielsen, Michael (16 de abril de 2004). "Problemas interesantes: el principio de Church-Turing-Deutsch".