Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página5/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   2   3   4   5   6   7   8   9   ...   31
4. El Problema de la Parada para las Máquinas de Turing

Vamos a demostrar en esta sección que el problema de la parada para una máquina de Turing M no tiene solución. Es decir, no existe ningún algoritmo (expresado en cualquiera de las formas conocidas) para determinar cuando M parará cuando empiece con una entrada dada.


Teorema.- Existe un máquina de Turing K con alfabeto {1} cuyo problema de la parada asociado es irresoluble (indecidible).

Demostración.-

Sea U un conjunto r.e. que no sea recursivo. Por r.e. y según vimos en la sección anterior, existe una máquina de Turing con alfabeto {1} que acepta 1 [1] si y sólo sí xU. Sea K dicha máquina.
Si existiese un algoritmo que nos dijese cuando K para en una entrada dada, este podría usarse para comprobar la pertenencia a U. Y sabemos que tal algoritmo es imposible, ya que U no es recursivo. Por tanto cumple las condiciones del teorema. ■
Este resultado sobre el problema de la parada es un poco más fuerte que el que habíamos demostrado anteriormente. Antes probamos (en lenguaje de máquinas de Turing) que no existe ningún algoritmo que acepte una máquina, una entrada y nos diga si la máquina parará o no parará.

A continuación, veremos otro problema relativo a máquinas de Turing que es también irresoluble. Comenzamos con una máquina de Turing K con alfabeto {l} que tiene un problema de la parada asociado irresoluble. Sean los estados de K, q1,…,qk. Construiremos máquina de Turing K’ añadiendo a K un estado, qk+1 , y las siguientes cuadruplas

qi B B qk+1
para i = 1,2,…,k tales que ninguna cuadrupla de K comienza con q1 B y

q1 1 1 q k+1

para i = 1, 2^ . -. , k cuando ninguna cuadrupla de k comienza por q1. De esta forma, K parará en una entrada dada si y solo sí la máquina K' alcanza el estado q k+1. Podemos concluir entonces el siguiente teorema.

Teorema.- Existe una máquina de Turing con alfabeto {1} y un estado qm tal que no existe ningún algoritmo que pueda determinar si K' alcanzará el estado qm cuando comienza con una configuración dada.

Ejercicios

1. Demostrar que existe una máquina de Turing M tal que no existe ningún algoritmo que pueda determinar si M parará con una cinta completamente blanca en una entrada dada.

2. Demostrar que existe una máquina de Turing M con alfabeto{s1 ,s2 } tal que no existe ningún algoritmo que pueda determinar ante una entrada dada, si esta máquina imprimirá alguna vez el símbolo s .

3. ¿Se podría realizar un programa que siempre pare y tal que aceptase programas en Pascal y nos dijese si están libres o no de bucles infinitos?



5. Máquinas de Turing no Determinísticas

Las máquinas de Turing que hemos visto se llaman también determinísticas. Existe otro tipo de máquinas más generales, llamadas no determinísticas. La diferencia fundamental es que puede haber varias cuadruplas comenzando por la misma pareja de símbolo estado. De esta forma ante una configuración inicial, pueden existir distintos cálculos posibles. No existe una única línea de cálculo. Dada una configuración la máquina puede evolucionar a distintas configuraciones.

Análogamente a las máquinas determinísticas, diremos que una

Configuración



… sj

qi

es terminal si y solo sí no existe ninguna cuadrupla que comience por qi sj , Cuando alcanza una configuración terminal, la máquina se dice que para.

Usaremos el símbolo ├ entre un par de configuraciones para indicar que se puede pasar de una a otra mediante una cuadrupla (un paso de cálculo).

Como ejemplo, consideremos la máquina de Turing no determinística compuesta por as siguientes cuadruplas

q1 B R q2

q2 1 R q3

q2 B B q4

q3 1 R q2

q3 B B q3

q4 B R q4

q4 B B q5


En estas condiciones y comenzando con la entrada 1111, tenemos

B 1 1 1 1 ├ B 1 1 1 1 ├



q1 q2



B 1 1 1 1 ├ B 1 1 1 1 ├

q3 q2



B 1 1 1 1 ├ B 1 1 1 1 B ├

q3 q2



B 1 1 1 1 B

q4


Hasta este momento el cálculo ha sido totalmente determinístico. Sin embargo, en el punto en que lo hemos dejado, tenemos dos opciones posibles: estamos ante una situación no determinística. Tenemos la posibilidad

B 1 1 1 1 B ├ B 1 1 1 1 B



q4 q5


q4


en cuyo momento la máquina para. Pero también tenemos la

posibilidad



B 1 1 1 1 B ├ B 1 1 1 1 B B ├

q4 q4



B 1 1 1 1 B B B ├ ….



q

Sea A = {s1, … ,sn } un alfabeto y sea u A* . Entonces de la máquina de Turing no determinística M se dice que acepta la cadena u si existe una sucesión de configuraciones γ1, γ2, …,γm tal que γ1 es la configuración

s0 u



q1

γm es terminal respecto a M γ1├ γ2├…├γm.

En este caso, la sucesión γ1, γ2, …,γm se llama un cálculo de aceptación de M para u.

Si A es el alfabeto de M, entonces el lenguaje aceptado por M es el conjunto de todas las cadenas u e A que son aceptadas por M.

Claro está, para máquinas determinísticas esta definición es la misma de antes. Sin embargo y es importante hacer notar que en las máquinas de Turing no determinísticas es posible que una cadena u sea aceptada, aunque sea posible tener una sucesión infinita de configuraciones

γ1├ γ2├…├γ3

siendo la primera configuración



s0 u

q1

Es sólo necesario que una de las posibles sucesiones de cálculo conduzca a una configuración terminal. Esto se expresa, a veces, diciendo que " La máquina puede adivinar en cualquier momento el paso correcto entre todos los posibles ".

De esta forma, en el ejemplo anterior, considerando el alfabeto A = {1}, resulta que M acepta la cadena 1111. De hecho el


lenguaje aceptado por M es {l(2n)}.

Como una máquina de Turing es también no determinística, podemos enunciar el siguiente teorema.



Teorema.- Para todo lenguaje L r.e., existe una máquina de Turing M no determinística que acepta el lenguaje L.

La propiedad inversa es también cierta. Todo lenguaje aceptado por una máquina de Turing no determinística será también r.e. Por la tesis de Church-Turing esto debería de ser cierto. Sólo es necesario simular una máquina no determinística M para una entrada u, siguiendo todas las alternativas en cada paso, y dando un valor (p.e. 0), si se alcanza una configuración terminal en una de las posibles ramas. Esto define una función que es, intuitivamente, calculable y cuyo dominio es el lenguaje aceptado por M. La demostración exacta no la vamos a dar.



Ejercicios

1. Sea L el conjunto de todas las palabras del alfabeto {a,b} que contengan al menos dos b consecutivas. Construir una máquina de Turing no determinística que nunca se mueva a la izquierda y que acepte el lenguaje L.


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