Un pequeño lenguaje tipo C que las máquinas de Turing pueden simular

Estoy buscando un lenguaje pequeño que ayude a 'convencer' a los estudiantes de que las máquinas de Turing son un modelo informático suficientemente general. Es decir, un lenguaje que se parece a los idiomas a los que están acostumbrados, pero que también es fácil de simular en una máquina de Turing.

Papadimitriou usa máquinas RAM para este trabajo, pero me temo que comparar algo extraño (como máquina de turing) con otra cosa extraña (básicamente, un lenguaje ensamblador) sería demasiado poco convincente para muchos estudiantes.

Cualquier sugerencia sería bienvenida (especialmente si vinieran con alguna literatura recomendada)

• $smn$$utm$

  Dudo que este sea el enfoque más simple posible, pero me gusta cómo se basa en algunos de los teoremas más fundamentales de la computabilidad (que es posible que desee abarcar por otros motivos).

  Parece que Andrej Bauer respondió una pregunta similar sobre Mathoverflow hace unos meses.

• Si está configurado en un lenguaje similar a C, su camino será mucho más duro, ya que tienen una semántica bastante complicada: deberá

  1. Demuestre que las máquinas de Turing pueden simular una pila y un montón al mismo tiempo, y
  2. Mostrar cómo se pueden implementar variables con una pila, y
  3. Muestre que las llamadas a procedimientos se pueden implementar con una pila.

  Esto es gran parte del contenido de una clase de compiladores, sinceramente.

Mi profesor de teoría de la competencia en pregrado comenzó probando que una máquina de Turing de una sola cinta puede implementar una máquina de Turing de varias cintas. Esto maneja la declaración de variables: si un programa tiene seis declaraciones de variables, entonces se puede implementar fácilmente en una máquina Turing de siete cintas (una cinta para cada variable y una cinta de "registro" para ayudar a realizar tareas como la aritmética y la verificación de igualdad entre cintas). Luego mostró cómo implementar bucles básicos FOR y WHILE, y en ese momento teníamos un lenguaje básico tipo C completo de Turing. Lo encontré satisfactorio, de todos modos.

Ahora mismo estoy pensando en cómo convencerme de que las máquinas de Turing son un modelo general de computación. Estoy de acuerdo en que el tratamiento estándar de la tesis de Church-Turing en algunos libros de texto estándar, por ejemplo, Sipser, no es muy completo. Aquí hay un bosquejo de cómo podría pasar de las máquinas de Turing a un lenguaje de programación más reconocible.

Considere un lenguaje de programación estructurado en bloque con ify whiledeclaraciones, con funciones definidas no recursivas y subrutinas, con variables aleatorias booleanas nombradas y expresiones booleanas generales, y con una única matriz booleana sin límites tape[n]con un puntero de matriz entera nque puede incrementarse o disminuirse, n++o n--. El puntero nes inicialmente cero y la matriz tapees inicialmente cero. Por lo tanto, este lenguaje de computadora puede ser similar a C o Python, pero es muy limitado en sus tipos de datos. De hecho, son tan limitados que ni siquiera tenemos una forma de usar el puntero nen una expresión booleana. Asumiendo quetapees solo infinito a la derecha, podemos declarar un "error del sistema" de flujo inferior del puntero si nalguna vez es negativo. Además, nuestro lenguaje tiene una exitdeclaración con un argumento, para generar una respuesta booleana.

Entonces, el primer punto es que este lenguaje de programación es un buen lenguaje de especificación para una máquina Turing. Puede ver fácilmente que, a excepción de la matriz de cintas, el código solo tiene muchos estados posibles: el estado de todas sus variables declaradas, la línea de ejecución actual y su pila de subrutinas. Este último solo tiene una cantidad finita de estado porque las funciones recursivas no están permitidas. Se podría imaginar un "compilador" que crea una máquina de Turing "real" a partir de un código de este tipo, pero los detalles no son importantes. El punto es que tenemos un lenguaje de programación con una sintaxis bastante buena, pero tipos de datos muy primitivos.

El resto de la construcción es convertir esto a un lenguaje de programación más habitable con una lista finita de funciones de biblioteca y etapas de precompilación. Podemos proceder de la siguiente manera:

1. Con un precompilador, podemos expandir el tipo de datos booleanos a un alfabeto de símbolos más grande pero finito como ASCII. Podemos suponer que tapetoma valores en este alfabeto más grande. Podemos dejar un marcador al comienzo de la cinta para evitar el desbordamiento del puntero, y un marcador móvil al final de la cinta para evitar que el TM patine hasta el infinito en la cinta accidentalmente. Podemos implementar operaciones binarias arbitrarias entre símbolos y conversiones a declaraciones booleanas ify while. (En realidad, también ifse puede implementar whilesi no estuviera disponible).

2. $k$$k$$i$$i$$k$

3. Designamos una cinta como "memoria" con valor de símbolo y las otras como "registros" o "variables" sin signo y con valor entero. Almacenamos los enteros en binario little-endian con marcadores de terminación. Primero implementamos copia de un registro y decremento binario de un registro. Combinando eso con el incremento y la disminución del puntero de memoria, podemos implementar la búsqueda de acceso aleatorio de la memoria de símbolos. También podemos escribir funciones para calcular la suma binaria y la multiplicación de enteros. No es difícil escribir una función de suma binaria con operaciones bit a bit, y una función para multiplicar por 2 con desplazamiento a la izquierda. (O realmente desplazamiento a la derecha, ya que es little-endian.) Con estas primitivas, podemos escribir una función para multiplicar dos registros usando el algoritmo de multiplicación larga.

4. Podemos reorganizar la cinta de memoria de una matriz de símbolos unidimensionales symbol[n]a una matriz de símbolos bidimensionales symbol[x,y]usando la fórmula n = (x+y)*(x+y) + y. Ahora podemos usar cada fila de la memoria para expresar un entero sin signo en binario con un símbolo de terminación, para obtener una memoria unidimensional, de acceso aleatorio y con valor entero memory[x]. Podemos implementar la lectura desde la memoria a un registro entero, y la escritura desde un registro a la memoria. Ahora se pueden implementar muchas funciones con funciones: aritmética de punto flotante y firmado, cadenas de símbolos, etc.

5. Solo una instalación básica más requiere estrictamente un precompilador, es decir, funciones recursivas. Esto se puede hacer con una técnica que se usa ampliamente para implementar lenguajes interpretados. Asignamos a cada función recursiva de alto nivel una cadena de nombre, y organizamos el código de bajo nivel en un whilebucle grande que mantiene una pila de llamadas con los parámetros habituales: el punto de llamada, la función llamada y una lista de argumentos.

En este punto, la construcción tiene suficientes características de un lenguaje de programación de alto nivel que una mayor funcionalidad es más el tema de los lenguajes de programación y compiladores que la teoría de CS. También es fácil escribir un simulador de máquina de Turing en este lenguaje desarrollado. No es exactamente fácil, pero ciertamente estándar, escribir un autocompilador para el idioma. Por supuesto, necesita un compilador externo para crear la TM externa a partir de un código en este lenguaje similar a C o Python, pero eso se puede hacer en cualquier lenguaje de computadora.

Tenga en cuenta que esta implementación esbozada no solo admite la tesis de Church-Turing de los lógicos para la clase de función recursiva, sino también la tesis de Church-Turing extendida (es decir, polinomial), ya que se aplica al cálculo determinista. En otras palabras, tiene una sobrecarga polinómica. De hecho, si nos dan una máquina RAM o (mi favorito personal) una cinta de árbol TM, esto puede reducirse a una sobrecarga poligarítmica para el cálculo en serie con memoria RAM.

El compilador LLVM le permite a uno "conectar" de manera bastante sencilla una nueva arquitectura. Llaman a esto escribir un nuevo back-end , y dan instrucciones detalladas y ejemplos de cómo hacerlo. Sospecho que tendrá que saltar algunos obstáculos con respecto a la memoria de acceso aleatorio, si no desea apuntar a una máquina RAM Turing, pero esto definitivamente es factible, ya que he visto una serie de proyectos que hacen que LLVM genere VHDL u otros lenguajes de máquina muy diferentes.

Esto tendría el efecto interesante de tener un compilador de optimización de última generación (en muchos sentidos, LLVM es más avanzado que GCC) que genera código para una máquina Turing.

No estoy en la teoría cs pero tengo algo que podría ser útil. He tomado otro acercamiento. Diseñé un procesador simple directamente programable con un pequeño subconjunto de C. No hay código de ensamblaje, solo código tipo C. Puede usar la misma herramienta que usé y modificar este procesador para diseñar su simulador de máquina Turing. Me tomó 4 días diseñar, simular y probar este procesador, ¡algunas instrucciones! Las herramientas que utilicé incluso me permitieron generar código sintetizable VHDL real. Es un verdadero procesador de trabajo.

Así es como se ve un programa:

Aquí hay una imagen del procesador usando estas herramientas:

Las herramientas "Novakod Studio" utilizan un lenguaje de descripción de hardware de lenguaje de alto nivel. A modo de ejemplo, aquí está el código del contador del programa: suficiente para hablar, si alguien está interesado, aquí está la información pública para contactarme: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Luc

¿Qué tal si tomamos la idea representada por el usuario GMB aquí (la máquina de Turing con una cinta puede simular una máquina de Turing con N cintas entrelazando las N cintas en una sola cinta y leyendo cualquiera de esas cintas saltando N ubicaciones a la vez, una Turing la máquina con cintas N puede implementar ...) y escribir un programa de máquina de Turing que implemente una máquina RAM simplista. La máquina RAM en realidad podría ser una CPU simplista y real con backend LLVM o GCC disponible. Luego, el GCC / LLVM se puede usar para compilar de forma cruzada un programa C para esa CPU y el programa de la máquina Turing que simula la máquina RAM, ejecuta la simulación de la máquina RAM haciendo que la máquina RAM simulada ejecute la salida GCC / LLVM. La implementación de la máquina Turing podría ser un código C muy simple que se ajuste a un pequeño archivo C.

En lo que respecta a la máquina RAM, existe un proyecto de demostración, donde una CPU de 32 bits es simulada por un microcontrolador de 8 bits y la CPU de 32 bits simulada arranca Linux. Lento como el infierno, pero según el autor , Dmitry Grinberg, funcionó. Quizás la CPU Zylin (usuario de GitHub zylin) podría ser una opción viable para la máquina RAM simulable. Otro candidato a la máquina RAМ podría ser el ProjectOberon dot com de Niklaus Wirth .

(El "punto" y "com" en mi texto se deben al hecho de que, solo 2015_10_21, registré mi cuenta en cstheory.stackexchange y la aplicación web no permite más de 2 enlaces para usuarios novatos, a pesar del hecho que pueden ver automáticamente desde mis otras cuentas de stackexchange que podría ser estúpido, pero no soy un troll).