¿Qué es Turing completo?

Respuestas:

325

Aquí está la explicación más breve:

Un sistema Turing Complete significa un sistema en el que se puede escribir un programa que encontrará una respuesta (aunque sin garantías con respecto al tiempo de ejecución o la memoria).

Entonces, si alguien dice "lo nuevo de Turing es completo", eso significa en principio (aunque a menudo no en la práctica) que podría usarse para resolver cualquier problema de cálculo.

A veces es una broma ... un tipo escribió un simulador de Turing Machine en vi, por lo que es posible decir que vi es el único motor computacional que se necesita en el mundo.

Mark Harrison
fuente
18
Para leer más, ver The Annotated Turing. Muy accesible amazon.com/Annotated-Turing-Through-Historic-Computability/dp/…
i_am_jorf
43
"a menudo no en la práctica" es incorrecto. Ningún sistema es Turing completo en la práctica, porque ningún sistema realizable tiene una cinta infinita. Lo que realmente queremos decir es que algunos sistemas tienen la capacidad de aproximar la integridad de Turing hasta los límites de su memoria disponible.
Shelby Moore III
22
Pero Vi es el único motor computacional que se necesita en el mundo ... ;-)
Joe Edgar
44
¿Emacs también es una máquina de tornear? XD
alem0lars
66
Recientemente, alguien demostró que PowerPoint también está Turing completo.
Tagc
193

Aquí está la explicación más simple.

Alan Turing creó una máquina que puede tomar un programa, ejecutar ese programa y mostrar algún resultado. Pero luego tuvo que crear diferentes máquinas para diferentes programas. Entonces creó "Universal Turing Machine" que puede tomar CUALQUIER programa y ejecutarlo.

Los lenguajes de programación son similares a esas máquinas (aunque virtuales). Toman programas y los ejecutan. Ahora, un lenguaje de programación se llama "Turing completo", si es que puede ejecutar cualquier programa (independientemente del idioma) que una máquina de Turing puede ejecutar con suficiente tiempo y memoria.

Por ejemplo: Digamos que hay un programa que toma 10 números y los agrega. La máquina de Turing puede ejecutar fácilmente este programa. Pero ahora imagine que por alguna razón su lenguaje de programación no puede realizar la misma adición. Esto lo haría "Turing incompleto" (por así decirlo). Por otro lado, si puede ejecutar cualquier programa que pueda ejecutar la máquina universal de Turing, entonces es Turing completo.

La mayoría de los lenguajes de programación modernos (p. Ej., Java, JavaScript, Perl, etc.) están completos porque implementan todas las características necesarias para ejecutar programas como la suma, multiplicación, condición if-else, declaraciones de retorno, formas de almacenar / recuperar / borrar datos y así sucesivamente.

Actualización: puede obtener más información en mi blog: "JavaScript se está completando" - Explicado

Raja Rao
fuente
55
La idea de que incluso habría un término para este tipo de máquina tiene mucho más sentido cuando recuerdo que Turing y otros primeros científicos informáticos construirían una máquina específica cada vez que quisieran resolver un problema específico. Estamos acostumbrados a una máquina que puede ser reprogramada para siempre. Gracias por el contexto, Raja.
Jacob Ford
¿Cómo se puede completar Turing en JavaScript? Carece de sistema de archivos, API multiproceso adecuada. Tiene toneladas de limitaciones, principalmente debido a la naturaleza del entorno limitado de seguridad del navegador. Difícilmente se le puede llamar 'un lenguaje de programación'. Vea cuántas variantes de abstracción de scripts existen (reaccionar, mecanografiar ... lo que sea), todo eso para compensar lo que JS no tiene. (Asm.js debe mencionarse aquí). Java, Python o C ++ son verdaderos ejemplos de 'Turing Complete'. Pero js? No lo creo.
Michael IV
2
@MichaelIV La máquina de turismo tampoco tenía un sistema de archivos / hilos. JS está absolutamente de gira completa.
Bax
@MichaelIV Para agregar a la respuesta de Bax, se podría considerar que una computadora moderna consta de varias máquinas Turing que trabajan juntas para permitir todas esas cosas agradables que mencionas. Por ejemplo, la CPU produce "cinta" para que la GPU la lea de modo que pueda escribir "cinta" para el monitor para que el monitor pueda escribir "cinta" para el usuario. Del mismo modo, la CPU podría producir "cinta" para los discos duros, NIC, tarjetas de sonido, etc.
86

De wikipedia :

La integridad de Turing, llamada así por Alan Turing, es importante porque cada diseño plausible para un dispositivo informático tan avanzado puede ser emulado por una máquina universal de Turing, una observación que se conoce como la tesis de Church-Turing. Por lo tanto, una máquina que puede actuar como una máquina universal de Turing puede, en principio, realizar cualquier cálculo que cualquier otra computadora programable sea capaz de hacer. Sin embargo, esto no tiene nada que ver con el esfuerzo requerido para escribir un programa para la máquina, el tiempo que puede tomar para que la máquina realice el cálculo, o cualquier habilidad que la máquina pueda poseer que no esté relacionada con el cálculo.

Si bien es probable que las máquinas verdaderamente completas de Turing sean físicamente imposibles, ya que requieren almacenamiento ilimitado, la integridad de Turing a menudo se atribuye libremente a máquinas físicas o lenguajes de programación que serían universales si tuvieran almacenamiento ilimitado. Todas las computadoras modernas son Turing-complete en este sentido.

No sé cómo puede ser más no técnico que eso, excepto diciendo "estar completo significa 'capaz de responder a un problema computable dado el tiempo y el espacio suficientes'".

Ran Biron
fuente
44
En este contexto, ¿qué es un "dispositivo informático"?
dopatraman
30
Como con la mayoría de los artículos de Wikipedia, aunque esta cita es técnicamente correcta, no proporciona ningún valor a una persona que no tiene conocimiento sobre el tema y está tratando de entenderlo. Poder explicar las cosas correctamente es una ciencia propia :)
Lacho Tomov
76

Definición informal

Un lenguaje completo de Turing es aquel que puede realizar cualquier cálculo. La tesis de Church-Turing establece que cualquier cálculo ejecutable puede ser realizado por una máquina de Turing. Una máquina de Turing es una máquina con memoria de acceso aleatorio infinita y un 'programa' finito que dicta cuándo debe leer, escribir y moverse a través de esa memoria, cuándo debe terminar con un determinado resultado y qué debe hacer a continuación. La entrada a una máquina de Turing se guarda en su memoria antes de que comience.

Cosas que pueden hacer que un lenguaje NO se complete

Una máquina de Turing puede tomar decisiones basadas en lo que ve en la memoria - El 'lenguaje' que sólo los soportes +, -, *, y /en números enteros no es Turing completo porque no puede tomar una decisión basada en su entrada, pero una máquina de Turing puede.

Una máquina de Turing puede ejecutarse para siempre : si tomamos Java, Javascript o Python y eliminamos la capacidad de hacer cualquier tipo de bucle, GOTO o llamada a función, no sería Turing completo porque no puede realizar un cálculo arbitrario que nunca termina Coq es un probador de teoremas que no puede expresar programas que no terminan, por lo que no está completo.

Una máquina de Turing puede usar memoria infinita : un lenguaje que era exactamente como Java pero que terminaría una vez que usara más de 4 Gigabytes de memoria no estaría completo, porque una máquina de Turing puede usar memoria infinita. Es por eso que en realidad no podemos construir una máquina de Turing, pero Java sigue siendo un lenguaje completo de Turing porque el lenguaje Java no tiene restricciones que le impidan usar memoria infinita. Esta es una razón por la cual las expresiones regulares no están completas.

Una máquina Turing tiene memoria de acceso aleatorio : un lenguaje que solo le permite trabajar con memoria pushy popoperaciones en una pila no estaría completo. Si tengo un 'lenguaje' que lee una cadena una vez y solo puede usar la memoria presionando y haciendo estallar desde una pila, me puede decir si cada parte (de la cadena tiene la suya )más tarde presionando cuando ve (y haciendo estallar cuando ve ). Sin embargo, no puede decirme si cada uno (tiene el suyo )más adelante y si cada uno [tiene el suyo ]más tarde (tenga en cuenta que ([)]cumple con este criterio pero ([]]no lo hace). Una máquina de Turing puede utilizar su memoria de acceso aleatorio para realizar un seguimiento ()'s y[]está por separado, pero este lenguaje con solo una pila no puede.

Una máquina de Turing puede simular cualquier otra máquina de Turing : una máquina de Turing, cuando se le da un "programa" apropiado, puede tomar el "programa" de otra máquina de Turing y simularlo en una entrada arbitraria. Si tuviera un lenguaje que tuviera prohibido implementar un intérprete de Python, no sería Turing completo.

Ejemplos de idiomas completos de Turing

Si su idioma tiene memoria de acceso aleatorio infinito, ejecución condicional y alguna forma de ejecución repetida, probablemente Turing esté completo. Hay sistemas más exóticos que aún pueden lograr todo lo que una máquina Turing puede hacer, lo que los hace completos también:

  • Cálculo lambda sin tipo
  • El juego de la vida de Conway
  • Plantillas C ++
  • Prólogo
Gordon Gustafson
fuente
11
SQL definitivamente está completo. Tiene capacidades de secuencias de comandos que permiten cualquier cálculo.
nzifnab
53
No, está confundiendo SQL con extensiones como T-SQL / PL-SQL. ANSI SQL no está completo. Pero TSQL / PLSQL - es.
Agnius Vasiliauskas
15
Aparentemente, SQL está completo: stackoverflow.com/questions/900055/…
Newtang
2
De acuerdo con la integridad de Turing: el sistema es completo de Turing si se puede utilizar para simular cualquier máquina de Turing de una sola cinta. Pero en el ejemplo anterior, como entendí, los desarrolladores construyeron particular cyclic tag systemy no universal cyclic tag system. Por lo tanto, el artículo no prueba la integridad del turing SQL (O no
entendí
2
No existe una implementación realizable de un lenguaje completo de Turing, porque no hay cintas infinitas. Lo que realmente queremos decir es que algunos idiomas tienen la capacidad de aproximar la integridad de Turing hasta los límites de la memoria disponible de la máquina host.
Shelby Moore III
17

Básicamente, la integridad de Turing es un requisito conciso, una recursión ilimitada.

Ni siquiera limitado por la memoria.

Pensé en esto independientemente, pero aquí hay una discusión sobre la afirmación. Mi definición de LSP proporciona más contexto.

Las otras respuestas aquí no definen directamente la esencia fundamental de la integridad de Turing.

Shelby Moore III
fuente
Los autómatas de estado finito pueden tener una recursión ilimitada. El caso en cuestión: a*.
3
Los FSM de @Rhymoid tienen memoria limitada ( el número finito de estados), pero la recursión ilimitada sin optimización de cola debe tener memoria ilimitada. No limité mi definición al subconjunto de recursión ilimitada solo con la optimización de cola. Quite amablemente su voto negativo.
Shelby Moore III
mantuviste la definición de recursión ilimitada brumosa. ¿Te refieres a 'recursión' en el sentido de 'recursividad primitiva' y 'ilimitada' al hacerla 'parcial' (o 'general' o 'mu-')? Entonces puede que tengas razón. Pero su formulación actual está demasiado cerca de las declaraciones criticadas en "On Folk Theorems" de David Harel. Es importante ser riguroso en matemáticas, y al dejar de lado definiciones precisas, lo ignora. Por cierto: los FSM pueden generalizarse para modelar la interacción; lo que los distingue de los TM es que el entorno de este último también está modelado (como la cinta).
La enumeración @Rhymoid es la antítesis de precisión, por ejemplo, enumere la precisión máxima de las fracciones de una pulgada. La recursión ilimitada significa todas las formas posibles de recursión, lo cual es imposible sin una cinta infinita. La recursión completamente generalizada (no solo general dentro del modelo) siempre es completa de Turing. Estoy declarando la equivalencia entre la recursividad generalizada y la capacidad de realizar cualquier cálculo posible. Esa es una equivalencia importante a tener en cuenta.
Shelby Moore III
"La recursión ilimitada significa todas las formas posibles de recursión" Esa es su lectura. Para la mayoría de los usuarios de SO, 'recursión ilimitada' significa while (p) { /* ... */ }. "Estoy declarando la equivalencia entre la recursividad generalizada y la capacidad de realizar cualquier cálculo posible". La tesis de la Iglesia es un asunto muy diferente y realmente debería discutirse por separado.
13

Turing completo significa que es al menos tan poderoso como una máquina de Turing . Esto significa que cualquier cosa que pueda ser calculada por una máquina de Turing puede ser calculada por un sistema Turing Complete.

Nadie ha encontrado aún un sistema más poderoso que una máquina de Turing. Entonces, por el momento, decir que un sistema es Turing Complete es lo mismo que decir que el sistema es tan poderoso como cualquier sistema informático conocido (ver Tesis de Church-Turing ).

Waylon Flinn
fuente
3
Tenga en cuenta que todo esto ignora el tiempo de la pared. Simplemente dice "se puede hacer".
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen en realidad, no tiene en cuenta la computabilidad física por completo. No solo podría llevar más tiempo que la edad del universo, sino que también podría usar más memoria de la que se puede construir con todos los fermiones y bosones del universo.
Waylon Flinn
Posiblemente, no hay límite para la cantidad de bosones y fermiones en el universo. No lo sabemos, y probablemente nunca lo sabremos, es el tamaño. Cada vez que lees sobre el número de X en 'el universo', la gente en realidad habla sobre el universo observable . Aunque interesante, no es un límite físico real.
Stijn de Witt
9

En los términos más simples, un sistema completo de Turing puede resolver cualquier posible problema computacional.

Uno de los requisitos clave es que el tamaño del bloc de notas sea ilimitado y que sea posible rebobinar para acceder a escrituras anteriores en el bloc de notas.

Así, en la práctica, ningún sistema es completo de Turing.

Más bien, algunos sistemas se aproximan a la integridad de Turing al modelar la memoria ilimitada y realizar cualquier cálculo posible que pueda caber dentro de la memoria del sistema.

Shelby Moore III
fuente
2

Creo que la importancia del concepto "Turing Complete" radica en la capacidad de identificar una máquina de computación (no necesariamente una "computadora" mecánica / eléctrica) que puede hacer que sus procesos se deconstruyan en instrucciones "simples", compuestas de más simples y más simples. instrucciones, que una máquina Universal podría interpretar y luego ejecutar.

Recomiendo encarecidamente el Turing anotado

@ Mark creo que lo que estás explicando es una mezcla entre la descripción de Universal Turing Machine y Turing Complete.

Algo que es Turing Complete, en un sentido práctico, sería una máquina / proceso / computación capaz de ser escrita y representada como un programa, para ser ejecutada por una Máquina Universal (una computadora de escritorio). Aunque no tiene en cuenta el tiempo o el almacenamiento, como lo han mencionado otros.

Brian Leahy
fuente
2

Lo que entiendo en palabras simples:

Turing completo: un lenguaje / programa de programación que puede hacer cómputo es Turing completo.

Por ejemplo :

  1. ¿Puedes agregar dos números usando solo HTML ? (La respuesta es ' No ', debe usar javascript para realizar la suma). Por lo tanto, HTML no está completo.

  2. Los lenguajes como Java, C ++, Python, Javascript, Solidity for Ethereum, etc. son Turing Complete porque puedes hacer cálculos como agregar dos números usando estos lenguajes.

Espero que esto ayude.

Shirish Singh
fuente
0

Está completo si puede probar y ramificarse (tiene un 'si')

Allan Wrobel
fuente
1
Para una pregunta tan antigua, valdría la pena verificar si otros ya han hecho contribuciones similares o más sustanciales
alan ocallaghan
No estoy seguro de la exactitud de la respuesta. Pero esta es una explicación realmente simple que nunca había visto antes. Lo curioso: hace mucho, mucho tiempo (después de escribir mi primer código) también utilicé la misma explicación para definir el procesador más simple posible.
Victor Yarema
Es un excelente primer intento con una definición operativa incisiva, concisa y precisa. Sin embargo, la rama debe permitir el bucle y, ¿no es el caso que la máquina también debe permitir llamadas de subrutina (es decir, recursividad)? ¿Existe un programa aplanado de bucles anidados para cada programa con recursión?
user3673
0

Una máquina Turing requiere que cualquier programa pueda realizar pruebas de condición. Eso es fundamental.

Considere un reproductor de piano roll. El reproductor de piano puede tocar una pieza musical muy complicada, pero nunca hay una lógica condicional en la música. Está Turing completo.

La lógica condicional es tanto el poder como el peligro de una máquina que está Turing completa.

El piano roll está garantizado para detenerse siempre. No existe tal garantía para un TM. Esto se llama el "problema de detención".

Richard Riehle
fuente
-1

Como dijo Waylon Flinn :

Turing completo significa que es al menos tan poderoso como una máquina de Turing.

Creo que esto es incorrecto, un sistema está completo de Turing si es exactamente tan poderoso como la Máquina de Turing, es decir, todos los cálculos realizados por la máquina pueden ser realizados por el sistema, pero también todos los cálculos realizados por el sistema pueden ser realizados por la máquina de Turing .

ChrisC
fuente
1
Creo que estás asumiendo que la tesis de Church-Turing es verdadera para llegar a esta conclusión. Aún no se ha probado. La propiedad que está describiendo se llama 'Equivalente de Turing'.
Waylon Flinn
1
@WaylonFlinn No, tiene razón. "Completitud" significa que es al menos tan fuerte como una cosa, pero tampoco más fuerte. Comparar con "NP-Complete".
Devin Jeanpierre el
3
@DevinJeanpierre No quiero comenzar una guerra de llamas aquí, pero estoy casi seguro de que la clase computacional que estás describiendo se llama "Equivalente de Turing". Sin embargo, Turing Complete tiene una relación similar con NP-Complete. NP-Complete es igual a NP si y solo si P = NP. Del mismo modo, Turing Complete es igual a Turing Equivalente si y solo si la tesis de Church-Turing es correcta.
Waylon Flinn
@Waylon Source? Nada de lo que leo coincide con eso (por ejemplo, en.wikipedia.org/wiki/Turing_completeness )
Devin Jeanpierre
44
@DevinJeanpierre Lo dice allí mismo, en el artículo de Wikipedia con el que se vincula. Citando la sección de definiciones formales: "Un sistema computacional que puede calcular cada función computable de Turing se llama Turing completo", "Un sistema Turing-completo se llama equivalente de Turing si cada función que puede calcular también es computable Turing"
Waylon Flinn
-2

En términos prácticos de lenguaje familiares para la mayoría de los programadores, la forma habitual de detectar la integridad de Turing es si el lenguaje permite o permite la simulación de sentencias while sin límite anidadas (a diferencia del estilo Pascal para sentencias, con límites superiores fijos).

Keith Douglas
fuente
1
Un solo ciclo while ilimitado es suficiente para simular una máquina Turing.
masterxilo
-8

¿Puede una base de datos relacional ingresar latitudes y longitudes de lugares y caminos, y calcular el camino más corto entre ellos? Este es un problema que muestra que SQL no está completo.

Pero C ++ puede hacerlo y puede hacer cualquier problema. Así es.

Akshay Jain
fuente
10
Ser capaz de calcular la ruta más corta entre puntos no es la definición de Turing completa. Hay mucho más que solo ese ejemplo.
Eva
1
Voy a poner esto aquí ... hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.aspx
Matthew Whited el