icono letras

Inicio

Presentación

Las secciones del sitio son las siguientes:

C--

Lenguaje

Especificación del lenguaje de programación C--. Se presentan las instrucciones y el modo de escribir un programa a partir de ellas. Las instrucciones se definen usando reglas gramaticales, donde los no terminales están en cursiva, los terminales en negrita, el símbolo «» se usa entre el símbolo en la cabecera de la regla y los símbolos por los que puede ser sustituido y el símbolo «|» para separar las opciones de sustitución.

Durante la ejecución del programa se mantiene un indicador que señala la próxima instrucción en ser ejecutada; a este indicador le llamaré puntero. Al conjunto de programa y puntero le llamaré registro.

Las instrucciones especifican cómo hay que modificar el registro. Cada ejecución de una instrucción diré que es un paso en la ejecución del programa.

Cada instrucción hace referencia a una posición del programa, que influye en el resultado de la ejecución. A esta posición le llamaré la posición referida por la instrucción.

Al ente que ejecuta el programa C-- lo llamaremos computador.

Macros

Se presentan una serie de macroinstrucciones, cadenas de símbolos que pueden ser sustituidos sistemáticamente por otras cadenas. Al ente que realiza esta sustitución de símbolos le llamaré expansor o traductor. Se presentan además algunas reglas que debe seguir el traductor a la hora de hacer el conjunto de sustituciones.

Algunos de los recursos usados en la explicación son:

Ejemplo Turing

Se muestra un programa en C-- (usando macros) que ejecuta una máquina de Turing introducida como dato. Con este ejemplo se pretende demostrar que se puede imitar la computación de cualquier máquina, siendo este programa en efecto una máquina universal de Turing escrita en C--.

Ejemplo recursivo

Se muestra un programa en C-- (usando macros), que usa una función recursiva primitiva que computa lo mismo que un programa C-- que se recibe como argumento. La función actúa pues, extrapolando la terminología de Turing, como un ejecutor universal de programas C--. El programa está escrito basándome en las definiciones de S. C. Kleene (‘Introduction to Metamathematics’, pág. 219).

El programa C-- que recibe la función debe ser codificado como un entero no negativo. El programa recursivo transforma este código en otro código representando un registro del programa y el puntero que señala las instrucciones que se van ejecutando. La codificación se hace como sigue:

codificación de instrucción

Usando la notación xn, donde x es una instrucción y n su código:

  1. La instrucción nula se codifica como 0.

  2. ‘0’1; ‘=’2; ‘*’3; ‘1’4.

  3. Sea xn; entonces xm, donde m = n + 4.

codificación de programa

Sea L la lista ordenada donde están escritas las instruccionhes del programa p que se va a codificar. Usando la notación pn, donde p es el programa y n su código:

  1. El programa sin instrucciones se codifica como 0.

  2. Si el programa consta de una única instrucción x escrita en la primera posición de L, entonces p3n.

  3. Si el programa consta de más de una instrucción, sea q un programa escrito en L, 𝖗 la última posición usada en L para escribir las instrucciones de q y sea q de tal forma que p es el programa resultante de escribir la instrucción x en la siguiente posición de 𝖗 en L. Sea xn y qm; sea a su vez w el programa resultante de sustituir todas las instrucciones del programa q por instrucciones ‘0’ y wz; entonces pm × αn, donde α es el menor número primo mayor que el mayor divisor de z.

codificación de registro

Sea pn; el registro formado por el programa p y el puntero que señala a la posición s será m, donde m = n × 2s.

AMT

Lenguaje

Se presenta el lenguaje AMT (Alan Mathison Turing) para escribir máquinas de Turing. Este lenguaje es el definido por el propio Turing (‘On Computable Numbers, with an Application to the Entscheidungsproblem’), salvo alguna pequeña modificación para evitar ambigüedades a la hora de interpretarlo.

Ejemplo C--

Se presenta una máquina de Turing que ejecuta programas C--. La máquina empieza con el programa escrito en la cinta y el lector posicionado en, o a la derecha de, la celda más a la izquierda que no esté vacía. El programa C-- se escribe en la cinta de la siguiente manera:

escritura del programa

Al inicio todas las celdas están vacías. En el proceso de escribir el programa en la cinta, si no están todas las celdas vacías, sea en cualquier momento α la celda más a la derecha con algún símbolo, y sea β la celda inmediatamente a la derecha de α.

  1. Si el programa sólo tiene una instrucción, llamémosla inst, se escoge cualquier celda; sea ésta 𝕮. Diremos que el programa se escribe a partir de 𝕮 si se hace de la siguiente manera:

    1. si la instrucción inst es nula se escribe en 𝕮 el símbolo «-».

    2. si la instrucción inst tiene un sólo símbolo se escribe éste en 𝕮.

    3. para escribir la instrucción inst se escribe inst a partir de 𝕮 y el símbolo «’» en β.

  2. Si el programa tiene más de una instrucción, sea P el programa, inst la primera instrucción de P y P el programa resultante de quitar inst a P. Para escribir P:

    1. se escribe el programa cuya única instrucción es inst.

    2. se escribe P a partir de β.

Los sucesivos registros que se derivarían al ejecutar al programa por un computador de C-- quedan reflejados, en el mismo orden, por algún estado de la máquina. Si la ejecución del programa C-- terminase en caso de ser ejecutado por un computador la máquina pararía, e invirtiendo las reglas sobre escritura en la cinta se podría obtener el programa final resultante de la ejecución. Esta máquina es por tanto un computador de C--.