¿Cuál es el conjunto mínimo de características / estructuras del lenguaje que lo hacen completo de Turing?
turing-completeness
Gato curioso
fuente
fuente
Respuestas:
Un tarpit de Turing es un tipo de lenguaje de programación esotérico que se esfuerza por completar Turing mientras usa la menor cantidad de elementos 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 cálculo del combinador SK (I) .
OISC ( One Instruction Set Computer ) denota un tipo de cálculo imperativo que requiere solo una instrucción de uno o más argumentos, generalmente "restar y ramificar si es menor o igual que cero", o "restar y omitir inversamente si se toma prestado". El x86 MMU implementa la instrucción anterior y, por lo tanto, es Turing completo.
En general, para que un lenguaje imperativo sea completo en Turing, necesita:
Una forma de repetición condicional o salto condicional (p. Ej.
while,if+goto)Una forma de leer y escribir alguna forma de almacenamiento (por ejemplo, variables, cinta)
Para que un lenguaje funcional basado en cálculo lambda sea TC, necesita:
La capacidad de abstraer funciones sobre argumentos (por ejemplo, abstracción lambda, cita)
La capacidad de aplicar funciones a argumentos (p. Ej., Reducción)
Por supuesto, hay otras formas de ver la computación, pero estos son modelos comunes para lonas de Turing. Tenga en cuenta que las computadoras reales no son máquinas Turing universales porque no tienen almacenamiento ilimitado. Estrictamente hablando, son "máquinas de almacenamiento acotadas". Si siguiera agregando memoria a ellos, se acercarían asintóticamente a las máquinas de Turing en el poder. Sin embargo, incluso las máquinas de almacenamiento acotadas y las máquinas de estados finitos son útiles para el cálculo; simplemente no son universales .
Estrictamente hablando, no se requiere E / S para completar Turing; TC solo afirma que un lenguaje puede calcular la función que desea, no que puede mostrarle el resultado. En la práctica, cada lenguaje útil tiene una forma de interactuar con el mundo de alguna manera.
fuente
Desde un punto de vista más práctico: si puede traducir todos los programas de un idioma completo de Turing a su idioma, entonces (que yo sepa), su idioma debe ser completo de Turing. Por lo tanto, si desea verificar si un lenguaje que diseñó es Turing-complete, simplemente puede escribir un Brainf *** en el compilador YourLanguage y demostrar / demostrar que puede compilar todos los programas legales de BF.
Para aclarar, quiero decir que además de un intérprete para YourLanguage, usted escribe un compilador (en cualquier idioma) que puede compilar cualquier programa BF en YourLanguage (manteniendo la misma semántica, por supuesto).
fuente
</sarcasm>Un sistema solo se puede considerar como Turing completo si puede hacer algo que una máquina universal de Turing pueda hacer. Dado que se dice que la máquina universal de Turing es capaz de resolver cualquier función computable en un tiempo determinado, los sistemas completos de Turing pueden, por extensión, tambié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 requisitos mínimos verdaderos para que un sistema sea considerado Turing completo. Nada más y nada menos. Si no puede simular ninguno de estos de alguna manera, no está completo. Los métodos que otras personas propusieron son solo medios para el final, ya que hay varios sistemas completos de Turing que no tienen esas características.
Tenga en cuenta que no hay una forma conocida de construir un verdadero sistema completo de Turing. Esto se debe a que no hay una forma conocida de simular genuinamente lo ilimitado de la cinta de la máquina Turing dentro del espacio físico.
fuente
Un lenguaje de programación se está completando si puede hacer algún cálculo con él. No hay un solo conjunto de características que completen un lenguaje durante el tiempo, por lo que las respuestas que dicen que necesita bucles o que necesita variables son incorrectas, ya que hay idiomas que no tienen ninguno pero están completos.
Alan Turing creó la máquina universal de Turing y, si puede traducir cualquier programa diseñado para funcionar en la máquina universal para que se ejecute en su idioma, también es completo. Esto también funciona indirectamente, por lo que puede decir que el lenguaje X se está completando si todos los programas para el lenguaje completo Y se pueden traducir para X ya que todos los programas de máquinas universales se pueden traducir a un programa Y.
La complejidad del tiempo, la complejidad del espacio, la facilidad de formato de entrada / salida y la facilidad de escribir cualquier programa no se incluyen en la ecuación, por lo que, en teoría, dicha máquina puede hacer todos los cálculos si los cálculos no se detienen por la pérdida de potencia o el sol se traga la Tierra.
Por lo general, para demostrar su integridad, hacen un intérprete para cualquier idioma probado, pero para que funcione necesita medios de entrada y salida, dos cosas que realmente no son necesarias para que un idioma esté completo. Es suficiente que su programa pueda alterar su estado al inicio y que pueda inspeccionar la memoria después de detener el programa.
Sin embargo, para crear un lenguaje exitoso se necesita algo más que la integridad completa, y esto es cierto incluso para las lonas impermeables. No creo que BrainFuck hubiera sido popular sin
,y..fuente
No se puede saber si se repetirá infinitamente o se detendrá.
-------------
Explicación: Dada alguna información, es imposible saber en todos los casos (usando otra máquina de Turing) si la cosa se repetirá infinitamente o finalmente se detendrá, excepto ejecutándola (lo que le da una respuesta si se detiene, pero no si se repite!).
Esto significa que tiene que ser capaz de almacenar una cantidad de datos potencialmente ilimitada de alguna manera: ¡debe haber un equivalente a la cinta infinita, sin importar cuán enrevesada sea! (De lo contrario, solo hay un número finito de estados y luego puede verificar si ya ha pasado por ese estado y, finalmente, detenerse). 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 Turing universal original de Turing tiene un problema de detención insoluble, su propia máquina completa de Turing también debe tener un problema de detención insoluble.
Los sistemas completos de Turing pueden emular 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, suponga que desea demostrar que Snakes & Ladders está completa en Turing, dado un tablero con un patrón de cuadrícula infinitamente repetido (con una versión diferente en el lado superior e izquierdo). Sabiendo que la máquina Minsky de 2 contadores está Turing completa (que tiene 2 contadores ilimitados y 1 estado de un número finito), puede construir un tablero equivalente donde la posición X e Y en la cuadrícula es el valor actual de los 2 contadores y la ruta actual es el estado actual. ¡Explosión! Acabas de demostrar que Snakes & Ladders están completos.
fuente
Una condición necesaria es un bucle con un recuento de iteración máximo que no se determina antes de la iteración, o recursión donde la profundidad de recursión máxima no se determina adelante. Como ejemplo, para ... en ... los bucles, ya que los encuentra en muchos idiomas más nuevos, no son suficientes para completar el lenguaje (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 deben calcularse con anticipación.
Por ejemplo, la función de Ackermann no se puede calcular en un idioma sin estas características. Por otro lado, se puede escribir una gran cantidad de software altamente complejo y altamente útil sin requerir estas características.
Por otro lado, con cada recuento de iteraciones y cada profundidad de recursión calculada con anticipación, no solo se puede decidir si un programa se detendrá o no, sino que se detendrá.
fuente
Sé que esta no es la respuesta formalmente correcta, pero una vez que elimine el 'mínimo' de 'Turing-complete' y vuelva a colocar 'práctico' donde pertenece, verá las características más importantes que distinguen un lenguaje de programación de un lenguaje de marcado son
luego viene
Para probar estas afirmaciones, comience con un lenguaje de marcado, por ejemplo, HTML. podríamos inventar un HTML + con variables solamente, o solo condicionales (MS lo hizo con comentarios condicionales), o algún tipo de construcción de bucle (que en ausencia de condicionales probablemente terminaría como algo así
<repeat n='4'>...</repeat>). hacer cualquiera de estos hará que HTML + sea significativamente (?) más poderoso que HTML simple, pero aún sería más un marcado que un lenguaje de programación; con cada nueva característica, lo convierte en un lenguaje menos declarativo y más imperativo.La búsqueda de la minimidad en la lógica y la programación es importante e interesante, pero si tuviera que enseñar a los jóvenes o viejos 'qué es la programación' y 'cómo aprender a programar', difícilmente comenzaría con toda la amplitud y amplitud de los fundamentos teóricos de la integridad de Turing. toda la esencia de la cocina y la programación es hacer cosas, en el orden correcto, repitiendo hasta que esté listo, como lo hizo tu madre. Eso lo resume todo para mí.
Por otra parte, nunca terminé mi CS.
fuente