¿Qué significa ser Turing completo?

34

Veo que la mayoría de las definiciones de lo que es ser Turing completo son tautológicas hasta cierto punto. Por ejemplo, si buscas en Google "qué significa ser Turing completo", obtienes:

Una computadora está completa en Turing si puede resolver cualquier problema que una máquina de Turing pueda ...

Si bien está muy bien definido si los diferentes sistemas están completos o no, no he visto una explicación de cuáles son las implicaciones / consecuencias de estar completo.

¿Qué puede hacer una máquina de Turing cuando no existe una máquina que no sea de Turing que también pueda realizar la misma tarea? Por ejemplo, una computadora puede realizar cálculos simples como (1+5)/3=?, pero una calculadora ordinaria también puede hacerlos, lo que no está completo de Turing si estoy en lo correcto.

¿Hay alguna manera de definir las capacidades de Turing Machine sin solo decir "poder simular otra máquina de Turing"?

sashoalm
fuente
31
Busque la definición de "máquina de turing". No existe una definición circular, ya que una máquina de Turing no se define como "ser capaz de simular otra máquina de Turing": es una computadora teórica totalmente diseñada (básicamente, una máquina de estado de cinta infinita). Simplemente estás mezclando "turing-complete" y "turing machine". Hasta donde yo sé, todavía no conocemos ningún algoritmo que no pueda ejecutarse en una máquina de Turing, pero eso podría ser solo mi propia ignorancia.
Luaan
2
@Luaan La tesis de la Iglesia-Turing estaría de acuerdo con usted.
Brian McCutchon
"¿Hay alguna manera de definir las capacidades de Turing Machine". Seguro. La teoría analiza cuánto espacio y tiempo se requiere para resolver algoritmos con máquinas de Turing (L, NL, P, NP, PSPACE, etc.), y también hay problemas que no se pueden resolver (que generalmente se pueden resolver mediante reducciones a otros problemas sin solución). Un ejemplo de un problema que las máquinas de Turing no pueden resolver es el problema de la detención.
Millie Smith
Cuando se trata de la teoría de CS (o cualquier otra), siempre es mejor leer un libro sobre el tema que googlearlo y leer algunas publicaciones de blog sobre el tema que, en muchos casos, están escritas por personas que no entienden completamente el tema. sí mismos. Un buen libro le ahorrará tiempo, le dará una visión más amplia y una mejor comprensión.
Bozidar Sikanjic
La función de Ackermann es un ejemplo destacado de algo que una máquina de Turing puede calcular pero un modelo de cómputo más limitado ( recursividad primitiva ) no puede.
zwol

Respuestas:

13

Pensé un momento si agregaría otra respuesta. Las otras respuestas se centran en el centro de su pregunta (sobre "turing complete", "tautología", etc.). Permítanme tomar la primera y la última parte, y por lo tanto la imagen más grande y ligeramente filosófica:

Pero, ¿qué significa?

¿Qué significa ser Turing completo?

¿Hay alguna manera de definir las capacidades de Turing Machine sin solo decir "poder simular otra máquina de Turing"?

Hablando informalmente, estar Turing completo significa que su mecanismo puede ejecutar cualquier algoritmo que pueda imaginar, sin importar cuán complejo, profundo, recursivo, complicado, largo (en términos de código) sea, y no importa cuánto almacenamiento o tiempo sea necesitaba evaluarlo. No hace falta decir que solo tiene éxito si el problema es computable, pero si es computable, tendrá éxito (alto).

(NB: para averiguar por qué esto es "informal", consulte la tesis de Church-Turing que va en esa línea, con una redacción más elaborada; sin embargo, al ser una tesis, podría o no ser correcta. Gracias a @DavidRicherby por señalando esta pequeña omisión en un comentario).

"Algoritmo" significa lo que comúnmente entendemos hoy como algoritmo informático; es decir, una serie de pasos discretos que manipulan el almacenamiento, con cierta lógica de control mezclada. Sin embargo, no es como una máquina Oracle, es decir, no puede "adivinar".

Ejemplo para un lenguaje práctico no tc

Si se ha programado usted mismo, probablemente conozca expresiones regulares, utilizadas para unir cadenas con algún patrón.

Este es un ejemplo de una construcción que no está completada en Turing. Puede encontrar fácilmente ejercicios en los que es simplemente imposible crear una expresión regular que coincida con ciertas frases.

Por ejemplo (y esto seguramente ha molestado a muchos programadores en aplicaciones reales reales), es teórica y prácticamente imposible crear una expresión regular que coincida con un lenguaje de programación o un documento XML: es imposible que una expresión regular encuentre la estructura de bloques ( do ... endo { ... }en idiomas; abrir y cerrar etiquetas en documentos XML) si se permite que sean arbitrariamente profundas. Si hay un límite allí, por ejemplo, solo puede tener 3 niveles de "recursión", entonces podría encontrar una expresión regular; pero si no está limitado, entonces no se puede.

Como obviamente es posible crear un programa en un lenguaje completo de Turing (como C) para analizar el código fuente (cualquier compilador lo hace), las expresiones regulares nunca podrán simular dicho programa, por lo tanto, por definición, no son completas de Turing

Motivación

La idea de la máquina de turing en sí misma no es nada práctica; es decir, Turing ciertamente no lo inventó para crear una computadora real o algo así, a diferencia de Charles Babbage o von Neumann, por ejemplo. El punto de tener el concepto de la Máquina de Turing es que es extremadamente simple. Consiste en casi nada. Reduce las computadoras posibles (y reales) al mínimo más imaginable.

El punto de esta simplificación, a su vez, es que esto hace que sea fácil (ish) reflexionar sobre cuestiones teóricas (como detener problemas, clases de complejidad y lo que sea que le moleste a la informática teórica). Una característica en particular es que generalmente es muy fácil verificar si un idioma o computadora puede simular una máquina de Turing simplemente programando dicha máquina de Turing (¡que es tan fácil!) En ese idioma.

Hasta el infinito

Tenga en cuenta que nunca necesita tiempo o almacenamiento infinito ; pero tanto el tiempo como el almacenamiento son ilimitados. Tendrán un valor máximo para cada ejecución computable, pero no hay límite en cuanto a qué tan grande puede llegar a ser ese valor. Aquí se pasa por alto el hecho de que una computadora real se quedará sin RAM; esto es, por supuesto, un límite para cualquier computadora física, pero también es obvio y no tiene ningún interés para el "poder de cómputo" teórico de la máquina. Además, no nos interesa el tiempo que realmente lleva, en absoluto. Entonces, nuestra pequeña máquina puede usar cantidades arbitrarias de tiempo y espacio, lo que la hace absolutamente poco práctica.

... y más allá

Una asombrosa último punto, entonces, es que un simple ejemplo, algo tan simple puede hacer todo lo que cualquier ordenador real concebible podría alguna vez , en todo el universo, lograr (solo mucho más lento) - por lo menos en lo que conocemos hoy en día.

AnoE
fuente
"Hablando informalmente, estar completo de Turing significa que su mecanismo puede ejecutar cualquier algoritmo que se le ocurra" Bueno, eso se basa en aceptar la tesis de Church-Turing, que dice que las máquinas de Turing pueden implementar cualquier algoritmo que se pueda imaginar. O, alternativamente, podría tomar las máquinas de Turing como la definición de algoritmo, en cuyo caso la declaración informal es solo una versión informal de "puede simular cualquier máquina de Turing" (que no es algo malo; solo una observación).
David Richerby
Mi impresión fue que el OP pregunta por una comprensión intuitiva de lo que significa estar completo. Por lo tanto, este tipo de respuesta frívola, no teórica-informática. Gracias por señalar esto, lo integraré en la respuesta. @DavidRicherby
AnoE
¡Gracias! Ese es el tipo de respuesta que estaba buscando. Estaba pensando en el problema de detención y en cómo los lenguajes con for-bucles limitados simples son predecibles (siempre se detienen) y, por lo tanto, no se completan con Turing. Estaba pensando que tal vez completar Turing significa ser potencialmente impredecible de alguna manera (¿es caótico el término correcto para esas funciones?)
sashoalm
@sashoalm, me alegra que te guste la respuesta. No, la imprevisibilidad realmente no tiene en cuenta el problema. Los bucles for limitados (como no tc) también son un buen ejemplo. De hecho, otro buen ejemplo para un lenguaje tc simple (y más real) sería uno que solo tenga variables y (sin límites) while, eso ya es suficiente para ser tc. La (des) limitación de la estructura de control es uno de los elementos clave.
AnoE
38

No es tautológico en absoluto.

Un modelo de computación es Turing completo si puede simular todas las máquinas de Turing, es decir, es al menos tan poderoso como las máquinas de Turing.

Una cosa que las máquinas de Turing pueden hacer es simular otras máquinas de Turing (a través de la máquina universal de Turing). Eso significa que, si su modelo de cómputo no puede simular máquinas de Turing, no puede hacer al menos una cosa que las máquinas de Turing pueden hacer, por lo que no satisface la definición, por lo que no está completa. No hay circularidad porque no definimos la integridad de Turing en términos de sí mismo: dijimos que la integridad de Turing es la propiedad de poder hacer todo lo que las máquinas de Turing pueden hacer.

unasi

¿Hay alguna manera de definir las capacidades de Turing Machine sin solo decir "poder simular otra máquina de Turing"?

No estoy seguro de lo que quiere decir con "definir las capacidades de las máquinas de Turing". Las capacidades se definen en términos del autómata de estado finito que opera en la cinta infinita. (No repetiré la definición completa, pero puede encontrarla, por ejemplo, en Wikipedia ).

David Richerby
fuente
19
Creo que OP mezcla Turing machine y Turing complete. Lo que realmente está buscando es la definición de una máquina de Turing; Su última oración es la respuesta. en.wikipedia.org/wiki/Turing_machine ayudaría.
JollyJoker
Entonces, ¿qué puede hacer una máquina de Turing? Como en el caso, si quisiera demostrar que algo puede emular una máquina de Turing, ¿qué conjunto mínimo de comportamientos debo poder demostrar que mi máquina también puede hacer?
Akshat Mahajan
2
No importa: deduje que es suficiente demostrar que un lenguaje puede imitar la forma en que funciona una máquina de Turing para demostrar que está completa.
Akshat Mahajan
17

El modelo de computación de Turing es solo uno de los muchos modelos equivalentes de computación. Tiene el mismo poder que las funciones recursivas de Gödel y el cálculo lambda de Church, que se propusieron aproximadamente al mismo tiempo, así como otros modelos como la máquina de puntero. Por lo tanto, puede afirmar que

Una computadora está completa en Turing si puede resolver cualquier problema que Excel pueda.

Esto funciona ya que Excel también está completo de Turing. Recomiendo echar un vistazo a la página de Wikipedia sobre la tesis de Church-Turing , y en una encuesta de Blass y Gurevich, Algorithms: A Quest for Absolute Definitions .


Con respecto a su pregunta, ¿qué puede hacer una máquina de Turing que no puede hacer una máquina que no es de Turing? En general, la respuesta depende de la máquina que no es de Turing.

Sin embargo, es posible definir nociones no triviales de problemas completos de Turing, por ejemplo:

LUNAFunaUNAF(una)L

Según esta definición, las codificaciones adecuadas del problema de detención son completas de Turing, por lo que para una clase razonable de máquinas (dependiendo de la definición de "eficientemente computable"), la máquina está completa de Turing si puede realizar algunas (equivalentemente, todas ) Lenguaje completo de Turing.

Hay muchos otros problemas completos de Turing capturados por este formalismo, dependiendo de la definición de "eficientemente computable", como el problema de correspondencia de Turing y los problemas relacionados con las fichas de Wang y el Juego de la Vida. Cualquiera de estos problemas puede funcionar como un punto de referencia en lugar del problema de detención.

Yuval Filmus
fuente
"Desafortunadamente, la respuesta depende de la máquina que no es de Turing". Edité mi pregunta porque no estaba clara. Puede elegir cualquier máquina que no sea de Turing, siempre y cuando pueda realizar la tarea mientras no esté completa.
sashoalm
55
Excel is also Turing-complete.- solo si puedes darle a Excel memoria infinita. Excel está limitado a 1,048,576 filas y 16,384 columnas, lo cual es mucho menos que infinito.
MattClarke
55
@MattClarke: Cierto, pero por la misma razón que ningún sistema jamás construido es Turing completo.
Emil
3
@Emil: exactamente, y es importante que los estudiantes de CS distingan entre las capacidades de los modelos de computación y las capacidades de las máquinas reales. Por supuesto, aquellos de nosotros que hemos alcanzado repetidamente los límites físicos de nuestras máquinas reales encontramos esta distinción fácil de hacer. Así que sabemos cómo definiríamos una versión sin restricciones del modelo de computación de Excel, y que sería Turing completo. A pesar de que escribir esa definición es un poco complicado.
Steve Jessop
44
@SteveJessop ¿Límites físicos de las máquinas? ¿Cómo podría alguien golpear tal cosa? ¡640k es suficiente para cualquiera!
David Richerby
4

En primer lugar, deseo señalar que la definición de integridad de Turing no es tautológica en absoluto. No solo probar un modelo computacional Turing-complete es un resultado interesante en sí mismo, sino que también le permite extender de inmediato todos los resultados de la teoría de la computabilidad a este otro modelo computacional; por ejemplo: las máquinas de 2 contadores están completas en Turing, las máquinas de Turing no pueden resolver el problema de detención, por lo tanto, las máquinas de 2 contadores no pueden.

La caracterización simple de las funciones computables por una máquina de Turing viene dada por μ-funciones recursivas, el conjunto mínimo de funciones cerradas bajo composición, recursividad primitiva y operador de minimización que contiene la función constantemente cero, la identidad y la función sucesora.

Dicha clase incorpora aquellas funciones que son "intuitivamente computables", es decir, que la computación podría ser realizada por un humano siguiendo un algoritmo preciso con lápiz y papel.

Obviamente "intuitivamente computable" no es realmente una definición formal, la identificación de "intuitivamente computable" con "Turing computable" se conoce como la tesis de Church-Turing. Dado que muchos intentos formales para caracterizar la computabilidad finalmente convergen en un modelo computacional que es completo de Turing, aunque nunca habrá una prueba formal de tal afirmación en un sentido matemático, existen razones sólidas para creerlo.

ordenación rápida
fuente
0

Una máquina Turing tiene la capacidad de calcular el mismo conjunto de funciones que una computadora cuántica universal, que puede simular cualquier sistema físico:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

Como tal, una máquina Turing es capaz de realizar cualquier procesamiento de información permitido por las leyes de la física, aunque no siempre lo hará de la manera más eficiente posible.

alanf
fuente