Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página1/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
  1   2   3   4   5   6   7   8   9   ...   31
CAPÍTULO 5 – MÁQUINAS DE TURING
Definición:

La Máquina de Turing es una máquina abstracta de cómputo que tiene la misma potencia que los computadores reales y que otras definiciones matemáticas de lo que se puede computar. Está compuesta por una unidad de control de estados finitos y por una cinta infinita, que se encuentra dividida en casillas. Cada casilla contiene uno de los símbolos de la cinta, de los que existen un número finito. Realiza movimientos basados en su estado actual y en el símbolo de cinta que se encuentra en la casilla a la que señalaba la cabeza de la cinta con alguno de los símbolos de cinta, y mueve la cabeza una posición a la derecha o hacia la izquierda




Máquina de Touring



Ejemplo: Máquina de Turing para reconocer cadenas equilibradas de paréntesis.

1. Estados Internos.


Vamos a estudiar ahora una variante del lenguaje de de Post-Turing que está mucho más cercano a la formulación original de Turing .

desaparece aquí el concepto de instrucción propiamente dicha. En vez de tener una lista de instrucciones s, vamos a suponer un mecanismo que puede estar en distintos estados internos. Este mecanismo, en cada momento, estará examinando una casilla de una cinta infinita lineal totalmente análoga a los programas de Post-Turing.


La combinación del estado interno con el símbolo que s esté examinando en la cinta, da lugar a que la máquina ejecute una determinada acción. Estas acciones pueden ser imprimir un símbolo o pasar a examinar la casilla de la izquierda o de la derecha. Finalmente, después de ejecutar la acción el mecanismo puede cambiar a un nuevo estado.
Usaremos los símbolos q1, q2, q3,….. para representar los estados internos y los símbolos s1,s2,s3.... para representar los símbolos que aparecen en la cinta donde el símbolo s0 representa un blanco ,B.

Por una cuadrupla entenderemos un conjunto ordenado de cuatro símbolos en el que el primer símbolo leído representa un estado interno, el segundo símbolo representa un e símbolo leído en la cinta, el tercero una acción (L ,R , sk , que representan respectivamente moverse a la izquierda , a la derecha o imprimir el símbolo sk) y el cuarto, el estado al que se evoluciona.


Existen tres tipos de cuadruplas, dependiendo de la acción que se ejecute,


  1. q1 sj sk p1,

  2. q1 sj R q1,

  3. q1 sj L q1.

Una máquina de Turing se define entonces como constituida por los siguientes elementos:



  • Un conjunto finito de estados Q ={q1,q2,…,qm}

  • Un estado inicial q1.

  • Un alfabeto C ={s1,s2,…,sn}

  • Un conjunto de cuadruplas, tales que no existen dos cuadruplas que empiecen por el mismo estado y el mismo símbolo. Es decir, una correspondencia unívoca.

δ : Q x (C {B}}---------------à(C {B}) {L ,R}

Estas máquinas de Turing se llaman también máquinas de Turing determinísticas. Cuando la correspondencia – no es unívoca, es decir, dados un estado y un símbolo de la cinta puede haber más de una acción y un estado al que evolucione la máquina, el dispositivo se llama máquina de Turing no derterminística.

Una máquina de Turing funciona de la siguiente forma. Comienza en el estado inicial q1 y con una cierta configuración en la cinta. De acuerdo con el símbolo observado en la cinta, ejecuta una acción y cambia de estado, Así va repitiendo esta misma operación hasta que en un momento dado, no exista ninguna cuadrupla en la máquina que empiece por el estado de la máquina y el símbolo observado. No hay ninguna acción definida para una configuración dada. En ese momento, la máquina de Turing para.
Con las mismas consideraciones respecto a la configuración inicial y final de la cinta se define entonces el concepto de función parcial calculada por una máquina de Turing , M.

Análogamente, se dice que una máquina de Turing M calcula estrictamente una función f definida en un conjunto de cadenas A* si y solo sí calcula f verificando, además



    1. El alfabeto de M es un subconjunto de A

    2. Siempre que M pare, la configuración final tiene la forma

B y


qi
Donde “y” no contiene blancos.

Escribiendo s0= B, s1=1 consideremos la siguiente máquina de Turing :

-el conjunto de estados es {q1, q2, q3}.
-El estado inicial es q1.

-El alfabeto es {1}.

-las cuadruplas son

q1 B R q2

q2 1 R q2

q2 B R q3

q3 1 R q3

q3 B 1 q1

Si comenzamos con la configuración, (x =111)

B 1 1 1


q1
Entonces se produce el siguiente cálculo,

B 1 1 1, B 1 1 1,…, B 1 1 1 B,

q1 q2 q2

B 1 1 1 1, B 1 1 1 1 B, 1 B 1 1 1 1 1

q3 q3 q1

El cálculo termina porque no existe ninguna cuadrupla que comienza por q1 1. Esta máquina de Turing calcula la función f(x)= x + 2, usando notación unaria, en base 1.

Los distintos pasos del cálculo, en los que se muestra el estado de la máquina, los símbolos de la cinta y la casilla actual se llaman configuraciones.
A veces, es interesante y mas claro dar las cuadruplas mediante una tabla de doble entrada e la que a cada estado y a cada símbolo examinado se le haga corresponder una acción y un estado. En la siguiente se expresan las cuadruplas del ejemplo anterior.
Estado

-------------------------------------------------------------------------------

Símbolo q1 q2 q3

B R q2 1 q3 1 q1

1 R q2 R q3
Otra representación que se suele usar en numerosas ocasiones es la de un grafo, en la que los nodos representan los estados y los arcos el símbolo examinado y la acción.

Estos grafos se llaman diagramas de transición de estados.


Hemos introducido un nuevo modelo de cálculo. A continuación demostraremos que es equivalente a todos los anteriores.
Teorema.-Cualquier función parcial calculable por un programa Post-Turing puede calcularse por una máquina de Turing usando el mismo alfabeto.
Demostración.-

Sea P un programa Post-Turing. Supongamos que este programa consiste de las instrucciones I1,….Ik y que los símbolos que aparecen en P son s0, s1,….sn. Construiremos una máquina de Turing M que simule el programa P.

Los estados de M, serán {q1 ,…, qk, qk+1 } uno para cada instrucción de P y otro

Para cuando el programa haya parado. El estado inicial será q1. El alfabeto será el mismo que el de P.

La idea de la demostración es que si el programa de Post-Turing va a ejecutar la instrucción Ii entonces la máquina esté en el estado qi. El estado qk+1 corresponderá a la parada del programa.
Entonces se construyen las cuadruplas de forma que la máquina actúe sobre la cinta de la misma forma que el programa.

Más concretamente, si la instrucción I1 es PRINT sk, entonces se añaden las siguientes cuadruplas,

qi sj sk qi+1 , j=0,1, ….,n

Si la instrucción I es RIGHT, se añaden a M las siguientes cuadruplas,

qi sj R qi+1 , j=0,1, ….,n
Si I es LEFT, se consideran las siguientes cuadruplas

qi sj L qi+1 , j=0,1, ….,n


Finalmente, si I1es IF s GOTO L, sea m el menor número tal que la instrucción I tiene a L como etiqueta, si esta existe. En caso de que no exista instrucción con etiqueta L, se hace m = K+1. Se añade entonces a M la cuadrupla

qi sk sk q,m

asi como las cuadruplas

qii s j s j q,i+1 j != k


Está claro que en estas condiciones, la máquina M funciona exactamente igual que el programa Post-Turing P. ■

Con los resultados del capítulo anterior podemos enunciar también el siguiente teorema.

Teorema.- Sea f una función parcial de m variables parcialmente calculable definida en A * para un alfabeto dado A. Entonces existe una máquina de Turing que calcula f estrictamente.

Es interesante aplicar este teorema al caso en que A = {1}. Entonces, si f(x1 ,..., xm ) es una función parcialmente calculable en N, existe una máquina de Turing que calcula f usando solo los símbolos 1 y B. La configuración inicial correspondiente a los valores x1, …, xm es


B l( x )1 B ….. B l( x )m

qk+1



Y la configuración final cuando f(x ,...,xm ) será

B l[f(x1),…….,f(xm)]

qk+1

A continuación veremos unas máquinas de Turing ligeramente distintas. En vez de tener cuadruplas que definan su funcionamiento, van a tener quintuplas - Va a haber dos tipos de quintuplas:

qi sj sk R q1

qi sj sk L q1

La diferencia está en que estas máquinas de Turing, en cada paso, imprimen un símbolo y, entonces, se mueven hacia la derecha o hacia la izquierda. Es decir, realizan dos acciones, una de imprimir y otra de movimiento- Así, para cada par de estado y símbolo en la cinta, se especifica el símbolo que se imprime, sk , el movimiento (L o R) y el nuevo estado q . A estas máquinas les llamaremos máquinas de Turing de quintuplas. Se puede demostrar el siguiente teorema.

Teorema.- Cualquier función que sea calculada por una máquina de Turing puede calcularse con una máquina de Turing de quintuplas y usando el mismo alfabeto.

Demostración," Sea M una máquina de Turing con estados q1 , . ..,qk y alfabeto {s1 , . . . ,sn } . Construiremos una máquina de Turing de quintuplas de M’ que simule a M. La máquina de Turing tendrá como estados

Q1, q2,………., qk, qk+1,…..,q2k.

Entonces la simulación se hace de la siguiente forma, las cuadruplas

qi sj R q1

se transforman en quintuplas

qi sj sj R q1

que tienen exactamente el mismo efecto. Análogamente, las cuadruplas

qi sj L q1

se transforman en quintuplas

qi sj sj L q1
que tienen también el mismo efecto. Para las cudruplas qi sj sk q1de M, colocamos quintuplas

qi sj sk R qk+1

El problema en este caso es que en estas máquinas de Turing necesitamos realizar movimiento, en este caso lo realizamos a la derecha. Para simular la máquina M, M’ debe de deshacer este movimiento. Para hacer esto pasamos a la máquina al estado K+1, en vez del estado 1, que es el que le correspondería. Entonces se añaden las quintuplas de la forma

qk+1 sj sj L qi , i=1 , …., k ; j=0,1,……, n.

Con lo cual M’ simula exactamente el comportamiento de M.

Finalmente completaremos otro círculo demostrando el siguiente teorema.

Teorema,- Cualquier función parcial que pueda calcularse mediante una máquina de Turing de quintuplas puede calcularse mediante un programa Post-Turing usando el mismo alfabeto.

Demostración. -Sea M una máquina de Turing de quintuplas con estados q1,…….,qk y

Y alfabeto {s1,….sn}. Asociamos con cada estado q una etiqueta A y con cada par q s una etiqueta B . Las etiquetas A se colocan en la primera instrucción del filtro

[A ] IF s0 GOTO B 10

IF s1 GOTO B 11

----------------------

IF sn GOTO B In


Si M contiene la quintupla qi sj sk R qk+1. entonces.

Introducimos un bloque de instrucciones

[Bij ] PRINT SK

RIGHT

GOTO A1


De forma similar, si M contiene la quintupla qi sj sk L qk+1

, introducimos el siguiente bloque de instrucciones:

[Bij ] PRINT SK

LEFT

GOTO A1


Finalmente, si no existe ninguna quintupla de M comenzando por qi sj , introducimos el bloque

[Bij ] GOTO E

Finalmente se construye el programa colocando juntos los filtros y bloques. El orden es irrelevante, excepto que el filtro etiquetado con A debe de ir en primer lugar. Este programa funciona exactamente igual que la máquina de Turing de quintuplas.

Este teorema completa otro círculo de implicaciones del que se deduce el siguiente corolario,



Corolario.- Para una función parcial dada, f, las siguientes condiciones son equivalentes.

1. f puede calcularse mediante un programa Post-Turing.

2. f puede calcularse mediante una máquina de Turing.

3. f puede calcularse mediante una máquina de Turing de

quintuplas.

Ejercicios.-


  1. Sea T una máquina de Touring con las siguientes cuadruplas

q1 B R q2

q2 1 R q3

q3 B R q4

q4 1 B q1

q4 B R q4

Para cada entero x, sea g(x) el número de 1 en la cinta cuando y solo cuando la máquina para. Siendo la configuración inicial una serie de x unos, y la casilla activa la inmediatamente a la izquierda de esta serie. ¿Cual es la función g(x)?

2. Escribir las cuadruplas de una máquina de Turing que calcule la función

1 si es cuadrado perfecto

f(x) =

0 en otro caso



en base 1. Escribir el grafo asociado (diagrama de transición de estados).

3. Dar definiciones precisas de configuración, cálculo y cálculo de una función f por una máquina de Turing M.


  1   2   3   4   5   6   7   8   9   ...   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal