1. No category

1
Curso Básico de Computación
7 Máquina de Turing
Es este capı́tulo introducimos la Máquina de Turing que es, un modelo matemático simple de una computadora.
7.1 Introducción
Hasta ahora no se ha podido demostrar que el modelo de la maquina de Turing
es equivalente a nuestra noción intuitiva de una computadora, pero existen argumentos complejos que sugieren esta equivalencia, a esto se le conoce como la
hipótesis de Church. La maquina de Turing tiene un poder computacional
más grande que cualquier computadora digital actual y no parece factible que
pueda ser superada algún dı́a. Al igual que los AFD y los AP, la máquina de
Turing es un dispositivo teórico que se utiliza principalmente en estudios de
computabilidad y de análisis de complejidad computacional.
7.2 El modelo de la Máquina de Turing
Un modelo formal de cómputo efectivo debe tener ciertas propiedades. Primero,
cada procedimiento debe poder ser descrito de manera finita. Segundo, el procedimiento debe consistir de pasos separados, y cada uno de ellos debe poderse
llevar a cabo de manera mecánica. Este modelo fue introducido por Alan Turing en 1936. Aquı́ presentaremos una variante.
El modelo básico que se ilustra en la siguiente figura,
a1 a2 ... ai ... an B B ...
Control
Finito
tiene un control finito, una cinta que está dividida en celdas, y una cabeza de
la cinta que explora una celda en la cinta a la vez. La cinta tiene una primer
celda ubicada en la posición más a la izquierda de la cinta pero es infinita del
lado derecho. Cada celda en la cinta puede contener exactamente un sı́mbolo
tomado de un alfabeto finito. Inicialmente, las n celdas más a la izquierda,
para algún número finito n ≥ 0, contienen la entrada de la máquina, la cual
es una cadena de sı́mbolos que se escogen de un alfabeto llamado sı́mbolos
de entrada. Todas las celdas restantes (que forman un conjunto infinito) contienen el sı́mbolo blanco, el cual es un sı́mbolo especial que no forma parte del
alfabeto de entrada.
Feliú Sagols Troncoso
Matemáticas-Cinvestav
2
Un movimiento en la Máquina de Turing depende del sı́mbolo explorado por
la cabeza de la cinta y del estado de control finito. De manera sintética se
hace lo siguiente:
1) dependiendo del sı́mbolo explorado por la cabeza lectora/escritora y del
estado en el control finito se cambia de estado,
2) se imprime un sı́mbolo en la celda explorada, reemplazando el sı́mbolo que
ésta contenga y
3) se mueve la cabeza de lectura una celda hacia la izquierda o derecha.
Note que la diferencia entre la máquina de Turing y un autómata finito de doble
vı́a es que la máquina de Turing tiene la habilidad de cambiar los sı́mbolos en
la cinta de entrada.
Formalmente, una máquina de Turing (MT) se denota por:
M = (Q, Σ, Γ, δ, q0 , B, F ),
donde
Q es un conjunto finito de estados,
Γ es un conjunto finito de sı́mbolos, llamado alfabeto de la cinta,
B es un sı́mbolo en Γ, y el sı́mbolo blanco,
Σ es un subconjunto de Γ que no incluye a B, es el alfabeto de sı́mbolos de
entrada,
δ es la función que determina los movimientos de la máquina, es una transformación de Q × Γ a Q × Γ × {L, R} (δ puede estar indefinida para
algunos argumentos),
q0 ∈ Q es el estado inicial,
F ⊆ Q es el conjunto de estados finales.
Una descripción instantánea (DI) de una máquina de Turing M es una expresión α1 qα2 . Aquı́ q ∈ Q, es el estado actual de M ; α1 α2 es una cadena en
Γ∗ y es el contenido de la cinta hasta el sı́mbolo no blanco más a la derecha o
el sı́mbolo de la izquierda de la cabeza, cualquiera que este más a la derecha.
(Observe que el blanco B puede ocurrir en α1 α2 ).
Asumimos que Q y Γ son disjuntos. Finalmente, asumimos que la cabeza de
la cinta explora el sı́mbolo más a la izquierda de α2 , o si α2 = , la cabeza
explora un blanco.
Se define un movimiento en M como: sea X1 X2 · · · Xi−1 qXi · · · Xn una DI. Se
supone que δ(q, Xi ) = (p, Y, L), si i − 1 = n, entonces se considera a Xi como
3
Curso Básico de Computación
B. Si i = 1 entonces no es posible realizar el movimiento a la izquierda ası́
que no hay DI siguiente porque la cabeza de la cinta no tiene permitido desprenderse del fin izquierdo de la cinta. Si i > 1, entonces escribimos
1) X1 X2 · · · Xi−1 qXi · · · Xn X1 X2 · · · Xi−2 pXi−1 Y Xi+1 · · · Xn
Sin embargo, si cualquier sufijo de Xi−1 Y Xi+1 · · · Xn es completamente blanco
entonces el sufijo se borra en (1).
M
Alternativamente si δ(q, Xi ) = (p, Y, R) entonces escribimos:
2) X1 X2 · · · Xi−1 qXi Xi+1 · · · Xn X1 X2 · · · Xi−1 Y pXi+1 · · · Xn
Note que en el caso de i − 1 = n, la cadena Xi · · · Xn es vacı́a, y el lado derecho
de (2) es más largo que el lado izquierdo.
Si dos DI están relacionadas por
, decimos que la segunda resulta de la
primera por un movimiento. Si una DI resulta de otra por un número finito
de movimientos, incluyendo cero movimientos, ellas están relacionadas por el
*
sı́mbolo .
M
M
M
El lenguaje aceptado por M, denotado por L(M ), es el conjunto de las palabras en Σ∗ que causan que M entre a un estado final cuando se colocan al
principio de la cinta de M , con M en el estado q0 , y la cabeza de la cinta
de M en la celda más a la izquierda. Formalmente, el lenguaje aceptado por
M = (Q, Σ, Γ, δ, q0 , B, F ) es
{w | w ∈ Σ∗ , q0 w
*
M
α1 pα2
para algún p ∈ F , y α1 , α2 ∈ Γ∗ }
Dada una MT que reconoce un lenguaje L, asumimos sin perder generalidad
que la M T se para, es decir, no tiene más movimientos, cuando la entrada es
aceptada. Sin embargo, para algunas palabras no aceptadas, es posible que la
MT nunca pare.
Ejemplo: El diseño de una MT que acepte el lenguaje L = {0n 1n | n ≥ 1} es:
inicialmente, la cinta de entrada de M contendrá 0n 1n seguido de un número
infinito de blancos. Repetidamente, M reemplaza el 0 más a la izquierda por
X, mueve hacia la derecha la cabeza de la cinta hasta encontrar el 1 que esté
más a la izquierda, reemplazandolo por Y , luego se mueve a la izquierda para
encontrar la X más a la derecha, entonces mueve la cabeza una celda hacia la
derecha y si encuentra un 0 entonces repite el ciclo. Sin embargo, si cuando
se busca un 1, M encuentra un blanco en su lugar, entonces M se para sin
aceptar su entrada . Si, después de cambiar un 1 por una Y , M no encuentra
más 0’s, entonces M examina que no haya más 1, si no los hay entonces acepta
su entrada.
Sea Q = {q0 , q1 , q2 , q3 , q4 }, Σ = {0, 1}, Γ = {0, 1, X, Y, B}, y F = {q4 }. Informalmente, cada estado representa una declaración o un grupo de declaraciones
en un programa. Al estado q0 se ingresa inicialmente y es el estado previo a
cada reemplazo del 0 más a la izquierda por una X. El estado q1 se usa para
buscar a la derecha, saltando sobre los 0’s y las Y ’s, hasta encontrar el 1 más
a la izquierda. Si M encuentra 1, lo cambia por Y , y entra al estado q2 .
Feliú Sagols Troncoso
Matemáticas-Cinvestav
4
El estado q2 busca a la izquierda una X y entra en el estado q0 cuando lo encuentra, luego se mueve hacia la derecha hasta el 0 ubicado más a la izquierda.
Conforme M busca hacia la derecha en el estado q1 , si B o X aparecen antes de
encontrar un 1, entonces la entrada es rechazada; puede que haya demasiados
0’s o la entrada no esta en 0∗ 1∗ .
El estado q0 tiene otro papel. Si, después del estado q2 se encuentra la X más
a la derecha, existe una Y inmediatamente a su derecha, entonces los 0’s están
agotados. Desde q0 , se explora Y , entra el estado q3 para explorar sobre las
Y ’s y examina que no haya 1’s restantes. Si las Y ’s están seguidas por B, se
entra al estado q4 y la aceptación ocurre; en otro caso, la cadena es rechazada.
La función δ es:
Estado
0
1
X
q0
(q1 , X, R)
−
−
q1
(q1 , 0, R) (q2 , Y, L)
−
q2
(q2 , 0, L)
−
(q0 , X, R)
q3
−
−
−
q4
−
−
−
Estado
q0
q1
q2
q3
q4
Y
B
(q3 , Y, R)
−
(q1 , Y, R)
−
(q2 , Y, L)
−
(q3 , Y, R) (q4 , B, R)
−
−
La siguiente tabla muestra el cálculo de M para la entrada 0011.
q0 0011 Xq1 011
q2 X0Y 1 Xq0 0Y 1
XXq2 Y Y
Xq2 XY Y
XXY Y q3 XXY Y Bq4
X0q1 11
XXq1 Y 1
XXq0 Y Y
Xq2 0Y 1
XXY q1 1
XXY q3 Y
7.3 Lenguajes computables y funciones
Un lenguaje que es aceptado por una máquina de Turing se dice recursivamente
enumerable (r.e.). El término “enumerable” deriva del hecho de que precisamente estos lenguajes tienen cadenas que pueden ser enumeradas (listadas)
por la máquina de Turing. La clase de los lenguajes r.e es muy amplia e incluye propiamente a los LLC.
La clase de lenguajes r.e. incluye algunos lenguajes para los cuales no se puede
determinar mecánicamente su pertenecia. Si L(M ) es tal lenguaje, entonces
cualquier máquina de Turing que reconozca a L(M ) falla y se detiene con alguna entrada que no está en L(M ). Si w ∈ L(M ), M eventualmente se para
con la entrada w. Sin embargo, mientras M se mantenga en ejecución, puede
que en algún momento pare y acepte su entrada o pueda que se mantenga ası́
por siempre.
Es conveniente distinguir una subclase de los conjuntos r.e. llamada conjuntos
recursivos, los cuales son los lenguajes aceptados por al menos una máquina
de Turing que se para con todas las entradas.
5
Curso Básico de Computación
La máquina de Turing como un medio
para evaluar funciones enteras
La máquina de Turing puede verse como un medio para evaluar funciones de
los enteros a los enteros. El método tradicional consiste en representar a los
enteros en base 1; ası́ el entero i ≥ 0 se representa por la cadena 0i . Si una
función tiene k argumentos, i1 , i2 , ..., ik , entonces estos enteros se colocan inicialmente en la cinta separados por 1’s: 0i1 10i2 1 · · · 10ik .
Si la MT se para y la cinta contiene 0m para algún m, entonces se dice que
f (i1 , i2 , ..., ik ) = m, donde f es la función de k argumentos calculados por
esta máquina de Turing. Note que una máquina de Turing puede calcular
una función de un argumento, una función diferente de dos argumentos, y ası́
sucesivamente. También note que si la MT M calcula la función f con k argumentos, entonces f no necesariamente tiene un valor para todas las diferentes
k-tuplas de enteros i1 , i2 , ..., ik .
Si f (i1 , i2 , ..., ik ) está definida para todas las i1 , i2 , ..., ik , entonces se dice que
f es una función recursiva total. Una función f (i1 , i2 , ..., ik ) calculada por la
MT se llama función recursiva parcial. En este sentido, las funciones recursivas parciales son análogas a los lenguajes r.e., las funciones recursivas totales
corresponden a los lenguajes recursivos. Todas las funciones aritméticas sobre
n
enteros, como la multiplicación, n!, 22 son funciones recursivas totales.
Ejemplo: La sustracción propia
se define como m − n para m ≥ n, y 0
para m < n. La MT M = ({q0 , q1 , ..., q6 }, {0, 1}, {0, 1, B}, δ, q0, B, {q6 }) se
define como: se inicia con 0m 10n en la cinta, se para con 0m n . M reemplaza
repetidamente el primer 0 por blanco, entonces busca a la derecha un 1 seguido
de un 0 y cambia el 0 por el 1. Luego, M se mueve hacia la izquierda hasta
encontrar un blanco, se mueve hacia la derecha y entonces repite el ciclo. La
repetición termina si
i) Al buscar hacia la derecha un 0, M encuentra un blanco. Entonces, los
n 0’s en 0m 10n han sido todos cambiados por 1’s, y n + 1 de los m 0’s
fueron cambiados por B. M reemplaza los n + 1 1’s por un 0 y n B’s,
quedando m − n 0’s de la cinta.
ii) Comenzando el ciclo, M no encontró un 0 para cambiarlos por un blanco,
porque
los primeros m 0’s ya fueron cambiados. Entonces n ≥ m, ası́
m n = 0. M reemplaza el resto de todos los 1’s y 0’s por B.
La función δ se describe como:
1. δ(q0 , 0) = (q1 , B, R)
Comienza el ciclo. Reemplaza el primer 0 por el B.
2. δ(q1 , 0) = (q1 , 0, R)
δ(q1 , 1) = (q2 , 1, R)
Busca en la derecha, búscando al primer 1.
Feliú Sagols Troncoso
Matemáticas-Cinvestav
6
3. δ(q2 , 1) = (q2 , 1, R)
δ(q2 , 0) = (q3 , 1, L)
Busca en la derecha al primer 0 que aparezca después de un 1. Cambia
ese 0 por 1.
4. δ(q3 , 0) = (q3 , 0, L)
δ(q3 , 1) = (q3 , 1, L)
δ(q3 , B) = (q0 , B, R)
Se mueve hacia la izquierda hasta encontrar el primer blanco. Entra al
estado q0 para repetir el ciclo.
5. δ(q2 , B) = (q4 , B, L)
δ(q4 , 1) = (q4 , B, L)
δ(q4 , 0) = (q4 , 0, L)
δ(q4 , B) = (q6 , 0, R)
Si en el estado q2 aparece un sı́mbolo B antes de un 0, se tiene la
situación (i) que se describió antes. Entra al estado q4 y se mueve hacia
la izquierda, cambiando todos los 1’s por B’s hasta encontrar a B. Esta
B se cambia de regreso a 0, se entra al estado q6 , y M se detiene.
6. δ(q0 , 1) = (q5 , B, R)
δ(q5 , 0) = (q5 , B, R)
δ(q5 , 1) = (q5 , B, R)
δ(q5 , B) = (q6 , B, R)
Si en el estado q0 aparece un 1 en lugar de un 0, el primer bloque de 0’s
ha sido consumido, como en la situación (ii) anterior. M entra al estado
q5 para borrar el resto de la cinta, entonces entra al estado q6 y se para.
Un cálculo simple de M con la entrada 0010 es:
q0 0010 Bq1 010 B0q1 10 B01q2 0
B0q3 11 Bq3 011 q3 B011 Bq0 011
BBq1 11 BB1q2 1 BB11q2 BB1q4 1
BBq4 1 Bq4 B0q6
Con la entrada 0100, M se comporta como:
q0 0100 Bq1 100 B1q2 00 Bq3 110
q3 B110 Bq0 110 BBq5 10 BBBq5 0
BBBBq5 BBBBBq6
7.4 Técnicas para la construcción de
máquinas de Turing
Con el objeto de describir construcciones complicadas de la máquina de Turing
es importante contar con herramientas conceptuales de “alto nivel”.
7
Curso Básico de Computación
Almacenamiento en el control finito
El control finito puede ser usado para almacenar una cantidad finita de información. Ası́, cada estado se escribe como un par de elementos, uno que ejerce
el control y el otro almacena un sı́mbolo.
Ejemplo: Considere una máquina de Turing M que mira el primer sı́mbolo de
entrada, lo registra en su control finito, y verifica que el sı́mbolo no aparezca
en otra parte de la entrada. Note que M acepta un conjunto regular, pero M
nos sirve para propósitos de demostración:
M = (Q, {0, 1}, {0, 1, B}, δ, [q0, B], B, F )
donde Q es {q0 , q1 } × {0, 1, B}. Es decir, Q consiste de los pares [q0 , 0],
[q0 , 1],[q1 , 0],[q1 , 1] y [q1 , B]. El conjunto F es {[q1 , B]}. La intención es que el
primer componente de un estado de control esté en acción, mientras el segundo
componente “recuerde” un sı́mbolo.
Se define δ como
1. a) δ([q0 , B], 0) = ([q1 , 0], 0, R),
b) δ([q0 , B], 1) = ([q1 , 1], 1, R),
Inicialmente, q0 es el componente de control del estado, y M se mueve
hacia la derecha. Los primeros componentes de los estado de M se
convierten en q1 , y el primer sı́mbolo de entrada es almacenado en la
segunda componente.
2. a) δ([q1 , 0], 1) = ([q1 , 0], 1, R),
b) δ([q1 , 1], 0) = ([q1 , 1], 0, R),
Si M tiene un 0 almacenado y ve un 1 o viceversa, entonces M continua
moviendose hacia la derecha.
3. a) δ([q1 , 0], B) = ([q1 , B], B, L),
b) δ([q1 , 1], B) = ([q1 , B], B, L),
M entra al estado final [q1 , B] si se alcanza un sı́mbolo blanco sin haber
encontrado el primero una segunda copia del sı́mbolo más a la izquierda.
Si M alcanza un blanco en el estado [q1 , 0] o [q1 , 1], es aceptado. Para el estado
[q1 , 0] y el sı́mbolo 0 o para el estado [q1 , 1] y el sı́mbolo 1, δ no está definida.
Ası́ si M encuentra sı́mbolos en la cinta almacenados, M se para sin aceptar.
En general, podemos permitir que el control finito tenga k componentes y todas, excepto una, almacenen información.
Múltiples pistas
Feliú Sagols Troncoso
Matemáticas-Cinvestav
8
Podemos imaginar que la cinta de la máquina de Turing está dividida en k
pistas, para algún k finito. Por ejemplo, para k = 3 estamos hablando de una
división como la que se muestra en la siguiente figura
c
B
B
1
B
1
0
B
0
1
B
0
1
1
1
1
0
0
1
1
1
$
B
B
B
B
B
B
B
B
...
Control
Finito
Es decir, bajo este esquema los sı́mbolos en la cinta son considerados como un
k-tuplas con un componente por cada pista.
Ejemplo: La cinta de la figura anterior pertenece a una máquina de Turing
que toma una entrada binaria más grande que 2, la escribe en la primera
pista, y determina si es un primo. La entrada aparece rodeada por ç y $ en la
primera pista. Ası́, las entradas permitidas son [ c ,B, B], [0, B, B], [1, B, B],
y [$,B, B]. Estos sı́mbolos pueden ser identificados con c , 0, 1 y $, respectivamente, cuando se examina como entrada. El sı́mbolo blanco es identificado
por [B, B, B].
Para probar si esta entrada es un primo, la MT primero escribe el número
dos en binario sobre la segunda pista y copia la primer pista en la tercera.
Entonces la segunda pista es substraı́da, tantas veces como sea posible, de la
tercera pista, efectivamente se divide la tercera pista por la segunda y deja el
resto.
Si el resto es 0, el número en la primera pista no es un primo. Si el resto no
es cero, se incrementa en uno el número de la segunda pista. Si la segunda es
igual a la primera, el número en la primera pista es primo, porque no se puede
dividir por cualquier otro número propiamente situado entre 1 y el mismo. Si
el segundo es menor que el primero, toda la operación se repite para el nuevo
número de la segunda pista.
En la figura anterior, la MT prueba si 47 es primo. La MT divide por 5, ya
que el 5 es substraı́do dos veces, aparece el 37 en la tercera pista.
Poniendo marcas de verificación sobre
los sı́mbolos
Poner marcas de verificación sobre los sı́mbolos es un truco útil para visualizar
como una MT reconoce lenguajes definidos por cadenas repetidas, tales como:
{ww | w ∈ Σ∗ }
{wcy | w, y ∈ Σ∗ , w 6= y}
o
9
Curso Básico de Computación
{ww R | w ∈ Σ∗ }.
Es también útil cuando la longitud de las subcadenas deben ser comparadas,
como en los lenguajes
{ai bi | i ≥ 1}
o
{ai bj ck | i 6= j o j 6= k}
√
Se introduce una pista extra en la cinta que tenga blancos o
(la marca de
√
verificación). La marca
aparece cuando la MT considera el sı́mbolo que
aparece bajo la marca es una de sus comparaciones.
Ejemplo: Considere una máquina de Turing M = (Q, Σ, Γ, δ, q0 , B, F ), la cual
reconoce el lenguaje {wcw | w ∈ (a + b)+ }. Sea
Q = {[q, d] | q = q1 , q2 , ..., q9 ; d = a, b, o B}
La segunda componente del estado se usa para almacenar un sı́mbolo de la
entrada,
Σ = {[B, d] | d = a, b, o c}
El sı́mbolo de entrada [B, d] se identifica con d. Recuerde que dos “pistas” son
herramientas conceptuales, es decir, [B, d] es otro “nombre” de d:
√
Γ = {[X, d] | X = B o ; d = a, b, c, o B}
q0 = [q1 , B];
F = {[q9 , B]};
[B, B] es identificado con B, sı́mbolo blanco. Para d = a o b y e = a o b se
define δ como:
√
1) δ([q1 , B], [B, d]) = ([q2 , d], [ , d], R)
M busca el sı́mbolo explorado en la cinta, almacena el sı́mbolo en el
control finito, y se mueve hacia la derecha.
2) δ([q2 , d], [B, e]) = ([q2 , d], [B, e], R)
M continua moviendose hacia la derecha, mira hacia c.
3) δ([q2 , d], [B, c]) = ([q3 , d], [B, c], R)
Al encontrar c, M entra a un estado con la primer componente q3 .
√
√
4) δ([q3 , d], [ , e]) = ([q3 , d], [ , e], R)
M se mueve hacia la derecha sobre sı́mbolos que tengan marcas de verificación.
√
5) δ([q3 , d], [B, d]) = ([q4 , B], [ , d], L)
M encuentra un sı́mbolo sin marca de verificación. Si tal sı́mbolo es
igual al sı́mbolo almacenado en el control finito. M le pone la marca de
verificación y comienza a moverse hacia la izquierda. Si los sı́mbolos son
diferentes, M se para sin aceptar su entrada. M también se para si en
el estado q3 , alcanza [B, B] antes de encontrar un sı́mbolo sin marcas de
verificación.
Feliú Sagols Troncoso
Matemáticas-Cinvestav 10
√
√
6) δ([q4 , B], [ , d]) = ([q4 , B], [ , d], L)
M se mueve hacia la izquierda sobre sı́mbolos con marcas de verificación.
7) δ([q4 , B], [B, c]) = ([q5 , B], [B, c], L)
M encuentra el sı́mbolo c.
8) δ([q5 , B], [B, d]) = ([q6 , B], [B, d], L)
Si el sı́mbolo inmediato a la izquierda de c no tiene marca de verificación.
M continúa hacia la izquierda para encontrar el sı́mbolo con marca de
verificación más a la derecha.
9) δ([q6 , B], [B, d]) = ([q6 , B], [B, d], L)
M continúa a la izquierda.
√
√
10) δ([q6 , B], [ , d]) = ([q1 , B], [ , d], R)
M encuentra un sı́mbolo con marca de verificación y se mueve hacia la
derecha para continuar con otro sı́mbolo para la comparación. El primer
componente del estado se convierte otra vez en q1 .
√
√
11) δ([q5 , B], [ , d]) = ([q7 , B], [ , d], R)
M podrı́a estar en el estado [q5 , B] inmediatamente después de cruzar
c moviendose hacia la izquierda (ver regla 7). Si un sı́mbolo con marca
de verificación aparece inmediatamente a la izquierda de c, todos los
sı́mbolos a la izquierda de c tienen marcas de verificación. M debe probar
si todos los sı́mbolos a la derecha tienen marcas de verificación. Si es
ası́, ellos deben haber sido comparados propiamente con los sı́mbolos a
la izquierda de c, ası́ M aceptará su entrada.
12) δ([q7 , B], [B, c]) = ([q8 , B], [B, c], R)
M se mueve hacia la derecha sobre c.
√
√
13) δ([q8 , B], [ , d]) = ([q8 , B], [ , d], R)
M se mueve hacia la derecha sobre los sı́mbolos con marcas de verificación.
√
14) δ([q8 , B], [B, B]) = ([q9 , B], [ , B], L)
Si M encuentra [B, B], el blanco, se para y la acepta. Si M encuentra
un sı́mbolo sin marca de verificación cuando su primer componente del
estado es q8 , se para sin aceptarla.
Corrimientos
Una máquina de Turing puede hacer un espacio en su cinta para mover todos
los sı́mbolos no blancos a un número finito de celdas hacia la derecha. Para
hacer esto, la cabeza de la cinta hace una excursión a la derecha, repetidamente
almacena los sı́mbolos leı́dos en el control finito y los reemplaza por sı́mbolos
leı́dos de celdas de la izquierda. La MT pueden entonces regresar a las celdas
11
Curso Básico de Computación
vacantes e imprimir los sı́mbolos escogidos. Si el espacio es suficiente, puede
empujar bloques de sı́mbolos a la izquierda de manera similar.
Ejemplo: Construir una parte de la MT M = (Q, Σ, Γ, δ, q0 , B, F ), la cual
puede ocasionalmente necesitar mover dos celdas de sı́mbolos no blancos a la
derecha. Suponemos que la cinta de M no contiene blancos entre no blancos,
ası́ que cuando se alcance un blanco se para el proceso de moverse. Supongamos que Q contiene estados de la forma [q, A1 , A2 ] para q = q1 o q2 , y
A1 , A2 ∈ Γ. Sea X un sı́mbolo especial no usado por M excepto en el proceso
de corrimiento. M comienza el proceso de corrimiento en el estado [q1 , B, B].
Las partes relevantes de la función δ son:
1) δ([q1 , B, B], A1 ) = ([q1 , B, A1 ], X, R) para A1 ∈ Γ − {B, X}.
M almacena el primer sı́mbolo leido en la tercera componente del estado.
X se imprime sobre la celda explorada, y M se mueve hacia la derecha.
2) δ([q1 , B, A1 ], A2 ) = ([q1 , A1 , A2 ], X, R) para A1 , A2 ∈ Γ − {B, X}.
M mueve el sı́mbolo de la tercera componente a la segunda componente,
almacena el sı́mbolo que comienza a leer en la tercera componente, imprime X y se mueve hacia la derecha.
3) δ([q1 , A1 , A2 ], A3 ) = ([q1 , A2 , A3 ], A1 , R) para A1 , A2 , A3 ∈ Γ − {B, X}.
Ahora M repetidamente lee el sı́mbolo A3 , lo almacena en la tercera
componente del estado, mueve el sı́mbolo que previamente estaba en
la tercera componente, A2 , a la segunda componente, deposita la segunda componente previa, A1 , en la celda explorada, y se mueve hacia
la derecha. Ası́, un sı́mbolo se deposita en dos celdas a la derecha de su
posición original.
4) δ([q1 , A1 , A2 ], B) = ([q1 , A2 , B], A1 , R) para A1 , A2 ∈ Γ − {B, X}.
Cuando se ve un blanco en la cinta, los sı́mbolos almacenados son depositados en la cinta.
5) δ([q1 , A1 , B], B) = ([q2 , B, B], A1 , L)
Después de que todos los sı́mbolos son depositados, M cambia la primer
componente del estados a q2 y se mueve hacia la izquierda para encontrar
un X, el cual marca la celda vacante más a la derecha.
6) δ([q2 , B, B], A) = ([q2 , B, B], A, L) para A ∈ Γ − {B, X}.
M se mueve hacia la izquierda hasta encontrar a X. Cuando se encuentra
X, M transfiere el control a un estado donde el autómata reanuda sus
funciones.
Subrutinas
Como en la programación, un diseño “modular o “de arriba a abajo” se facilita al emplear subrutinas para definir procesos elementales. Una máquina
Feliú Sagols Troncoso
Matemáticas-Cinvestav 12
de Turing puede simular cualquier tipo de subrutinas encontradas en lenguajes
de programación, incluyendo procesos recursivos y cualquier mecanismo conocido para transferir parámetros.
Aquı́ sólo vamos a describir el uso de subrutinas sin parámetros y no recursivas, pero aún éstas son herramientas en extremo poderosas.
La idea general es escribir parte de un programa de una MT como una subrutina; el diseño tiene un estado inicial designado y un estado de retorno
también designado el cual temporalmente no tiene definidos movimientos y
que se usa para efectuar el regreso a la rutina que lo ha invocado. Para
diseñar una MT que “invoque” a la subrutina, se construye un conjunto nuevo
de estados para la subrutina, y se especifica el movimiento al estado de retorno. La llamada se lleva a cabo ingresando al estado inicial de la subrutina,
y el regreso se lleva a cabo mediante el movimiento al estado de retorno.
Ejemplo: El diseño de una MT M que implemente la función “multiplicación”
recursiva total es: M comienza con 0m 10n en la cinta y termina con 0mn rodeados por blancos. La idea general es colocar un 1 después de 0m 10n y entonces
copiar el bloque de n 0’s sobre la parte final de la derecha m veces, borrando en cada paso uno de los m 0’s. El resultado es 10n 10mn . Finalmente se
borra el prefijo 10n 1, y se deja 0mn . El corazón del algoritmo es la subrutina
COPIA, que comienza con la DI 0m 1q1 0n 10i y eventualmente genera una DI
0m 1q5 0n 10i+n . COPIA es definida en la siguiente tabla:
q1
q2
q3
q4
0
(q2 , 2, R)
(q2 , 0, R)
(q3 , 0, L)
1
(q4 , 1, L)
(q2 , 1, R)
(q3 , 1, L)
(q5 , 1, R)
2
B
(q3 , 0, L)
(q1 , 2, R)
(q4 , 0, L)
En el estado q1 , y con 0 bajo la cabeza de la cinta, M cambia a el 0 a 2 y
entra al estado q2 . En el estado q2 , M mueve la cabeza de la cinta hacia la
derecha, hasta alcanzar el siguiente sı́mbolo blanco, cambia a este sı́mbolo por
0, e inicia el siguiente movimiento hacia la izquierda en el estado q3 . En el
estado q3 , M mueve la cabeza de la cinta hacia la izquierda hasta encontrar
el 2. Al alcanzarlo, entra al estado q1 y el proceso se repite hasta encontrar el
1, que indica que el proceso de copiar está completo. El estado q4 se usa para
convertir los 2 en 0’s, y la subrutina para en q5 .
Para completar el programa de multiplicación, se añaden estados para convertir la DI inicial q0 0m 10n en B0m−1 1q1 0n 1. Es decir, necesitamos las reglas
δ(q0 , 0) = (q6 , B, R),
δ(q6 , 0) = (q6 , 0, R),
δ(q6 , 1) = (q1 , 1, R).
Se necesitan algunos estados adicionales para convertir la DI B i 0m−i 1q5 0n 10ni
en
B i+1 0m−i−1 1q1 0n 10ni , que prepara el entorno para volver a invocar a COPIA,
y verifica si i = m, es decir, si todos los m 0’s fueron borrados. En caso que
13
Curso Básico de Computación
i = m, se borra el prefijo 10n 1 y el cálculo se detiene en el estado q12 . Los
movimientos son:
q5
q7
q8
q9
q10
q11
0
(q7 , 0, L)
1
2
B
(q8 , 1, L)
(q9 , 0, L)
(q9 , 0, L)
(q11 , B, R)
(q10 , B, R)
(q0 , B, R)
(q11 , B, R)
(q12 , B, R)