¿Cuál es el conjunto mínimo de características / estructuras de lenguaje que lo completan?
¿Cuál es el conjunto mínimo de características / estructuras de lenguaje que lo completan?
Un Turing tarpit es un tipo de lenguaje de programación esotérico que se esfuerza por completar Turing utilizando al mismo tiempo tan pocos elementos como posible. Brainfuck es quizás el tarpit más conocido, pero hay muchos.
Iota y Jot son lenguajes funcionales con dos y tres símbolos, respectivamente, basados en el SK (I) cálculo de combinador .
OISC ( Una computadora de conjunto de instrucciones ) denota un tipo de cálculo imperativo que requiere solo una instrucción de uno o más argumentos, generalmente" restar y derivar si es menor o igual a cero ", o" restar y omitir en reversa si se solicita un préstamo ". La MMU x86 implementa la instrucción anterior y, por lo tanto, se completa con Turing.
En general, para que un lenguaje imperativo esté completo, se necesita:
Una forma de repetición condicional o salto condicional (por ejemplo, while , if + goto )
Una forma de leer y escribir alguna forma de almacenamiento (por ejemplo, variables, cinta)
Para que un lambda-calculus sea un lenguaje funcional basado en TC, necesita:
La capacidad de abstraer funciones sobre argumentos (por ejemplo, abstracción lambda, cita)
La capacidad de aplicar funciones a argumentos (por ejemplo, reducción)
Por supuesto, hay otras formas de ver la computación, pero estos son modelos comunes para los tarpits de Turing. Tenga en cuenta que las computadoras reales son no máquinas de Turing universales porque no tienen almacenamiento ilimitado. Estrictamente hablando, son "máquinas de almacenamiento limitadas". Si siguiera agregándoles memoria, se acercarían asintóticamente a las máquinas de Turing en el poder. Sin embargo, incluso las máquinas de almacenamiento limitado y las máquinas de estados finitos son útiles para el cálculo; simplemente no son universales .
Estrictamente hablando, la E / S no es necesaria para completar Turing; TC solo afirma que un idioma puede calcular la función que desea, no que pueda mostrarle el resultado. En la práctica, cada lenguaje útil tiene una forma de interactuar con el mundo de alguna manera.
Desde un punto de vista más práctico: si puede traducir todos los programas en un idioma de Turing-complete a su idioma, entonces (por lo que sé), su idioma debe ser Turing-completo. Por lo tanto, si desea verificar si el lenguaje que diseñó es Turing-complete, simplemente puede escribir un Brainf *** en el compilador YourLanguage y demostrar o demostrar que puede compilar todos los programas BF legales.
Para aclarar, quiero decir que además de un intérprete para YourLanguage, usted escribe un compilador (en cualquier idioma) que pueda compilar cualquier programa BF en YourLanguage (manteniendo la misma semántica, por supuesto).
Un sistema solo se puede considerar como Turing completo si puede hacer cualquier cosa que una máquina universal de Turing pueda hacer. Como se dice que la máquina universal de Turing puede resolver cualquier función computable en un tiempo determinado, los sistemas completos de Turing también pueden, por extensión, hacerlo.
Para verificar si algo está completo en Turing, vea si puede implementar una máquina de Turing en su interior. En otras palabras, verifique si puede simular lo siguiente:
Estos son los verdaderos requisitos mínimos para que un sistema se considere Turing completo. Nada más y nada menos. Si no puede simular ninguno de estos de alguna manera, no es Turing completo. Los métodos que otras personas propusieron son solo medios para el fin, ya que hay varios sistemas completos de Turing que no tienen esas características.
Tenga en cuenta que no hay forma conocida de construir un verdadero sistema completo de Turing. Esto se debe a que no se conoce ninguna forma de simular de manera genuina la ilimitación de la cinta de la máquina de Turing dentro del espacio físico.
Un lenguaje de programación está completo si puedes hacer cualquier cálculo con él. No hay un solo conjunto de características que haga que el lenguaje se complete, por lo que las respuestas dicen que necesita bucles o que necesita que las variables sean incorrectas, ya que hay lenguajes que no tiene ninguno pero se está completando.
Alan Turing hizo la máquina de turing universal y si puedes traducir cualquier programa diseñado para funcionar en la máquina universal para que se ejecute en tu idioma, también es Turing completo. Esto también funciona indirectamente, por lo que puede decir que el idioma X se está completando si todos los programas para el idioma completo Y se pueden traducir a X, ya que todos los programas de la máquina universal de turismos se pueden traducir a un programa Y.
La complejidad del tiempo, la complejidad del espacio, el formato de entrada / salida fácil y la escritura fácil de cualquier programa no se incluyen en la ecuación, por lo que dicha máquina puede, en teoría, hacer todos los cálculos si los cálculos no se detienen debido a la pérdida de potencia o al tragar la Tierra. el sol.
Por lo general, para demostrar que están completos, hacen un intérprete para cualquier idioma probado, pero para que funcione se necesitan medios de entrada y salida, dos cosas que realmente no se requieren para que un idioma se complete. Es suficiente que su programa pueda alterar su estado al inicio y que pueda inspeccionar la memoria después de que el programa se haya detenido.
Sin embargo, para hacer un lenguaje exitoso se necesita algo más que una completa integridad, y esto es cierto incluso para los tarpits. No creo que BrainFuck hubiera sido popular sin , y . .
No puedes saber si se repetirá infinitamente o se detendrá.
Explicación: dada alguna información, es imposible decir en todos los casos (usando otra máquina de Turing) si la cosa va a hacer un bucle infinito o eventualmente se detendrá, excepto ejecutándolo (lo que le da una respuesta si se detiene) , pero no si hace un bucle!).
Esto significa que tienes que poder almacenar una cantidad de datos potencialmente ilimitada de alguna manera; tiene que haber un equivalente a la cinta infinita, ¡no importa lo complicada que sea! (De lo contrario, solo hay un número finito de estados y luego puede verificar si ha pasado por ese estado anteriormente y finalmente se detiene). En general, las máquinas de Turing pueden aumentar o reducir el tamaño de su estado por algún medio controlable.
Dado que la máquina de Turing universal original de Turing tiene un problema de detención sin solución, su propia máquina completa de Turing también debe tener un problema de detención sin solución.
Los sistemas completos de Turing pueden emular a cualquier otro sistema completo de Turing, por lo que si puede construir un emulador para algún sistema completo de Turing conocido en su sistema, eso demuestra que su sistema también está completo.
Por ejemplo, supongamos que quieres probar que Snakes & Escaleras se completó con Turing, dada una tabla con un patrón de cuadrícula infinitamente repetido (con una versión diferente en la parte superior e izquierda). Sabiendo que la máquina Minsky de 2 contadores está completa Turing (que tiene 2 contadores ilimitados y 1 estado de un número finito), puede construir un tablero equivalente donde las posiciones X e Y en la cuadrícula son el valor actual de los 2 contadores y la ruta actual es el estado actual. ¡Explosión! Acabas de probar que Snakes & Las escaleras están completamente terminadas.
Una condición necesaria es un bucle con un recuento máximo de iteraciones que no se determina antes de la iteración, o recursión donde la profundidad máxima de recursión no se determina más adelante. A modo de ejemplo, para ... in ... los bucles, como los encuentra en muchos idiomas nuevos, no son lo suficientemente no para completar el idioma (pero tendrán otros medios). Tenga en cuenta que esto no significa un número limitado de iteraciones o una profundidad de recursión limitada, sino que las iteraciones máximas y la profundidad de recursión se deben calcular por adelantado.
Por ejemplo, la función Ackermann no se puede calcular en un idioma sin estas características. Por otro lado, una gran cantidad de software altamente complejo y muy útil puede escribirse sin requerir estas características.
Por otro lado, con cada recuento de iteraciones y cada profundidad de recursión calculadas por delante, no solo se puede decidir si un programa se detendrá o no, sino que se se detendrá.
Sé que esta no es la respuesta oficialmente correcta, pero una vez que retire el 'mínimo' de 'Turing-complete' y coloque 'práctico' en su lugar, verá las características más importantes que distinguen una programación. El lenguaje de un lenguaje de marcas son
siguiente venga
para probar estas afirmaciones, comience con un lenguaje de marcado, por ejemplo, HTML. podríamos inventar un HTML + con solo variables, o solo condicionales (MS hizo eso con comentarios condicionales), o algún tipo de construcción de bucle (que en ausencia de condicionales probablemente terminaría como algo así como <repeat n='4'>...</repeat> ). hacer cualquiera de estos hará que HTML + sea significativamente más poderoso que el HTML simple, pero aún así sería más un marcado que un lenguaje de programación; Con cada nueva característica, hace que sea menos de un lenguaje declarativo y más de un imperativo.
la búsqueda de la minimalidad en lógica y programación es importante e interesante, pero si tuviera que enseñar a jóvenes o viejos 'qué es la programación' y 'cómo aprender a programar', difícilmente podría comenzar con la Amplitud y anchura de los fundamentos teóricos de la integridad de Turing. toda la esencia de la cocina y la programación es hacer las cosas, en el orden correcto, repitiendo hasta que esté listo, como lo hizo tu madre. eso lo resume todo para mí.
de nuevo, nunca terminé mi CS.
Lea otras preguntas en las etiquetas turing-completeness