Completitud de Turing

Capacidad de un sistema informático para simular máquinas de Turing

Para conocer el uso de este término en la teoría de la computabilidad relativa de las máquinas oráculo, consulte la reducción de Turing .

En la teoría de la computabilidad , se dice que un sistema de reglas de manipulación de datos (como el 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 . Esto significa que este sistema puede reconocer o decidir otros conjuntos de reglas de manipulación de datos. La completitud de Turing se utiliza como una forma de expresar el poder de un conjunto de reglas de manipulación de datos de este tipo. Prácticamente todos los lenguajes de programación actuales son Turing completos. El concepto lleva el nombre del matemático e informático inglés Alan Turing .

Un concepto relacionado es el de la equivalencia de Turing  : dos computadoras P y Q se llaman equivalentes si P puede simular Q y Q puede simular P. La tesis de Church-Turing conjetura que cualquier función cuyos valores puedan ser calculados por un algoritmo puede ser calculada por un Turing, y por lo tanto, si cualquier computadora del mundo real puede simular una máquina de Turing, es Turing equivalente a una máquina de Turing. Se puede usar una máquina de Turing universal para simular cualquier máquina de Turing y, por extensión, los aspectos computacionales de cualquier computadora del mundo real posible. ^{[NB 1]}

Para demostrar que algo es Turing completo, basta con mostrar que se puede usar para simular algún sistema Turing completo. Por ejemplo, un lenguaje imperativo es Turing-completo si tiene bifurcaciones condicionales (por ejemplo, declaraciones "if" y "goto", o una instrucción "branch if zero"; ver computadora con un conjunto de instrucciones ) y la capacidad de cambiar una instrucción arbitraria cantidad de memoria (por ejemplo, la capacidad de mantener un número arbitrario de elementos de datos). Por supuesto, ningún sistema físico puede tener una memoria infinita; pero si se ignora la limitación de la memoria finita, la mayoría de los lenguajes de programación son por lo demás Turing-completos.

Uso no matemático

En el uso coloquial , los términos "Turing-completo" y "Turing-equivalente" se utilizan para significar que cualquier computadora de propósito general del mundo real o lenguaje de computadora puede simular aproximadamente los aspectos computacionales de cualquier otra computadora de propósito general del mundo real o lenguaje de ordenador.

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

Definiciones formales

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

Completitud de Turing

Un sistema computacional que puede calcular todas las funciones computables de Turing se llama Turing-completo (o Turing-poderoso). Alternativamente, tal sistema es uno que puede simular una máquina de Turing universal .

Equivalencia de Turing

Un sistema completo de Turing se denomina equivalente de Turing si cada función que puede calcular es también computable por Turing; es decir, calcula precisamente la misma clase de funciones que las máquinas de Turing . Alternativamente, un sistema equivalente de Turing es uno que puede simular y ser simulado por una máquina de Turing universal. (Todos los sistemas Turing completos que se pueden implementar físicamente son equivalentes a Turing, lo que agrega apoyo a la tesis de Church-Turing . ^{[ Cita requerida ]} )

Universalidad (computacional)

Un sistema se denomina universal con respecto a una clase de sistemas si puede calcular todas las funciones computables por los sistemas de esa clase (o puede simular cada uno de esos sistemas). Típicamente, el término universalidad se usa tácitamente con respecto a una clase de sistemas completa de Turing. El término "débilmente universal" se usa a veces para distinguir un sistema (por ejemplo, un autómata celular ) cuya universalidad se logra solo modificando la definición estándar de máquina de Turing para incluir flujos de entrada con infinitos unos.

Historia

La completitud de Turing es significativa porque cada diseño del mundo real para 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 de las matemáticas: que una máquina universal de Turing 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 , o el tiempo que puede tomar la máquina para realizar el cálculo, o cualquier habilidad que la máquina pueda poseer que no tenga nada que ver con la computación.

El motor analítico de Charles Babbage (década de 1830) habría sido la primera máquina completa de Turing si se hubiera construido en el momento en que se diseñó. Babbage apreciaba que la máquina fuera capaz de realizar grandes hazañas de cálculo, incluido el razonamiento lógico primitivo, pero no apreciaba que ninguna otra máquina pudiera hacerlo mejor. Desde la década de 1830 hasta la de 1940, se construyeron y mejoraron máquinas calculadoras mecánicas como sumadores y multiplicadores, pero no podían realizar una rama condicional y, por lo tanto, no eran Turing completas.

A finales del siglo XIX, Leopold Kronecker formuló nociones de computabilidad, definiendo funciones recursivas primitivas . Estas funciones se pueden calcular mediante el cálculo de memoria, pero no son suficientes para hacer una computadora universal, porque las instrucciones que las calculan no permiten un bucle infinito. A principios del siglo XX, David Hilbert dirigió un programa para axiomatizar todas las matemáticas con axiomas precisos y reglas lógicas de deducción precisas que podrían ser realizadas por una máquina. Pronto quedó claro que un pequeño conjunto de reglas de deducción son suficientes para producir las consecuencias de cualquier conjunto de axiomas. Kurt Gödel demostró en 1930 que estas reglas eran suficientes para producir todos los teoremas.

La noción real de computación se aisló poco después, comenzando con el teorema de incompletitud de Gödel . Este teorema mostró que los sistemas de axiomas eran limitados al razonar sobre el cálculo que deduce sus teoremas. Church y Turing demostraron de forma independiente que el problema de decisión ( Entscheidungsproblem) de Hilbert no tenía solución, ^[1] 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, cuando se juntan, son capaces de producir cualquier cálculo. El trabajo de Gödel mostró que la noción de computación es esencialmente única.

En 1941 Konrad Zuse completó la computadora Z3 . Zuse no estaba familiarizado con el trabajo de Turing sobre computabilidad en ese momento. En particular, el Z3 carecía de instalaciones dedicadas para un salto condicional, lo que le impedía ser Turing completo. Sin embargo, en 1998, Rojas demostró que el Z3 es capaz de realizar saltos condicionales y, por lo tanto, Turing completo, al utilizar algunas de sus características de manera no intencionada. ^[2]

Teoría de la computabilidad

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

El ejemplo clásico es el problema de la detención : crear un algoritmo que tome como entrada un programa en algún lenguaje Turing completo y algunos datos para ser alimentados a ese programa, y ​​determine si el programa, operando en la entrada, eventualmente se detendrá o continuará. para siempre. Es trivial crear un algoritmo que pueda hacer esto para algunas entradas, pero es imposible hacerlo en general. Para cualquier característica de la salida final del programa, es imposible determinar si esta característica se mantendrá.

Esta imposibilidad plantea problemas al analizar programas informáticos del mundo real. Por ejemplo, no se puede escribir una herramienta que proteja por completo a los programadores de escribir bucles infinitos o que proteja a los usuarios de suministrar entradas que causarían bucles infinitos.

En su lugar, se puede limitar un programa para que se ejecute solo durante un período de tiempo fijo ( tiempo de espera ) o limitar el poder de las instrucciones de control de flujo (por ejemplo, proporcionar solo bucles que iteran sobre los elementos de una matriz existente). Sin embargo, otro teorema muestra que hay problemas que se pueden resolver con lenguajes completos de Turing que no pueden ser resueltos por ningún lenguaje con solo habilidades de bucle finito (es decir, cualquier lenguaje que garantice que cada programa eventualmente terminará en un punto muerto). Entonces, tal lenguaje no es Turing completo. Por ejemplo, un lenguaje en el que los programas están garantizados para completarse y detenerse no puede calcular la función computable producida por el argumento diagonal de Cantor en todas las funciones computables en ese lenguaje.

Oráculos de turing

Artículo principal: máquina Oracle

Una computadora con acceso a una cinta infinita de datos puede ser más poderosa que una máquina de Turing: por ejemplo, la cinta puede contener la solución al problema de la detención o algún otro problema indecidible de Turing. Una cinta de datos tan infinita se llama oráculo de Turing . Incluso un oráculo de Turing con datos aleatorios no es computable ( con probabilidad 1 ), ya que solo hay innumerables cálculos pero incontables oráculos. Entonces, una computadora con un oráculo de Turing aleatorio puede calcular cosas que una máquina de Turing no puede.

Física digital

Ver también: Tesis de Church-Turing § Implicaciones filosóficas

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado . ( Noviembre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Todas las leyes físicas conocidas tienen consecuencias que se pueden calcular mediante una serie de aproximaciones en una computadora digital. Una hipótesis llamada física digital establece que esto no es un accidente porque el universo mismo es computable en una máquina de Turing universal. Esto implicaría que ninguna computadora más poderosa que una máquina universal de Turing puede construirse físicamente.

Ejemplos de

Los sistemas computacionales (álgebras, cálculos) que se discuten como sistemas completos de Turing son aquellos destinados al estudio de la informática teórica . Están pensados ​​para ser lo más simples posible, para que sea más fácil comprender los límites de la computación. A continuación, presentamos algunos:

• Teoría de los autómatas
• Gramática formal (generadores de lenguaje)
• Lenguaje formal (reconocedores de lenguaje)
• Cálculo lambda
• Máquinas de post-Turing
• Cálculo de procesos

La mayoría de los lenguajes de programación (sus modelos abstractos, tal vez con algunas construcciones particulares que suponen que se omite la memoria finita), convencionales y no convencionales, son Turing-completos. Esto incluye:

• Todos los lenguajes de uso general en uso generalizado.
  • Lenguajes de programación procedimental como C , Pascal .
  • Lenguajes orientados a objetos como Java , Smalltalk o C # .
  • Multi-paradigma lenguajes como Ada , C ++ , Common Lisp , Fortran , JavaScript , Object Pascal , Perl , Python , R .
• La mayoría de los lenguajes que utilizan paradigmas menos comunes:
  • Lenguajes funcionales como Lisp y Haskell .
  • Lenguajes de programación lógica como Prolog .
  • Procesador de macros de uso general como m4 .
  • Lenguajes declarativos como XSLT . ^[3]
  • VHDL y otros lenguajes de descripción de hardware.
  • TeX , un sistema de composición tipográfica.
  • Lenguajes de programación esotéricos , una forma de recreación matemática en la que los programadores descubren cómo lograr construcciones básicas de programación en un lenguaje extremadamente difícil pero matemáticamente equivalente a Turing.

Algunos sistemas de reescritura son Turing completos.

La completitud de Turing es una declaración abstracta de capacidad, más que una prescripción de características específicas del lenguaje utilizadas para implementar esa capacidad. Las características utilizadas para lograr la completitud de Turing pueden ser bastante diferentes; Los sistemas Fortran usarían construcciones de bucle o posiblemente incluso declaraciones goto para lograr la repetición; Haskell y Prolog, que carecen de bucles casi por completo, usarían la recursividad . La mayoría de los lenguajes de programación describen cálculos en arquitecturas de von Neumann , que tienen memoria (RAM y registro) y una unidad de control. Estos dos elementos hacen que esta arquitectura Turing sea completa. Incluso los lenguajes funcionales puros son Turing completos. ^{[4] [NB 2]}

La completitud de Turing en SQL declarativo se implementa mediante expresiones de tabla comunes recursivas . ^[5] Como era de esperar, las extensiones de procedimiento de SQL ( PLSQL , etc.) también son Turing-complete. Esto ilustra una razón por la cual los lenguajes no completos de Turing relativamente poderosos son raros: cuanto más poderoso es el lenguaje inicialmente, más complejas son las tareas a las que se aplica y más pronto su falta de completitud se percibe como un inconveniente, lo que fomenta su desarrollo. extensión hasta que sea Turing-completo.

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

Rule 110 y Game of Life de Conway , ambos autómatas celulares , son Turing completos.

Completitud involuntaria de Turing

Algunos juegos y otro software se completan con Turing por accidente, es decir, no por diseño.

Software:

• Microsoft Excel ^[6]
• Microsoft PowerPoint ^[7]

Juegos de vídeo:

• Fortaleza enana ^[8]
• OpenTTD ^{[ cita requerida ]}
• Terraria ^{[ cita requerida ]}
• Minecraft ^{[9] [ fuente autoeditada ]}
• Buscaminas ^[10]
• LittleBigPlanet ^[9]
• Baba eres tú ^{[11] [12]}
• Factorio ^[13]
• Ciudades: Horizontes ^[14]
• Opus Magnum ^[15]
• Portal 2 ^{[16] [ fuente autoeditada ]}
• Tablero de geometría ^[17]

Medios de comunicación social:

• Habbo Hotel ^[18]

Juegos de cartas:

• Magic: The Gathering ^{[9] [19]}

Juegos de cero personas (simulaciones):

• El juego de la vida de Conway ^{[20] [21]}

Lenguajes computacionales:

• Plantillas C ++ ^{[22] [23]}

Hardware de la computadora:

• Instrucción MOV x86 ^[24]

Biología:

• Se ha demostrado que las redes de reacción química ^{[25] [26] [27] [28]} y las computadoras de ADN basadas en enzimas ^[29] son equivalentes a Turing

Idiomas no completos de Turing

Existen muchos lenguajes computacionales que no son Turing completos. Un ejemplo es el conjunto de lenguajes regulares , que son generados por expresiones regulares y que son reconocidos por autómatas finitos . Una extensión más poderosa, pero aún no completa de Turing, de los autómatas finitos es la categoría de autómatas pushdown y gramáticas libres de contexto , que se utilizan comúnmente para generar árboles de análisis sintáctico en una etapa inicial de compilación de programas . Otros ejemplos incluyen algunas de las primeras versiones de los lenguajes de sombreado de píxeles incrustados en las extensiones Direct3D y OpenGL . ^{[ cita requerida ]}

En los lenguajes de programación funcional total , como Charity y Epigram , todas las funciones son totales y deben finalizar. Charity usa un sistema de tipos y constructos de control basados ​​en la teoría de categorías , mientras que Epigram usa tipos dependientes . El lenguaje LOOP está diseñado para que solo calcule las funciones que son recursivas primitivas . Todos estos calculan subconjuntos adecuados de las funciones computables totales, ya que el conjunto completo de funciones computables totales no es computablemente enumerable . Además, dado que todas las funciones en estos lenguajes son totales, los algoritmos para conjuntos enumerables recursivamente no se puede escribir en estos lenguajes, a diferencia de las máquinas de Turing.

Aunque el cálculo lambda (sin tipo) es Turing completo, el cálculo lambda simplemente tipado no lo es.

Idiomas de datos

La noción de completitud de Turing no se aplica a lenguajes como XML , HTML , JSON y YAML , porque generalmente se usan para representar datos estructurados, no para describir computación. A veces se los denomina lenguajes de marcado o, más propiamente, "lenguajes contenedores" o "lenguajes de descripción de datos". ^{[ cita requerida ]}

Ver también

• Integridad de la IA
• Teoría algorítmica de la información
• Jerarquía de Chomsky
• Tesis de Church-Turing
• Teoría de la computabilidad
• Bucle interior
• Bucle (informática)
• Máquina que siempre se detiene
• Teorema de Rice
• teorema de s mn
• Teorema del programa estructurado
• Tarpito de Turing

Notas

1. A UTM no puede aspectos Simular no computacionales tales como I / O .
2. El siguiente libro proporciona una introducción a los modelos de cálculo: Rauber, Thomas; Rünger, Gudula (2013). Programación paralela: para sistemas multinúcleo y cluster (2ª ed.). Saltador. ISBN 9783642378010.

Referencias

1. Hodges, Andrew (1992) [1983], Alan Turing: The Enigma , Londres: Burnett Books, p. 111, ISBN 0-04-510060-8
2. Rojas, Raúl (1998). "Cómo hacer que Zuse's Z3 sea una computadora universal" . Anales de la historia de la informática . 20 (3): 51–54. doi : 10.1109 / 85.707574 .
3. Lyons, Bob (30 de marzo de 2001). "Máquina universal de Turing en XSLT" . Soluciones de integración B2B de Unidex . Archivado desde el original el 17 de julio de 2011 . Consultado el 5 de julio de 2010 .
4. Boyer, Robert S .; Moore, J. Strother (mayo de 1983). Una prueba mecánica de la integridad de Turing de Pure Lisp (PDF) (Informe técnico). Instituto de Ciencias de la Computación, Universidad de Texas en Austin. 37. Archivado (PDF) desde el original el 22 de septiembre de 2017.
5. Dfetter; Breinbaas (8 de agosto de 2011). "Sistema de etiquetas cíclicas" . Wiki de PostgreSQL . Consultado el 10 de septiembre de 2014 .
6. "Anuncio de LAMBDA: convertir fórmulas de Excel en funciones personalizadas" . TECHCOMMUNITY.MICROSOFT.COM . 3 de diciembre de 2020 . Consultado el 8 de diciembre de 2020 .
7. Wildenhain, Tom (9 de abril de 2020). "Sobre la integridad de Turing de MS PowerPoint" (PDF) . ^{[ fuente autoeditada ]}
8. Cedotal, Andrew (16 de abril de 2010). "El hombre usa el juego de computadora más difícil del mundo para crear ... una máquina de Turing que funciona" . El Mary Sue . Archivado desde el original el 27 de junio de 2015 . Consultado el 2 de junio de 2015 .
9. Zwinkau, Andreas (20 de octubre de 2013). "Accidentalmente Turing-Complete" . Andreas Zwinkau . Archivado desde el original el 5 de junio de 2015 . Consultado el 2 de junio de 2015 .^{[ fuente autoeditada ]}
10. Kaye, Richard (31 de mayo de 2007). "Las versiones infinitas del buscaminas están completadas por Turing" (PDF) . Páginas del Buscaminas de Richard Kaye . Archivado (PDF) desde el original el 2 de febrero de 2017 . Consultado el 14 de marzo de 2017 . ^{[ fuente autoeditada ]}
11. "BABA SE ESTÁ ENTRANDO COMPLETO: Un boceto de una prueba (v2)" . 25 de marzo de 2019 . Consultado el 2 de junio de 2020 .
12. "Tweet de Matthew Rodríguez (@ mattar0d) de un video que muestra una implementación de la Regla 110 del Autómata Celular en Baba Is You" . 25 de marzo de 2019 . Consultado el 2 de junio de 2020 .
13. "Hice una computadora programable Turing-complete en Factorio" . Reddit . 31 de enero de 2016 . Consultado el 2 de febrero de 2020 .
14. Plunkett, Luke (16 de julio de 2019). "Ciudades: mapa de Skylines se convierte en una computadora impulsada por caca" . Kotaku . Consultado el 16 de julio de 2019 .
15. Caldwell, Brendan (20 de noviembre de 2017). "El jugador del Opus Magnum hace una computadora alquímica" . Escopeta de papel de piedra . Consultado el 23 de septiembre de 2019 .
16. Tatum, Alexander (16 de julio de 2019). "Calculadora binaria de 3 dígitos" . Vapor . Consultado el 1 de julio de 2019 .
17. cosas que la gente hizo con mi lenguaje de programación GD , recuperado el 18 de octubre de 2021
18. "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 .
19. Alex Churchill; Stella Biderman; Austin Herrick (2019). "Magic: The Gathering es Turing completo". arXiv : 1904.09828 [ cs.AI ].
20. Rendell, Paul (12 de enero de 2005). "Una máquina de Turing en el juego de la vida de Conway" . Rendell-Attic . Archivado desde el original el 8 de julio de 2009 . Consultado el 22 de junio de 2009 .^{[ fuente autoeditada ]}
21. Calcyman; Johnston, Nathaniel (16 de junio de 2009). "Constructor de computadoras universal espartano" . LifeWiki . Consultado el 22 de junio de 2009 .
22. Meyers, Scott (Scott Douglas) (2005). C ++ efectivo: 55 formas específicas de mejorar sus programas y diseños (3ª ed.). Upper Saddle River, Nueva Jersey: Addison-Wesley. ISBN 0321334876. OCLC  60425273 .
23. Ver Historia de TMP en Wikilibros.
24. Dolan, Stephen. "mov es Turing-completo" (PDF) . stedolan.net . Consultado el 9 de mayo de 2019 .
25. Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (4 de mayo de 2020). "Uso de polimerasa de desplazamiento de hebra para programar redes de reacción química". Revista de la Sociedad Química Estadounidense . 142 (21): 9587–9593. doi : 10.1021 / jacs.0c02240 . ISSN 0002-7863 . PMID 32364723 .  
26. 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" . Nanotecnología de la naturaleza . 8 (10): 755–762. Código bibliográfico : 2013NatNa ... 8..755C . doi : 10.1038 / nnano.2013.189 . ISSN 1748-3395 . PMC 4150546 . PMID 24077029 .   
27. Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 de diciembre de 2017). "Sistemas dinámicos de ácidos nucleicos sin enzimas" . Ciencia . 358 (6369): eaal2052. doi : 10.1126 / science.aal2052 . ISSN 0036-8075 . PMID 29242317 .  
28. 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–5398. Código bibliográfico : 2010PNAS..107.5393S . doi : 10.1073 / pnas.0909380107 . ISSN 0027-8424 . PMC 2851759 . PMID 20203007 .   
29. Shapiro, Ehud (7 de diciembre de 1999). "Una máquina de Turing mecánica: modelo para una computadora biomolecular" . Enfoque de interfaz . Instituto de Ciencias Weizmann . 2 (4): 497–503. doi : 10.1098 / rsfs.2011.0118 . PMC 3363030 . PMID 22649583 . Archivado desde el original el 3 de enero de 2009 . Consultado el 13 de agosto de 2009 .  

Otras lecturas

• Brainerd, WS; Landweber, LH (1974). Teoría de la Computación . Wiley. ISBN 0-471-09585-0.
• Giles, Jim (24 de octubre de 2007). "La 'computadora universal' más simple gana $ 25,000 para estudiantes" . Nuevo científico .
• Herken, Rolf, ed. (1995). La máquina universal de Turing: una encuesta de medio siglo . Springer Verlag. ISBN 3-211-82637-8.
• Turing, AM (1936). "Sobre números computables, con una aplicación al Entscheidungsproblem" (PDF) . Actas de la London Mathematical Society . 2. 42 : 230-265. doi : 10.1112 / plms / s2-42.1.230 .
• Turing, AM (1938). "En números computables, con una aplicación al Entscheidungsproblem: una corrección". Actas de la London Mathematical Society . 2. 43 : 544–546. doi : 10.1112 / plms / s2-43.6.544 .

enlaces externos

• "Turing completo" . wiki.c2.com .