Parte 4 Máquinas De Turing
89
1 Parte 4-Máquinas de Turing v. 2.0 Dr. Ricardo Quintero Teoría de la Computación
-
Upload
ricardo-quintero -
Category
Education
-
view
11.590 -
download
2
Transcript of Parte 4 Máquinas De Turing
1
Parte 4-Máquinas de Turing v. 2.0
Dr. Ricardo Quintero
Teoría de la Computación
2
Definiciones básicas
Existen lenguajes bastante sencillos que no son independientes de contexto.Por ejemplo: {anbncn|n≥0} no puede ser reconocido por un ADPND, ya que aunque la pila puede recordar el número de a’s (apilando) para el número de b’s (desapilando), este valor n se pierde cuando se desean contar las c’s.
3
Definiciones básicas
El problema es que en la pila los datos solamente pueden ser consultados en el top y no debajo del mismo. El problema no es la memoria adicional, sino la forma en la que la estamos accesando (su organización).Aunque podríamos considerar múltiples organizaciones de memoria, vamos a discutir la que introduce la Máquina de Turing, que es bastante sencilla pero poderosa.
4
Definiciones básicas
La memoria en una Máquina de Turing tiene las siguientes características: Es una colección de celdas que se extiende
infinitamente en ambas direcciones, es una cinta infinita.
Cada celda es capaz de almacenar un único símbolo.
No existe una celda primera, ni una última y por lo tanto tiene capacidad de almacenamiento infinito.
Los contenidos de las celdas pueden ser accedidos en cualquier orden.
Existe una cabeza de lectura/escritura que puede moverse sobre la cinta y en cada movimiento leerá o escribirá un símbolo.
5
Máquina de Turing (TM)
Una máquina de Turing es una 7-tupla M=(Q,,,s,b,F,), donde: Q es un conjunto finito de estados. es un alfabeto de entrada. es un alfabeto llamado alfabeto de la cinta. sQ es el estado inicial. b es el símbolo blanco (y no está en ). FQ es el conjunto de estados finales o de
aceptación. :QxQXx{L,R} es una función parcial (esto
es, su dominio no es todo Qx) que se llama función de transición.
6
Máquina de Turing
En esta definición el valor inicial de todas las celdas de la cinta es el símbolo b.Generalmente se permite que - {b}. b. Esto es, el alfabeto de entrada es un subconjunto del alfabeto de la cinta, sin incluir el blanco. transforma pares (q,) formados por el estado actual y símbolos de la cinta en ternas (p,t,X), donde p es el estado siguiente, t es el símbolo escrito en la cinta y X es un movimiento de lectura o escritura, que puede ser L o R según que el movimiento sea hacia la izquierda o la derecha.
7
Un movimiento en la Máquina de Turing
En un movimiento de la TM se considerará el símbolo actual sobre la cabeza de lectura/escritura y el estado actual de la misma y la dinámica será la siguiente:1. Cambia de estado.2. Escribe un símbolo sobre la cinta,
reemplazando el que existía previamente.3. Mueve la cabeza de lectura/escritura una celda
a la izquierda o la derecha.
8
Ejemplo de movimiento en la Máquina de Turing
La transición (q1,a)=(q5,b,R) provoca que la TM pase de una configuración:
a b b
Cabeza r/w
Estado interno
q1
A la configuración:b b b
Cabeza r/w
Estado interno
q5
9
Sobre la cadena de entrada y su relación con
la cinta
Como las transiciones dependen únicamente del estado actual y del contenido de la celda sobre la que se encuentra la cabeza de lectura/escritura entonces:
Cualquier cadena de entrada se debe presentar a la TM sobre la
cinta.
10
La TM en JFlap
JFlap nos permite trabajar también con TM. En particular estamos considerando un modelo en el que solamente existe una cinta.La opción será 1-Tape Turing Machine.
11
Ejemplo de TM en JFlap
Ej.- Considere la TM siguiente: Q={q1,q2} ={a,b} ={a,b,b} F={q2} s=q1
(q1,a)=(q1,a,R) (q1,b)=(q1,a,R) (q1,b)=(q2,b,L)
Estudie el archivo Ej0411.TM para su correspondiente TM en JFlap. Introduzca la cadena de entrada abba.
12
Ejemplo de TM en JFlap
Ej.- TM en JFlap:
13
Descripciones Instantáneas de la TM
Existen dos formas comunes de representar la Descripción Instantánea (DI) de una TM.La primera tiene la forma (qi,w1w2) donde: qi es el estado actual. w1 es la cadena de la cinta que precede a la
cabeza r/w. el el símbolo de la cinta sobre el que se
encuentra la cabeza r/w. w2 es la cadena de la cinta que sucede a la
cabeza r/w.
14
Descripciones Instantáneas de la TM
Para el ejemplo anterior, las DI serían: (q1,babba) (q1,abba) (q1,aaba) (q1,aaaa) (q1,aaaab) (q2,aaaa)
15
Descripciones Instantáneas de la TM
La segunda está dada por la cadena:
a1a2...ak-1qiak...an
Que representa a la configuración (qi,waku)
Por tanto, las dos primeras DI anteriores serían: q1abba y aq1bba.
16
Paso de una DI a otra
En cualquiera de los dos casos el paso de una configuración a otra se denota por .Por tanto, para el ejemplo anterior se tendrían en los dos tipos de DI vistos: (q1,babba) (q1,abba) (q1,aaba)
(q1,aaaa) (q1,aaaab) (q2,aaaa)
O bien q1abba aq1bba aaq1ba aaaq1a aaaaq1b
aaaq2a
17
Paso de una DI a otra
Las notaciones * y + tienen el signficado usual de “cero o más” o “uno o más” respectivamente.
18
Ejemplo de TM
Ej.- Considere la TM siguiente: Q={q1,q2, q3} ={a,b} ={a,b,b} F={q3} s=q1 (q1,a)=(q1,a,L) (q1,b)=(q1,b,L) (q1,b)=(q2,b,R) (q2,a)=(q3,a,L) (q2,b)=(q3,b,L) (q2,b)=(q3,b,R)
Esta TM examina la cinta de izquierda hasta que encuentre la primer celda en blanco. Se parará y se colocará sobre el blanco
19
Ejemplo de TM
Ej.- Para aababb se tendría:
(q1,aababb) (q1,aababb) (q1,aababb) (q1,aababb) (q1, baababb) (q2,aababb) (q3, baababb)
o bien
aabq1abb aaq1babb aq1ababb q1aababb q1baababb q2aaababb q3baababb
20
Parada de la TM
Cuando (q,a) está indefinido y la configuración de la TM es (q,w1aw2), es imposible pasar a otra configuración. Se dice que la TM está parada.Puede ser que qF, siendo F el conjunto de estados finales o no. Es importante dar significado a la parada en un estado F.Para simplificar se supondrá que no se define ninguna transición para cualquier estado final.
21
Computación
La secuencia de todos los movimientos que conducen a una TM a una configuración de parada (en un estado de aceptación F o no) se llama computación.
22
Ejemplo de TM
Ej.- Considere la TM siguiente: Q={q1,q2} ={a,b} ={a,b,b} F= s=q1 (q1,a)=(q2,a,R) (q1,b)=(q2,b,R) (q1,b)=(q2,b,R) (q2,a)=(q1,a,L) (q2,b)=(q1,b,L) (q2,b)=(q1,b,L)
23
Ejemplo de TM
Ej.- Si esta TM comienza con la cabeza r/w sobre la a de una cadena de la forma abw, se tiene la siguiente secuencia de movimientos:
q1abw aq2bw q1abw aq2bw ...
Esta TM ha caído en un “ciclo inifinito”, nunca parará. Esta es una situación fundamental en la teoría de las TM.
24
TM que nunca para
Una TM que nunca para es aquella que se describe de la siguiente manera:
(q,w1w2)*
O bienw1qw2*
25
Tarea
Resolver los siguientes ejercicios del libro de texto: 4.1.1, 4.1.3
26
TM como aceptadores de lenguajes
Así como un AF o un ADPND, un TM puede comportarse como un aceptador de un lenguaje.Se coloca la cadena w en la cinta, se sitúa la cabeza de r/w sobre el símbolo del extremo izquierdo de la cadena w y ponemos en marcha la máquina a partir de su estado inicial.Si después de una secuencia de movimientos la TM llega a un estado final y para, entonces w es aceptada.
27
Definición de TM como aceptador de lenguajes
Def.- Sea M=(Q,,,s=q1,b,F,) una TM. Entonces el lenguaje aceptado por M es:
L(M)={w*|q1w*w1pw2 para pF y wi*}
28
TM que acepta el lenguaje a*
Ej.- La siguiente TM acepta el lenguaje regular a*: Q={q1,q2} ={a,b} ={a,b,b} F={q2} s=q1 (q1,a)=(q1,a,R) (q1,b)=(q2,b,R)
29
TM que acepta el lenguaje a* en JFlap
Ej.- La TM que acepta a* en JFlap:
30
Rechazando una cadena que no pertenece a un
lenguaje
Para rechazar una cadena que no es aceptable, hay que evitar que se llegue a un estado final.Otra alternativa para rechazar una cadena es que la TM entre en un “ciclo infinito”.
31
Ejemplo de Rechazo de una cadena mediante un “ciclo
infinito”
Ej.- El archivo Ej0421-2.TM contiene una TM que rechaza las cadenas que no pertenecen a a* mediante “ciclos infinitos”.
32
Ejemplo de lenguaje no independiente del contexto que
acepta una TM
Ej.- El archivo Ej0422.TM contiene una TM que acepta las cadenas que pertenecen al lenguaje {anbn|n≥1} ¿Cuál es la “lógica” de la TM para reconocer este lenguaje?
33
Lenguajes recursivamente enumerables
Los lenguajes aceptados por una TM se les conoce como Lenguajes Recursivamente Enumerables (RE).El término “Enumerable” proviene de que una TM puede listar (enumerar) las cadenas del lenguaje.Los RE es un conjunto de lenguajes bastante grande, que incluye los LIC.
34
Lenguajes recursivamente enumerables
Una TM que acepta un lenguaje no necesita parar para todas sus cadenas de entrada. La única condición es que se pare en un estado de aceptación para aquellas cadenas que pertenezcan al lenguaje.De hecho existen TM que no se paran ante todas las cadenas de ciertos LRE.El subconjunto de lenguajes recursivamente enumerables cuya totalidad de cadenas es aceptada por una TM que para se les llama recursivos.
35
La TM como un modelo abstracto de computadora
Puesto que la TM puede leer y escribir sobre su cinta pueden convertir la entrada en salida. Este es el propósito de las computadoras digitales, de tal manera que una TM es considerado como un modelo abstracto de computadora.La entrada para la TM se forma por todos los símbolos de la cinta que no son blancos.La salida está formada por cualquiera de los símbolos que queden en la cinta cuando la computación termina.
36
Ejemplo de TM como modelo abstracto de
computadora
Ej.- El archivo Ej0422-2.TM es una TM que complementa las cadenas sobre el alfabeto S. Su definición es la siguiente:
Q={q1,q2, q3} ={a,b} ={a,b,b} F={q3} s=q1 (q1,a)=(q1,b,R) (q1,b)=(q1,a,R) (q1,b)=(q2,b,L) (q2,a)=(q2,a,L) (q2,b)=(q2,b,L) (q2,b)=(q3,b,R)
37
La TM como una función de cadena
La TM puede ser considerada como la implementación de una función de cadena f(w)=u cuando se cumple qsw*qfu, donde qs es el estado inicial y qf es un estado final.Por conveniencia y claridad, la cabeza de r/w empezará y terminará sobre el símbolo de las cadenas de entrada y salida que está situado más a la izquierda.
38
Funciones Turing computables
Def.- Una función de cadena f es Turing computable si existe una TM M=(Q,,, q1,b,F,) para la cual q1w*qfu para algún qfF, cuando f(w)=u.
39
La TM como computadora de funciones de enteros
La TM puede ser extender fácilmente para computar funciones de enteros. El siguiente ejemplo ilustra esto.Ej.- Suponga un ={a,b} y se representan los enteros como cadenas de a’s. Esto es, el entero positivo n se representa mediante an. La función suma f(n,m)=n+m podría ser implementada mediante la transformación de la entrada anbam (es decir, se introducen a la TM los dos números enteros, m y n, separados por una b) en la salida an+mb.
(Cont...)
40
La TM como computadora de funciones de enteros
Ej.- (Cont...) La siguiente TM implementa la suma de enteros (Ej0423.TM en JFlap) : Q={q1,q2, q3 , q4 , q5} ={a,b} ={a,b,b} F={q5} s=q1 (q1,a)=(q1,a,R) (q1,b)=(q2,a,R) (q2,a)=(q2,a,R) (q2,b)=(q3,b,L) (q3,a)=(q4,b,L) (q4,a)=(q4,a,L) (q4,b)=(q5,b,R)
41
Construcción de TM
Es posible construir una TM más compleja a partir de TM sencillas.Podemos combinar dos TM permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece.El contenido de la cinta al inicio de la ejecución de la segunda TM está formado por todo lo que dejó la primer TM, y la cabeza de r/w de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.
42
Ejemplo 1 de TM
Ej.- Sea la TM M1 dada por: Q={q1,q2, q3 , q4} ={a} ={a,b} F1={q4} s1=q1 (q1,a)=(q2,a,R) (q1,b)=(q2,b,R) (q2,a)=(q2,a,R) (q2,b)=(q3,b,L) (q3,b)=(q4,b,L) (q3,a)=(q4,a,R)
Esta máquina busca el primer blanco que haya a la derecha de donde ha comenzado y para.
43
Ejemplo 2 de TM
Ej.- Sea la TM M2 dada por: Q={p1,p2} ={a} ={a,b} F2={p2} s2=p1 (p1,a)=(p2,a,R) (p1,b)=(p2,a,R)
Esta máquina escribe una a y para. La a se escribe independiente del contenido actual de la celda.
44
Combinando Ejemplo 1 y Ejemplo 2 de TM
Al combinar M1 y M2 de tal forma que una computación de M1 vaya seguida de una computación de M2, obtenemos un dispositivo que primero busca hacia la derecha el primer blanco y después escribe una a en la celda.Representaremos la combinación de estas dos TM mediante M1M2 para indicar que la computación de M1 va seguida por la computación de M2.
45
Combinación o composición de TM
Def.- Sean M1 y M2 dos TM sobre el mismo alfabeto de entrada y el mismo alfabeto de cinta , donde: M1=(Q1, , , s, b, F1,1) M2=(Q2, , , s, b, F2,2)
Se supone que Q1Q2=. La composición de las TM M1 y M2 es la TM=(Q,,,s,b,F,), que se denota M1M2, donde: (Cont ...)
46
Combinación o composición de TM
Q=Q1Q2
s=s1
F=F2
q,), si qQ1 y 1(q,)(p,,x) pF1
2(q,), si qQ2
(s2,,X), si qQ1 y 1(q,)=(p,,x) pF1
(q,)=
47
Transiciones combinando Ejemplo 1 y 2 de TM
Ej.- Combinando las TM M1 y M2 tendríamos: (q1,a)=(q2,a,R) (q1,b)=(q2,b,R) (q2,a)=(q2,a,R) (q2,b)=(q3,b,L) (q3,b)=(p1,b,L) (q3,a)=(p1,a,R) (p1,a)=(p2,a,R) (p1,b)=(p2,a,R)
Transiciones de M1 que no cambian
Transiciones de M1 que cambian y conectan a M2
Transiciones de M2 que no cambian
Con s=q1 y F={p2}
48
La TM Rb
A la TM del Ejemplo 1 le llamaremos Rb: “Busca el primer blanco que haya a la derecha de la posición actual de la cabeza r/w”:Obviamente la máquina Rb Rb Rb : “Buscaría el tercer blanco que haya a la derecha de la posición actual de la cabeza de r/w”
49
Tabla para Rb
(q,) ≠b =b
q1 (q2,,R) (q2,b,R)
q2 (q2,,R) (q3,b,L)
q3 (q4,,R) (q4,b,R)
50
La TM Lb’
La TM Lb’ será aquella que: “Busca el primer símbolo que no sea blanco que haya a la izquierda de la posición actual de la cabeza r/w”:
51
Tabla para Lb’
(q,) =b ≠b
q1 (q2, b, L) (q2, , L)
q2 (q2, b, L) (q3, , R)
q3 (q4, b, L) (q4, , L)
Con F={q4} y s=q1
52
Combinando Rb y Lb’
Combinando Rb y Lb’ se tiene Rb
Lb’, donde la cabeza de r/w se sitúa sobre el símbolo de la cinta que precede b que hay a la derecha de la posición actual.
53
La TM ‘a’
La TM a será aquella que: “Escriba en la salida un único símbolo a y que permanezca sobre dicha celda”.
54
Tabla para ‘a’
(q,)
q1 (q2, a, R)
q2 (q3, , L)
Con F={q3} y s=q1
55
La TM R
La TM R será aquella que: “Mueve la cabeza de r/w a la derecha. No hace cambios en los símbolos de la cinta”.
56
Tabla para R, con dos estados finales diferentes
Con F={p2 y p3} y s=p1
(p,) =b ≠b
p1 (p2, b, R) (p3, , R)
57
Combinando Lb’ y R con bifurcación
Combinando Lb’ y R se tiene Lb’ R. Suponga que se desea que esta máquina sea seguida por otra que escriba una a si la celda es un blanco o una b si la celda contiene una a. Una bifurcación.Esto se podría se representar mediante el siguiente diagrama.
58
Combinando Lb’ y R con bifurcación
Lb’ R a
b
=b
=a
59
TM que cambia ‘a’ en ‘b’ y visceversa
R b
a
=a
=b
60
TM con múltiples transiciones y movimientos simples de la cabeza de
r/w
R Ra,b,b
R R
61
TM con bifurcación
R b
=aa
Busca hacia la derecha la primer celda que contenga un símbolo que no sea a y escribe una
b en ese lugar.
62
Desplazando una cadena sobre la cinta una celda a la
derecha
Supongamos que se requiere que la cadena a desplazar sea precedida y seguida por blancos.Por tanto, se desea transformar:
bwbEn
bbw
63
Desplazando una cadena sobre la cinta una celda a la
derecha
L2 bRa
bRb
=a
=b
R
=b
RbR
64
La misma máquina anterior: La TM SR
L2 bR≠b
R
=b
RbREl símbolo en bRsignifia que la máquina compuesta “recuerda” el símbolo que ha sido sobreescrito con el b.
Esta máquina de desplazamiento hacia la derecha se denotará SR.
65
Reconociendo {wwI|w} con estados de aceptación y no
aceptación
bRbL Lb
b
=
b
=b
R bb b
=b
Para en un estado de aceptación Para en un estado
de no aceptación
Se empieza con bub y se espera descubrir que u=wwI. La cadena se acepta cuando todos los símbolos de u son eliminados
66
Reconociendo {wwI|w} solamente con estados de aceptación
bRbL Lb
b
=
b
=b
R bb b
=b
Para en un estado de aceptación
Se empieza con bub y se espera descubrir que u=wwI. La cadena se acepta cuando todos los símbolos de u son eliminados. Sólo se tienen
estados de aceptación
67
Tarea
Resolver del libro de texto: 4.3.2, 4.3.3, 4.3.5, 4.3.6, 4.3.8
68
Modificaciones a la TM
Es posible efectuar modificaciones al diseño original de la TM.Muchas de estas modificaciones dan mayor flexibilidad a la TM original para resolver ciertos problemas en particular.Todos estos diseños alternativos tienen la misma potencia computacional que la TM original.
69
TM sin movimiento de cabeza de r/w
Es posible que la función de transición original:
:QxQxx{R,L}se transforme a:
:QxQxx{R,L,S}Donde S significa “permanecer”, es decir, no mover la cabeza de r/w; para obtener una diseño de TM útil para ciertos problemas.
70
Equivalencia con la TM original
Una transición (q,)=(p,’,S) se puede simular con la TM original de la siguiente manera:(q,)=(p’,’,R) y (p’,)=(p,,L) y/o
(q,)=(p’,’,L) y (p’,)=(p,,R) .
71
Ejemplo de TM equivalentes con/sin estado de
“permanecer”
M1 se define con estado de “permanecer”:
(q,) ≠b =b
q1 (q2, , L) (q2, , L)
q2 (q2, , L) (q3, , S)
Con F={q3} y s=q1
72
Ejemplo de TM equivalentes con/sin estado de
“permanecer”
M1 se define sin estado de “permanecer”. Es equivalente:
(q,) ≠b =b
q1 (q2, , L) (q2, , L)
q2 (q2, , L) (q4, , L)
q3 (q3, , R) (q3, b, R)
Con F={q3} y s=q1
73
TM con múltiples pistas
Considere el siguiente tipo de cinta:
b b b
a a b
a a b
. . .. . .
74
TM con múltiples pistas
Tiene cada celda dividida en tres subceldas. Cada celda de la cinta puede considerarse un n-tupla ordenada.En el ejemplo anterior las n-tuplas son: (b,a,a), (b,a,a) y (b,b,b).Por tanto, los movimientos de la máquina dependen del estado y la n-tupla actual.
75
Equivalencia con la TM original
Si es un alfabeto de cinta, una TM que tiene una cinta de k pistas, cada una con alguno de los símbolos de , puede interpretarse como una TM cuyo alfabeto de cinta estuviera formado por todas las k-tuplas sobre .Por ejemplo, si la TM tiene 2 pistas, entonces el alfabeto de cinta es x.
76
TM con múltiples pistas que suma dos números
La siguiente TM suma dos números binarios:
b 1 0 1 b
b 0 1 0 b
b b b b b
. . .. . .
Suma 101 y 010, deja el resultado en la tercer subcelda
77
Función de transición de TM con múltiples pistas que suma dos
números
q1, R), si (b, b, b)
q2, L), si = (b, b, b)
(q1,)=
78
Función de transición de TM con múltiples pistas que suma dos
números
(q2(0,0,b))=(q2,(0,0,0),L)
(q2(0,1,b))=(q2,(0,1,1),L)
(q2(1,0,b))=(q2,(1,0,1),L)
(q2(1,1,b))=(q3,(1,1,0),L)
(q2(b, b,b))=(q4,(b, b,0),S)
(q3(0,0,b))=(q2,(0,0,1),L)
(q3(0,1,b))=(q2,(0,1,0),L)
(q3(1,0,b))=(q2,(1,0,0),L)
(q3(1,1,b))=(q2,(1,1,1),L)
(q2(b, b,b))=(q4,(b, b,1),S)
79
TM con múltiples pistas que suma dos números
La TM sumará los números binarios:
b b 1 0 1 b
b b 0 1 0 b
b 0 1 1 1 b
. . .. . .
Suma 101 y 010, deja el resultado en la tercer subcelda
Operando 1
Operando 2
Resultado
80
Otras modificaciones
Algunas otras modificaciones que se pueden tener incluyen: TM con una cinta infinita en una sola
dirección. TM multicinta. TM multidimensional.
Cualquier computación que se pueda realizar por medio de las nuevas máquinas cae dentro de las categorías de “computable por una TM” y por tanto son mecánicamente computables.
81
TM Universal
Def.- Es una TM que, a partir de una descripción adecuada de una TM M y una cadena de entrada w, simula el comportamiento de M sobre la cadena w.
82
Descripción de la TM M
Su descripción será a partir del alfabeto finito {0,1}.La TM M deberá de tener un único estado de aceptación, por lo que de no ser así deberá de ser transformada para que desde todos los estados de aceptación que tenga exista una transición a este estado.
83
Descripción de la TM M
Se supondrá que el conjunto de estados será Q={q1,q2,...,qn} donde q1 será el estado inicial y q2 el único estado final.
Se supondrá que el alfabeto de la pila será ={1,2,...,m} donde 1 será el blanco.Partiendo de estas suposiciones M estará definida a partir de su función de transición .
84
Función de transición de la TM M
Para codificar la función de transición : Se representará q1 con un 1, q2 con 11 y
así sucesivamente. Igualmente se representará 1 con un 1,
i con i unos y así sucesivamente. El movimiento de la cabeza se
representará así: L con 1 y R con 11.
Usaremos los 0’s como separadores.
85
Función de transición de la TM M
Una transición tal como:(q3,1)=(q4,3,L)
Se presentaría mediante la cadena:011101011110111010
Así, M tendrá una codificación representada por una cadena finita de 0’s y 1’s. Aún más, dada una codificación, es posible también su decodificación.
86
Implementación de la TM Mu
La TM Mu se puede implementar como una TM de tres cintas cuyo alfabeto de entrada contenga 0’s y 1’s.La primer cinta contiene la codificación de M con su cabeza situada sobre el 0 inicial de la cadena de 0’s y 1’s.La segunda cinta contiene la codificación del contenido de la cinta de M con su cabeza sobre el 1 que pertenece a la codificación del símbolo actual.
87
Implementación de la TM Mu
La tercer cinta se usa para guardar el estado actual de M, conteniendo la versión codificada del estado inicial q1 de M rodeado por blancos. La cabeza de r/w se sitúa sobre el primer 1 de la cadena codificada.
88
Funcionamiento de la MU
Mu analiza las cintas segunda y tercera con el de la primer cinta hasta encontrar una transición o hasta agotar todas las posibilidades.Si no se encuentra una transición, Mu para como también lo haría M. En otro caso, Mu se comporta como lo haría M.Si M para con la cadena w, entonces Mu parará cuando tenga la codificación de M y w también.
89
Funcionamiento de la MU
También la cadena final que quede en la segunda cinta de Mu será también la codificación que hubiera quedado en M.Al parar M, Mu puede moverse al único estado de aceptación o no.
