HOME

Definición de Máquinas de Turing

Índice

Las máquinas de Turing son un model sencillo de cómputo, pero veremos gradualmente que es igual de poderoso que varios otros modelos. De hecho, el que varios intentos de índole muy distinta de definir rigurosamente qué significa computabilidad resulten en definiciones equivalentes es una indicación de que la computabilidad es un concepto fundamental que tenemos correctamente formalizado de varias formas.

Lo básico que tiene una máquina de Turing

Veremos de hecho dos definiciones ligeramente diferentes de máquina de Turing, que difieren en el formato de las instrucciones que sigue la máquina. Ambas definiciones tienen bastante en común, y empezaremos por describir eso.

Una máquina de Turing tiene:

  • un conjunto finito \(S\) de símbolos;
  • un conjunto finito \(Q\) de estados, uno de los cuales se designa como el estado inicial;
  • una memoria infinita que en cada momento guarda una sucesión de símbolos que es infinita en ambas direcciones, es decir, en cada momento la memoria está dada por una función \(m : \mathbb{Z} \to S\);
  • una cabeza que puede leer y modificar el símbolo en una posición especifica de la memoria (dada por un entero), y puede moverse a la izquierda o la derecha;
  • una cantidad finita de instrucciones que indican qué hace la máquina paso a paso, cada instrucción indica una pareja de un estado y un símbolo y solo es aplicable si la máquina se encuentra en ese estado y la cabeza lee ese símbolo.

Pediremos que para cada pareja de un estado y un símbolo haya a lo más una instrucción aplicable. Así en cada paso está claro que debe hacer la máquina de Turing.1

Para operar una máquina de Turing, el usuario decide la entrada, es decir, el contenido inicial de la memoria; la máquina entra al estado inicial con la cabeza en la posición 0 y sigue las instrucciones. Puede pasar una de dos cosas: o bien después de un número finito de pasos la máquina termina, en cuyo caso decimos que la salida es la sucesión de símbolos que haya quedado en la memoria; o bien nunca para, en cuyo caso no hay salida correspondiente a la entrada.

La máquina de Turing define entonces una función parcial de las entradas a las salidas. Lo de parcial se refiere a que realmente la salida no tiene por qué estar definida para cualquier entradas. (Formalmente una función parcial \(A \to B\) es simplemente una función \(A' \to B\) donde \(A'\) es algún subconjunto de \(A\)).

Ahora explicamos dos variantes de la definición, que difieren en el formato de las instrucciones.

Versión de Turing

En la definición original de Turing todas las instrucciones son de la forma:

  • Si la máquina está en el estado \(q\) y la cabeza lee el símbolo \(s\), entonces:
    1. la cabeza reemplaza el símbolo por \(s'\),
    2. la cabeza se: (<) mueve un lugar a la izquierda, (|) queda donde está, o (>) mueve un lugar a la derecha, y
    3. la máquina pasa al estado \(q'\).

La instrucción está determinada por la quinteta \((q,s,s',d,q')\) donde \(d \in \{<, |, >\}\) indica cual de las opciones de movimiento de cabeza se toma en el segundo paso.

Versión de Post

En la variante de Post cada instrucción o bien imprime un símbolo o bien mueve la cabeza, así que hay dos tipos de instrucciones:

  • Si la máquina está en el estado \(q\) y la cabeza lee el símbolo \(s\), entonces imprime el símbolo \(s'\) y pasa al estado \(q'\).
  • Si la máquina está en el estado \(q\) y la cabeza lee el símbolo \(s\), entonces la cabeza se mueve un lugar a la izquierda/derecha y la máquina pasa al estado \(q'\).

Representamos estás instrucciones con cuartetas \((q,s,i,q')\) donde \(i \in S \sqcup \{<,>\}\), indica o bien qué símbolo de \(S\) imprimir, o bien en qué dirección mover la cabeza.

Preguntas

La sección «Preguntas» en general va a contener cosas para pensar relativas al tema. Algunas son ejercicios «normales» donde está claro qué es una solución correcta, pero algunas son preguntas más «abiertas», «vagas» o «filosóficas», y tienen como motivo entender algo intuitivamente o entender porque las cosas se hacen de cierta forma. Estas preguntas son para discutir en el chat del curso o en la sesión de video.

  • Aségurate de entender cómo funciona una máquina de Turing. Puede ser útil jugar con un simulador de máquinas de Turing.
  • ¿Es posible «componer» dos máquinas de Turing? Es decir, dadas dos máquinas existe una tercera tal que el efecto de usarla sea que la primera corra hasta que termine (si termina), y después que le segunda corra (usando de entrada la salida que dejó la primera).
  • Cuando queremos crear máquinas de Turing que haga cálculos aritméticos, por ejemplo, hay que decidir cómo vamos a representar los números como entradas para la máquina. Por ejemplo, para funciones \(\mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) podemos usar estos dos esquemas diferentes:

    Notación unaria
    Usamos como símbolos2 \(S = \{\ast, 1\}\) y representamos el número \(n\) como una memoria llena de \(\ast\) salvo por \(n\) posiciones consecutivas de la memoria donde ponemos un \(1\).
    Notación binaria
    Usamos como símbolos \(S = \{\ast, 0, 1\}\) y representamos \(n\) por su notación binaria en medio de un mar de \(\ast\). Por ejemplo \(6\) sería \(\cdots\ast\ast110\ast\ast\cdots\).

    ¿Cómo afecta la elección de notación la existencia de una máquina de Turing para calcular una función dada?

  • Escribe algunas máquinas de Turing para desarrollar una intuición de qué pueden hacer y qué tan práctico es hacerlo. Aquí hay algunas sugerencias de tareas a llevar a cabo con una máquina de Turing:

    (En general supondremos la entrada consta de una infinidad de \(\ast\), luego una sucesión finita de 0s y 1s, y al final otra infinidad de \(\ast\), con la cabeza colocada inicialmente en el primero 0 o 1).

    • Sobreescribe todos los 0 con 1.
    • Sobreescribe los 0 y 1 con \(\ast\).
    • Supón que la entrada solo tiene \(\ast\) y \(1\)s, duplica la cadena de 1s —por ejemplo la entrada \(\cdots\ast111\ast\cdots\) debería corresponder a la salida \(\cdots*111111\ast\cdots\)
    • Decidir si un número en notación binaria es múltiplo de 3 o no.
    • Sumar dos números en notación unaria.
    • Sumar dos números en notación binaria.
  • ¿Son igual de expresivas las dos variantes de máquina de Turing? ¿Cualquier máquina de un tipo puede ser simulada por una del otro tipo?

Referencias

Estos libros usan cuartetas (estado, símbolo, símbolo o movimiento, estado nuevo):

  • Crossley et al, What is Mathematical Logic?, capítulo 4, p. 31–36.
  • Weber, Computability Theory, sección 3.2, p. 43–50.

Éstas referencias usan funciones de transición:

  • Bridges, Computability: A Mathematical Sketchbook p. 5–15.
  • Stanford Encyclopedia of Philosophy, Turing Machines.

Finalmente, recomiendo jugar con el simulador de máquinas de Turing de Martín Ugarte.


1

Se pueden permitir varias isntrucciones aplicables y dejar que la máquina «adivine» cual es la que debe usar: eso es el concepto más sofisticado de máquina de Turing no determinista.

2

Usaremos el asterisco para las posiciones de la memoria que dejamos «en blanco», porque de hecho usar un espacio en blanco sería confuso.

Omar Antolín Camarena