Hispanopedia Wiki
Articulo de referencia

Completitud de Turing

El Juego de la Vida de Conway es Turing-completo y puede simular cualquier sistema, incluido él mismo (en la imagen). En la teoría de la computabilidad , se dice que un sistema ...

Hispanopedia WikiContenido en espanolLectura gratuita

El Juego de la Vida de Conway es Turing-completo y puede simular cualquier sistema, incluido él mismo (en la imagen).

En la teoría de la computabilidad , se dice que un sistema de reglas de manipulación de datos (como un modelo de computación , un conjunto de instrucciones de una computadora , un lenguaje de programación o un autómata celular ) es Turing-completo o computacionalmente universal si puede usarse para simular cualquier máquina de Turing [ 1 ] [ 2 ] (ideada por el matemático e informático inglés Alan Turing ). Esto significa que este sistema es capaz de reconocer o decodificar otros conjuntos de reglas de manipulación de datos. La completitud de Turing se utiliza para expresar el poder de dicho conjunto de reglas de manipulación de datos. Prácticamente todos los lenguajes de programación actuales son Turing-completos. [ a ]

Un concepto relacionado es el de equivalencia de Turing : dos computadoras P y Q se consideran equivalentes si P puede simular a Q y Q puede simular a P. [ 4 ] La tesis de Church-Turing conjetura que cualquier función cuyos valores puedan ser calculados por un algoritmo puede ser calculada por una máquina de Turing, y por lo tanto, que si cualquier computadora del mundo real puede simular una máquina de Turing, es Turing equivalente a una máquina de Turing. Una máquina de Turing universal puede utilizarse para simular cualquier máquina de Turing y, por extensión, los aspectos puramente computacionales de cualquier posible computadora del mundo real. [ 5 ] [ 6 ] 

Para demostrar que algo es Turing-completo, basta con demostrar que puede utilizarse para simular algún sistema Turing-completo. Ningún sistema físico puede tener memoria infinita, pero si se ignora la limitación de la memoria finita, la mayoría de los lenguajes de programación son Turing-completos. [ 7 ] [ 8 ]

Uso no matemático

En el lenguaje coloquial , los términos "Turing-completo" y "equivalente a Turing" se utilizan para indicar que cualquier ordenador o lenguaje de programación de propósito general del mundo real puede simular aproximadamente los aspectos computacionales de cualquier otro ordenador o lenguaje de programación de propósito general del mundo real. En la práctica, esto da lugar a los conceptos de virtualización y emulación informática .

Las computadoras reales construidas hasta ahora pueden analizarse funcionalmente como una máquina de Turing de una sola cinta (que utiliza una "cinta" como memoria); por lo tanto, las matemáticas asociadas pueden aplicarse abstraiendo su funcionamiento lo suficiente. Sin embargo, las computadoras reales tienen recursos físicos limitados, por lo que solo son completas como autómatas lineales acotados . En contraste, la abstracción de una computadora universal se define como un dispositivo con un conjunto de instrucciones Turing-completo, memoria infinita y tiempo disponible infinito.

Definiciones formales

En la teoría de la computabilidad , se utilizan varios términos estrechamente relacionados para describir la potencia computacional de un sistema computacional (como una máquina abstracta o un lenguaje de programación ):

Completitud de Turing
Un sistema computacional capaz de calcular todas las funciones computables por una máquina de Turing se denomina Turing-completo (o Turing-potente). Alternativamente, dicho sistema es aquel que puede simular una máquina de Turing universal .
Equivalencia de Turing
Un sistema Turing-completo se denomina Turing-equivalente si cada función que puede calcular también es Turing-computable; es decir, calcula exactamente la misma clase de funciones que las máquinas de Turing . Alternativamente, un sistema Turing-equivalente es aquel que puede simular, y ser simulado por, una máquina de Turing universal. (Todos los sistemas Turing-completos físicamente implementables conocidos son Turing-equivalentes, lo que respalda la tesis de Church-Turing ) .
Universalidad (computacional)
Un sistema se considera universal con respecto a una clase de sistemas si puede calcular todas las funciones computables por los sistemas de esa clase (o si puede simular cada uno de esos sistemas). Por lo general, el término «universalidad» se usa tácitamente con respecto a una clase de sistemas Turing-completos. El término «débilmente universal» se usa a veces para distinguir un sistema (por ejemplo, un autómata celular ) cuya universalidad se logra únicamente modificando la definición estándar de máquina de Turing para incluir secuencias de entrada con infinitos unos.

Historia

La completitud de Turing es significativa porque cualquier diseño real de un dispositivo informático puede ser simulado por una máquina de Turing universal . La tesis de Church-Turing afirma que esta es una ley matemática : que una máquina de Turing universal puede, en principio, realizar cualquier cálculo que cualquier otra computadora programable pueda realizar. Esto no dice nada sobre el esfuerzo necesario para escribir el programa , ni el tiempo que la máquina pueda tardar en realizar el cálculo, ni ninguna otra capacidad que la máquina pueda poseer que no tenga que ver con la computación. 

La máquina analítica de Charles Babbage (década de 1830) habría sido la primera máquina Turing-completa si se hubiera construido en la época en que fue diseñada. Babbage reconoció que la máquina era capaz de realizar grandes proezas de cálculo, incluyendo razonamiento lógico primitivo, pero no comprendió que ninguna otra máquina pudiera superarla. Desde la década de 1830 hasta la de 1940, se construyeron y mejoraron máquinas de calcular mecánicas como sumadores y multiplicadores, pero no podían realizar bifurcaciones condicionales y, por lo tanto, no eran Turing-completas.

A finales del siglo XIX, Leopold Kronecker formuló las nociones de computabilidad, definiendo funciones recursivas primitivas . Estas funciones pueden calcularse mediante computación rutinaria, pero no son suficientes para crear una computadora universal, ya que las instrucciones que las calculan no permiten un bucle infinito. A principios del siglo XX, David Hilbert lideró un programa para axiomatizar todas las matemáticas con axiomas precisos y reglas lógicas de deducción precisas que pudieran ser ejecutadas por una máquina. Pronto quedó claro que un pequeño conjunto de reglas de deducción es suficiente para producir las consecuencias de cualquier conjunto de axiomas. Kurt Gödel demostró en 1930 que estas reglas eran suficientes para producir cualquier teorema.

La noción misma de computación se aisló poco después, comenzando con el teorema de incompletitud de Gödel . Este teorema demostró que los sistemas axiomáticos eran limitados al razonar sobre la computación que deduce sus teoremas. Church y Turing demostraron independientemente que el problema de decisión de Hilbert era irresoluble, [ 9 ] identificando así el núcleo computacional del teorema de incompletitud. Este trabajo, junto con el trabajo de Gödel sobre funciones recursivas generales , estableció que existen conjuntos de instrucciones simples que, al combinarse, pueden producir cualquier computación. El trabajo de Gödel demostró que la noción de computación es esencialmente única.

En 1941, Konrad Zuse completó la computadora Z3 . En aquel entonces, Zuse desconocía el trabajo de Turing sobre computabilidad. En particular, la Z3 carecía de funciones específicas para saltos condicionales, lo que le impedía ser Turing completa. Sin embargo, en 1998, Rojas demostró que la Z3 es capaz de simular saltos condicionales y, por lo tanto, es Turing completa en teoría. Para ello, su programa de cinta tendría que ser lo suficientemente largo como para ejecutar todas las rutas posibles a través de ambos lados de cada bifurcación. [ 10 ]

La primera computadora capaz de realizar ramificaciones condicionales en la práctica, y por lo tanto Turing completa en la práctica, fue la ENIAC en 1946. La computadora Z4 de Zuse estuvo operativa en 1945, pero no admitió ramificaciones condicionales hasta 1950. [ 11 ]

teoría de la computabilidad

La teoría de la computabilidad utiliza modelos de computación para analizar problemas y determinar si son computables y bajo qué circunstancias. El primer resultado de esta teoría es que existen problemas para los que es imposible predecir qué hará un sistema (Turing-completo) durante un tiempo arbitrariamente largo.

El ejemplo clásico es el problema de la parada : crear un algoritmo que reciba como entrada un programa escrito en un lenguaje Turing-completo y algunos datos que se le introducirán , y determinar si el programa, al procesar la entrada, se detendrá finalmente o continuará indefinidamente. Es trivial crear un algoritmo que pueda hacer esto para algunas entradas, pero imposible hacerlo en general. Para cualquier característica de la salida final del programa, es imposible determinar si dicha característica se mantendrá.

Esta imposibilidad plantea problemas al analizar programas informáticos reales. Por ejemplo, no se puede crear una herramienta que proteja completamente a los programadores de escribir bucles infinitos ni que impida a los usuarios introducir datos que los provoquen.

En cambio, se puede limitar la ejecución de un programa a un tiempo fijo ( tiempo de espera ) o restringir el poder de las instrucciones de control de flujo (por ejemplo, proporcionando solo bucles que iteren sobre los elementos de un arreglo existente). Sin embargo, otro teorema demuestra que existen problemas resolubles por lenguajes Turing-completos que no pueden ser resueltos por ningún lenguaje con capacidades de bucle finitas (es decir, lenguajes que garantizan que todo programa terminará). Por lo tanto, ningún lenguaje de este tipo es Turing-completo. Por ejemplo, un lenguaje en el que se garantiza que los programas finalicen no puede calcular la función computable producida por el argumento diagonal de Cantor sobre todas las funciones computables en ese lenguaje.

oráculos de Turing

Una computadora con acceso a una cinta de datos infinita puede ser más potente que una máquina de Turing: por ejemplo, la cinta podría contener la solución al problema de la parada o algún otro problema indecidible para una máquina de Turing. Dicha cinta de datos infinita se denomina oráculo de Turing . Incluso un oráculo de Turing con datos aleatorios no es computable ( con probabilidad 1 ), ya que solo existen un número numerable de computaciones, pero un número incontable de oráculos. Por lo tanto, una computadora con un oráculo de Turing aleatorio puede calcular cosas que una máquina de Turing no puede.

Física digital

Todas las leyes conocidas de la física tienen consecuencias que pueden calcularse mediante una serie de aproximaciones en una computadora digital. Una hipótesis llamada física digital afirma que esto no es casualidad, ya que el universo mismo puede calcularse en una máquina de Turing universal. Esto implicaría que no se puede construir físicamente ninguna computadora más potente que una máquina de Turing universal. [ 12 ]

Ejemplos

Los sistemas computacionales (álgebras, cálculos) que se consideran sistemas Turing-completos son aquellos destinados al estudio de la informática teórica . Su objetivo es que sean lo más simples posible, para facilitar la comprensión de los límites de la computación. He aquí algunos ejemplos:

La mayoría de los lenguajes de programación (sus modelos abstractos, quizás omitiendo algunas construcciones particulares que asumen memoria finita), convencionales y no convencionales, son Turing-completos. Esto incluye:

Algunos sistemas de reescritura son Turing-completos.

La completitud de Turing es una afirmación abstracta de capacidad, más que una prescripción de características específicas del lenguaje utilizadas para implementar dicha capacidad. Las características utilizadas para lograr la completitud de Turing pueden ser muy diferentes; los sistemas Fortran usarían construcciones de bucle o posiblemente incluso sentencias goto para lograr la repetición; Haskell y Prolog, que carecen casi por completo de bucles, usarían recursión . La mayoría de los lenguajes de programación describen computaciones en arquitecturas de von Neumann , que poseen memoria (RAM y registros) y una unidad de control. Estos dos elementos hacen que esta arquitectura sea Turing-completa. Incluso los lenguajes puramente funcionales son Turing-completos. [ 15 ] [ 16 ]

La completitud de Turing en SQL declarativo se implementa mediante expresiones recursivas de tablas comunes . Como era de esperar, las extensiones procedimentales de SQL ( PLSQL , etc.) también son Turing-completas. Esto ilustra una de las razones por las que los lenguajes relativamente potentes que no son Turing-completos son poco comunes: cuanto más potente es inicialmente un lenguaje, más complejas son las tareas a las que se aplica y antes se percibe su falta de completitud como una desventaja, lo que fomenta su extensión hasta que sea Turing-completo.

El cálculo lambda sin tipos es Turing-completo, pero muchos cálculos lambda con tipos, incluido el Sistema F , no lo son. El valor de los sistemas con tipos radica en su capacidad para representar la mayoría de los programas informáticos típicos, a la vez que detectan más errores.

La regla 110 y el juego de la vida de Conway , ambos autómatas celulares , son Turing-completos.

Completitud de Turing no intencional

Algunos programas informáticos y videojuegos son Turing-completos por accidente, es decir, no por diseño.

Software:

Juegos:

Redes sociales:

Lenguajes computacionales:

Biología:

Sistemas físicos:

Lenguajes no Turing-completos

Existen muchos lenguajes computacionales que no son Turing-completos. Un ejemplo de ello son los lenguajes regulares , generados mediante expresiones regulares y reconocidos por autómatas finitos . Una extensión más potente, aunque aún no Turing-completa, de los autómatas finitos es la categoría de autómatas de pila y gramáticas libres de contexto , que se utilizan habitualmente para generar árboles de análisis sintáctico en la fase inicial de la compilación de programas . Otros ejemplos incluyen algunas de las primeras versiones de los lenguajes de sombreado de píxeles integrados en las extensiones de Direct3D y OpenGL .

En los lenguajes de programación totalmente funcionales , como Charity y Epigram , todas las funciones son totales y deben terminar. Charity utiliza un sistema de tipos y construcciones de control basadas en la teoría de categorías , mientras que Epigram utiliza tipos dependientes . El lenguaje LOOP está diseñado para calcular únicamente las funciones recursivas primitivas . Todos estos lenguajes calculan subconjuntos propios de las funciones computables totales, ya que el conjunto completo de funciones computables totales no es enumerable computacionalmente . Además, dado que todas las funciones en estos lenguajes son totales, no se pueden escribir algoritmos para conjuntos recursivamente enumerables en ellos, a diferencia de las máquinas de Turing.

Si bien el cálculo lambda (sin tipos) es Turing-completo, el cálculo lambda simplemente tipado no lo es.

Véase también

Notas a pie de página

  1. ↑ Podría decirse que la computación completa (TC) es el único paradigma para la teoría que sustenta la informática... Se ha argumentado que, en la actualidad, el paradigma dominante de la informática puede caracterizarse teóricamente como computación completa (TC), que abarca los lenguajes de programación, y prácticamente como pensamiento computacional (TC), que abarca las metodologías de programación. [ 3 ]

Referencias

  1. ↑ Stuart, Tom (2013). "7. La universalidad está en todas partes §Cálculo Lambda" . Comprender la computación: de las máquinas simples a los programas imposibles . O'Reilly Media. pág.  209. ISBN 978-1-4493-3011-8En otras palabras , RUN es un programa de cálculo lambda que puede simular cualquier máquina de Turing.
  2. ↑ Calude, Cristian S. (2024). "§1.14 Lenguajes de programación con problema de parada decidible" . ¿Detenerse o no detenerse? Esa es la cuestión . World Scientific. pág. 30. ISBN  978-981-12-3229-9Los programas en pseudocódigo poseen una propiedad poderosa: la completitud o universalidad de Turing. Un lenguaje de programación se denomina Turing completo o computacionalmente universal si puede simular cualquier máquina de Turing.
  3. ↑ Michaelson, Greg (14 de febrero de 2020). "Paradigmas de programación, completitud de Turing y pensamiento computacional". El arte, la ciencia y la ingeniería de la programación . 4 (3) 4. arXiv : 2002.06178 . doi : 10.22152/programming-journal.org/2020/4/4 .
  4. ↑ Üçoluk, Göktürk; Kalkan, Sinan (2012). "§1.3.1 Cómo elegir un lenguaje de programación para una implementación" . Introducción a los conceptos de programación con estudios de caso en Python . Springer. pág. 13. ISBN  978-3-7091-1343-1Todos los paradigmas, todos los lenguajes de programación e incluso todas las CPU son equivalentes. Esto se conoce como la equivalencia de Turing .
  5. ↑ Goertzel, Ben (2013). «§1.1 Computación estocástica y cuántica» . La estructura de la inteligencia: un nuevo modelo matemático de la mente . Springer. pág. 13. ISBN  978-1-4612-4336-6Hemos visto que una máquina de Turing universal puede seguir cualquier conjunto preciso de instrucciones, al menos en el sentido de que puede simular cualquier otra computadora .
  6. ↑ Garnham, Alan (2017). «8. Cuestiones conceptuales §1. El ordenador como modelo de la mente: la tesis de Turing» . Inteligencia artificial: una introducción . Routledge. pág. 164. ISBN  978-1-351-33786-1La máquina de Turing universal puede imitar el funcionamiento de cualquier otra máquina de Turing .
  7. ↑ Mogensen, Torben Ægidius (2022). «Prefacio §¿Necesitamos nuevos lenguajes de programación?» . Diseño e implementación de lenguajes de programación . Springer Nature. pág. 6. ISBN  978-3-031-11806-7.
  8. ↑ Woodward, John R. (2003). «Modularidad en la programación genética» . En Ryan, Conor (ed.). Programación genética: 6.ª Conferencia Europea, EuroGP 2003, Essex, Reino Unido, 14-16 de abril de 2003. Springer. p. 258. doi : 10.1007/3-540-36599-0_23 . ISBN  978-3-540-00971-9.
  9. ↑ Hodges, Andrew (1992) [1983], Alan Turing: El enigma , Londres: Burnett Books, pág. 111, ISBN  0-04-510060-8
  10. ↑ Rojas, Raul (1998). "Cómo convertir el Z3 de Zuse en una computadora universal" . Annals of the History of Computing . 20 (3): 51– 54. Bibcode : 1998IAHC...20c..51R . doi : 10.1109/85.707574 .
  11. ↑ Rojas, Raúl (1 de febrero de 2014). "Konrad Zuse und der bedingte Sprung" [ Konrad Zuse y el salto condicional ] . Informatik-Spektrum (en alemán). 37 (1): 50– 53. doi : 10.1007/s00287-013-0717-9 . ISSN 0170-6012 . S2CID 1086397 .  
  12. ↑ Schmidhuber, Jürgen (1997), "La visión de un científico informático sobre la vida, el universo y todo lo demás", en Freksa, Christian; Jantzen, Matthias; Valk, Rüdiger (eds.), Fundamentos de la informática: Potencial — Teoría — Cognición , Lecture Notes in Computer Science, vol. 1337, Springer, pp. 201–208 , arXiv : quant-ph/9904050 , doi : 10.1007/bfb0052088 , ISBN   978-3-540-69640-7, S2CID 17830241 
  13. ↑ Dfetter; Breinbaas (8 de agosto de 2011). "Sistema de etiquetas cíclicas" . Wiki de PostgreSQL . Consultado el 10 de septiembre de 2014 .
  14. ↑ Lyons, Bob (30 de marzo de 2001). "Máquina de Turing universal en XSLT" . Soluciones de integración B2B de Unidex . Archivado del original el 17 de julio de 2011. Recuperado el 5 de julio de 2010 .
  15. ↑ Boyer, Robert S.; Moore, J. Strother (mayo de 1983). Una prueba mecánica de la completitud de Turing de Pure Lisp (PDF) (Informe técnico). Instituto de Ciencias de la Computación, Universidad de Texas en Austin. 37. Archivado (PDF) del original el 22 de septiembre de 2017.
  16. ↑ Rauber, Thomas; Rünger, Gudula (2013). Programación paralela: para sistemas multinúcleo y en clúster (2.ª ed.). Springer. ISBN  978-3-642-37801-0.
  17. ↑ "Presentamos LAMBDA: Convierte fórmulas de Excel en funciones personalizadas" . TECHCOMMUNITY.MICROSOFT.COM . 3 de diciembre de 2020. Consultado el 8 de diciembre de 2020 .
  18. ↑ "Jira es Turing-completo" . seriot.ch . Consultado el 23 de mayo de 2026 .
  19. ↑ J. Su, Caleb. "Un nuevo enfoque de la completitud de Turing en Baba is You" (PDF) .
  20. ↑ Cedotal, Andrew (16 de abril de 2010). "Un hombre utiliza el videojuego más difícil del mundo para crear... una máquina de Turing funcional" . The Mary Sue . Archivado del original el 27 de junio de 2015. Consultado el 2 de junio de 2015 .
  21. ↑ Plunkett, Luke (16 de julio de 2019). "Cities: Skylines Map Becomes A Poop-Powered Computer" . Kotaku . Consultado el 16 de julio de 2019 .
  22. ↑ Caldwell, Brendan (20 de noviembre de 2017). "Un jugador de Opus Magnum crea una computadora alquímica" . Rock Paper Shotgun . Recuperado el 23 de septiembre de 2019 .
  23. ↑ Churchill, Alex; Biderman, Stella; Herrick, Austin (2020). Magic: The Gathering es Turing completo (PDF) . 10.ª Conferencia Internacional sobre Diversión con Algoritmos. Archivado del original (PDF) el 23 de septiembre de 2025.
  24. ↑ Ouellette, Jennifer (23 de junio de 2019). "Es posible construir una máquina de Turing dentro de Magic: The Gathering" . Ars Technica . Consultado el 12 de marzo de 2023 .
  25. ↑ "Completitud de Turing" . www.cs.odu.edu . Consultado el 11 de mayo de 2026 .
  26. ↑ Kaye, Richard (31 de mayo de 2007). "Las versiones infinitas del Buscaminas son Turing completas" (PDF) . Archivado del original (PDF) el 3 de agosto de 2016. Recuperado el 8 de julio de 2016 .
  27. ↑ De Wynter, Adrian (2023). "Completitud de Turing y la civilización de Sid Meier" . IEEE Transactions on Games . 15 (2). IEEE: 292–9 . Bibcode : 2023ITGam..15..292D . doi : 10.1109/TG.2022.3166874 .
  28. ↑ "Hilo de Twitter de Habbo sobre la implementación de una máquina de Turing dentro del juego" . 9 de noviembre de 2020. Consultado el 11 de noviembre de 2020 .
  29. ↑ Meyers, Scott (Scott Douglas) (2005). Effective C++: 55 specific ways to improve your programs and designs (3.ª ed.). Upper Saddle River, NJ: Addison-Wesley. ISBN  0-321-33487-6OCLC 60425273​​ 
  30. ↑ Ganador del 27.º IOCCC Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (agosto de 2015). «Control-flow bending: on the effectiveness of control-flow integrity» . Actas del 24.º Simposio de la Conferencia USENIX sobre Seguridad . págs. 161-176 . ISBN  978-1-931971-23-2.
  31. ↑ Dabler, Ryan (23 de septiembre de 2021). "TypeScript y la completitud de Turing" . ITNEXT . LINKIT . Consultado el 12 de noviembre de 2022 .
  32. ↑ Dolan, Stephen. "mov es Turing-completo" (PDF) . stedolan.net . Archivado del original (PDF) el 14 de febrero de 2021. Consultado el 9 de mayo de 2019 .
  33. ↑ Williams, Al (21 de marzo de 2021). "Una instrucción para gobernarlas a todas: el compilador de C emite solo MOV" . Hackaday . Recuperado el 23 de octubre de 2023 .
  34. ↑ Break Me00 The MoVfuscator Convirtiendo mov en una pesadilla de RE que te destroza el alma Christopher Domas , 25 de septiembre de 2015 , consultado el 5 de noviembre de 2022
  35. ↑ Litherum (7 de marzo de 2019). "Litherum: Fuente adicional" . Litherum . Consultado el 23 de mayo de 2026 .
  36. ↑ "Las reglas de transliteración de Unicode son Turing-completas" . seriot.ch . Consultado el 8 de julio de 2026 .
  37. ↑ Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin ; Chen, Yuan-Jyue; Reif, John (4 de mayo de 2020). "Uso de la polimerasa con desplazamiento de hebras para programar redes de reacciones químicas". Journal of the American Chemical Society . 142 (21): 9587– 93. doi : 10.1021/jacs.0c02240 . ISSN 0002-7863 . PMID 32364723. S2CID 218504535 .   
  38. ↑ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (octubre de 2013). "Controladores químicos programables hechos de ADN" . Nature Nanotechnology . 8 (10): 755– 762. Bibcode : 2013NatNa...8..755C . doi : 10.1038 / nnano.2013.189 . PMC 4150546. PMID 24077029 .  
  39. ↑ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 de diciembre de 2017). "Sistemas dinámicos de ácidos nucleicos sin enzimas" . Science . 358 (6369) eaal2052. doi : 10.1126/science.aal2052 . ISSN 0036-8075 . PMID 29242317 .  
  40. ↑ Soloveichik, David; Seelig, Georg; Winfree, Erik (23 de marzo de 2010). "El ADN como sustrato universal para la cinética química" . Actas de la Academia Nacional de Ciencias . 107 (12): 5393–8 . Bibcode : 2010PNAS..107.5393S . doi : 10.1073/pnas.0909380107 . PMC 2851759. PMID 20203007 .  
  41. ↑ Shapiro, Ehud (7 de diciembre de 1999). " Una máquina de Turing mecánica: plano para una computadora biomolecular" . Interface Focus . 2 (4). Instituto Weizmann de Ciencias : 497–503 . doi : 10.1098/rsfs.2011.0118 . PMC 3363030. PMID 22649583 .  
  42. ↑ Miranda, Eva; Ramos, Isaac (27 de diciembre de 2025). "El billar clásico puede calcular". arXiv : 2512.19156 [ math.DS ].

Lecturas adicionales

  • Brainerd, WS; Landweber, LH (1974). Teoría de la computación . Wiley. ISBN 0-471-09585-0OCLC 694056​​ 
  • Giles, Jim (24 de octubre de 2007). "La 'computadora universal' más sencilla le hace ganar a un estudiante 25.000 dólares" . New Scientist .
  • Herken, Rolf, ed. (1995). La máquina de Turing universal: un estudio de medio siglo (PDF) . Springer. ISBN 3-211-82637-8OCLC 32013506​​ 
  • Turing, AM (1936). "Sobre los números computables, con una aplicación al problema de decisión" . Actas de la Sociedad Matemática de Londres . 2. 42 : 230–265 . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . 
  • Turing, AM (1938). "Sobre los números computables, con una aplicación al problema de decisión: una corrección". Actas de la Sociedad Matemática de Londres . 2. 43 : 544–6 . doi : 10.1112/plms/s2-43.6.544 .
  • "Turing completo" . wiki.c2.com .