theory - programming - machine learning pdf español

¿Qué es Turing Complete? (12)

¿Qué significa la expresión "Turing Complete"?

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

Definición informal

Un lenguaje completo de Turing es aquel que puede realizar cualquier cálculo. La Tesis de Church-Turing establece que cualquier computación realizable puede ser realizada por una máquina de Turing. Una máquina de Turing es una máquina con una 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 resultado determinado y qué debe hacer a continuación. La entrada a una máquina de Turing se pone en su memoria antes de que comience.

Cosas que pueden hacer que un idioma NO sea Turing completo.

Una máquina de Turing puede tomar decisiones basándose en lo que ve en la memoria : el ''lenguaje'' que solo admite + , - , * y / en enteros no está completo porque no puede hacer una elección en función de su entrada, pero sí una La máquina de turing puede.

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

Una máquina de Turing puede usar memoria infinita : un lenguaje que era exactamente igual a 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. Esta es la razón por la que no podemos construir una máquina Turing, pero Java sigue siendo un lenguaje completo de Turing porque el lenguaje Java no tiene ninguna restricción que le impida utilizar una memoria infinita. Esta es una de las razones por las que las expresiones regulares no están completas.

Una máquina de Turing tiene memoria de acceso aleatorio : un idioma que solo le permite trabajar con la memoria a través de pop operaciones push y pop en una pila no se completaría con Turing. Si tengo un ''lenguaje'' que lee una cadena una vez y solo puedo usar la memoria empujando y haciendo estallar en una pila, me puede decir si cada ( en la cadena tiene su propia ) más adelante presionando cuando vea ( y haciendo estallar cuando ve ) . Sin embargo, no puede decirme si cada ( tiene su propio ) más adelante y cada [ tiene su propio ] más tarde (tenga en cuenta que ([)] cumple con este criterio pero ([]] no lo hace). Una máquina de Turing puede usar su memoria de acceso aleatorio a track () ''s y [] '' s por separado, pero este idioma 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 estaba prohibido implementar un intérprete de Python, Turing no estaría completo.

Ejemplos de idiomas completos de Turing.

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

Calculo lambda sin atornillar
El juego de la vida de Conway.
Plantillas C ++
Prólogo

¿Puede una base de datos relacional ingresar latitudes y longitudes de lugares y carreteras, y calcular el camino más corto 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.

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 en cuanto al tiempo de ejecución o la memoria).

Entonces, si alguien dice "mi nuevo producto es Turing Complete", eso significa que 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 chico escribió un simulador de Turing Machine en vi, por lo que es posible decir que vi es el único motor computacional que se ha necesitado en el mundo.

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 está completo de Turing si es exactamente tan potente como la Máquina de Turing, es decir, cada cálculo realizado por la máquina puede ser realizado por el sistema, pero también todos los cálculos realizados por el sistema pueden ser realizados por la máquina de Turing. .

Creo que la importancia del concepto "Turing Complete" reside en la capacidad de identificar una máquina informática (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 altamente el Turing Anotado

@Mark, creo que lo que está 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 escribirse y representarse como un programa, para ser ejecutada por una Máquina Universal (una computadora de escritorio). Aunque no toma en cuenta el tiempo o el almacenamiento, como lo mencionan otros.

De wikipedia :

La integridad de Turing, nombrada en honor a Alan Turing, es significativa porque cada máquina plausible de Turing puede emular todo diseño plausible para un dispositivo de computación hasta ahora avanzado, 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 realizar. 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 la máquina para realizar el cálculo o cualquier capacidad que la máquina pueda tener y que no esté relacionada con el cálculo.

Si bien las máquinas realmente completas de Turing son muy imposibles físicamente, ya que requieren almacenamiento ilimitado, la integridad de Turing a menudo se atribuye a máquinas físicas o lenguajes de programación que serían universales si tuvieran 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 al decir "turing complete significa ''capaz de responder a un problema computable si se le da suficiente tiempo y espacio''".

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 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 está completo en 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.

En términos prácticos de lenguaje familiar 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 anidadas e ilimitadas (a diferencia del estilo de Pascal para sentencias, con límites superiores fijos).

Fundamentalmente, la integridad de Turing es un requisito conciso, una recursión ilimitada.

Ni siquiera limitado por la memoria.

Pensé en esto de forma independiente, pero aquí hay una discusión de 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.

Lo que entiendo en palabras simples:

Turing Complete: Un lenguaje / programa de programación que puede hacer cálculos, es Turing complete.

Por ejemplo :

¿Puedes agregar dos números usando solo HTML ? (La respuesta es '' No '', debe usar javascript para realizar la adición). Por lo tanto, HTML no es Turing Complete.
Los lenguajes como Java, C ++, Python, Javascript, Solidity para Ethereum, etc. son Turing Complete porque puede hacer cálculos como agregar dos números usando estos lenguajes.

Espero que esto ayude.

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. 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 (consulte la Tesis de Church-Turing ).

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. Así que 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 puede ejecutar cualquier programa (independientemente del idioma) que una máquina de Turing pueda 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 la máquina universal de Turing pueda ejecutar, entonces Turing está completo.

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

Actualización: puede obtener más información en la publicación de mi blog: "JavaScript está completo para Turing", se explica