¿Qué es Turing Complete?

¿Qué significa la expresión “Turing Complete”?

¿Puedes dar una explicación simple, sin entrar en demasiados detalles teóricos?

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

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

Entonces, si alguien dice “mi nueva cosa es Turing completa” eso significa en principio (aunque a menudo no en la práctica) podría usarse para resolver cualquier problema de cálculo.

En algún momento es una broma … un tipo escribió un simulador de máquina Turing en vi, por lo que es posible decir que vi es el único motor computacional jamás utilizado en el mundo.

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

Alan Turing creó una máquina que puede tomar un progtwig y ejecutar ese progtwig y mostrar algunos resultados. Pero luego tuvo que crear diferentes máquinas para diferentes progtwigs. Entonces creó “Universal Turing Machine” que puede tomar CUALQUIER progtwig y ejecutarlo.

Los lenguajes de progtwigción son similares a esas máquinas (aunque virtuales). Toman progtwigs y los ejecutan. Ahora, un lenguaje de progtwigción se llama “Turing completo”, si es que puede ejecutar cualquier progtwig (independientemente del idioma) que una máquina de Turing pueda ejecutar dado suficiente tiempo y memoria.

Por ejemplo: digamos que hay un progtwig que toma 10 números y los agrega. La máquina de Turing puede ejecutar fácilmente este progtwig. Pero ahora imagine por alguna razón que su lenguaje de progtwigción no puede hacer la misma adición, entonces es la máquina de Turing incompleta. Por otro lado, si puede ejecutar cualquier progtwig como la máquina de turing universal puede ejecutar, entonces está completo.

La mayoría de los lenguajes de progtwigción modernos como Java, JavaScript, Perl, etc. están completos porque todos implementan todas las características requeridas para ejecutar progtwigs como adición, multiplicación, condición if-else, declaraciones de retorno, formas de almacenar / recuperar / borrar datos, etc. .

Actualización: Puede obtener más información en mi publicación de blog: “JavaScript is Turing Complete” – Explicado

De la wikipedia :

La exhaustividad de Turing, que lleva el nombre de Alan Turing, es significativa ya que cada diseño plausible para un dispositivo informático avanzado puede ser emulado por una máquina universal de Turing, una observación que se conoce como la tesis 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 progtwigble sea capaz de hacer. Sin embargo, esto no tiene nada que ver con el esfuerzo requerido para escribir un progtwig para la máquina, el tiempo que puede tomar la máquina para realizar el cálculo o cualquier habilidad que la máquina pueda poseer que no estén relacionadas con el cálculo.

Mientras que las máquinas verdaderamente completas de Turing son físicamente imposibles, ya que requieren un almacenamiento ilimitado, la integridad de Turing a menudo se atribuye a máquinas físicas o lenguajes de progtwigción que serían universales si tuvieran un almacenamiento ilimitado. Todas las computadoras modernas son Turing completas en este sentido.

No sé cómo puede ser más no técnico que eso, excepto diciendo que “es un medio completo” capaz de responder un problema computable dado el tiempo y el espacio suficientes “.

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 performable 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 “progtwig” 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 idioma NO esté completo

Una máquina de Turing puede tomar decisiones basadas en lo que ve en la memoria : el ‘lenguaje’ que solo admite enteros + , - , * y / en enteros no está completo porque no puede hacer una elección basada en su entrada, sino La máquina de Turing puede.

Una máquina de Turing puede funcionar 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 express progtwigs que no finalizan, por lo que no es completo.

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

Una máquina de Turing tiene memoria de acceso aleatorio : un lenguaje que solo le permite trabajar con la memoria mediante operaciones push y pop en una stack no sería Turing completo. Si tengo un ‘idioma’ que lee una cadena una vez y solo puede usar la memoria empujando y apareciendo desde una stack, puede decirme si cada uno ( en la cadena tiene el suyo ) más tarde presionando cuando vea ( y aparece cuando ve ) . Sin embargo, no puede decirme si cada ( tiene lo suyo ) más tarde y cada [ tiene lo suyo ] más adelante (tenga en cuenta que ([)] cumple este criterio pero ([]] no). Una máquina de Turing puede usar su memoria de acceso aleatorio para rastrear () y [] ‘s por separado, pero este lenguaje con solo una stack 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 “progtwig” apropiado, puede tomar otro “progtwig” de la máquina de Turing y simularlo en una entrada arbitraria. Si tenía un idioma que estaba prohibido implementar un intérprete de Python, no sería Turing completo.

Ejemplos de Turing idiomas completos

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

  • Cálculo lambda no utilizado
  • El juego de la vida de Conway
  • Plantillas C ++
  • Prólogo

Fundamentalmente, la completitud de Turing es un requisito conciso, recursividad 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 completitud de Turing.

Turing Complete 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. Por lo tanto, 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 la Tesis de Church-Turing ).

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

Uno de los requisitos clave es que el tamaño del bloc de notas no tenga límites y que sea posible rebobinar para acceder a las escrituras anteriores en el bloc de notas.

Por lo tanto, en la práctica, ningún sistema es Turing-completo.

Más bien, algunos sistemas se aproximan a la completitud de Turing modelando la memoria ilimitada y realizando cualquier cálculo posible que pueda caber dentro de la memoria del sistema.

Creo que la importancia del concepto “Turing Complete” está 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 simple y simple instrucciones, que una máquina Universal podría interpretar y luego ejecutar.

Recomiendo mucho The Annotated Turing

@ Mark, creo que lo que estás explicando es una mezcla entre la descripción de la Máquina universal de Turing y Turing completa.

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 progtwig, para ser ejecutada por una Máquina Universal (una computadora de escritorio). Aunque no toma en cuenta el tiempo o el almacenamiento, como lo mencionaron otros.

Como dijo Waylon Flinn :

Turing Complete significa que es al menos tan poderoso como una Máquina de Turing.

Creo que esto es incorrecto, un sistema es Turing completo si es exactamente tan poderoso como la Máquina de Turing, es decir, cada computación hecha por la máquina puede ser hecha por el sistema, pero también cada computación hecha por el sistema puede ser hecha por la máquina de Turing .

En términos de lenguaje práctico familiar para la mayoría de los progtwigdores, la forma habitual de detectar la integridad de Turing es si el lenguaje permite o permite la simulación de sentencias while ilimitadas anidadas (a diferencia de las sentencias al estilo Pascal, con límites superiores fijos).

¿Puede una base de datos relacional ingresar latitudes y longitudes de lugares y caminos, y calcular la ruta más corta entre ellos – no. Este es un problema que muestra que SQL no está completo.

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