control de lectura_capitulo 9 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
9.-Indecidibilidad
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
9.-Indecidibilidad
Resumen.
Lenguaje no recursivamente enumerable
Recuerde que un lenguaje L es recursivamente enumerable (RE) si L=L(M)para alguna máquina de Turing M. Además, veremos lenguajes “recursivos” o “decidibles” que no sólo no son recursivamente enumerables, sino que son aceptados por una MT que siempre se detiene, independientemente de si acepta o no. Nuestro objetivo a largo plazo es demostrar la indecibilidad del lenguaje que consta de pares(M,w)tales que:
1. M es una máquina de Turing (codificada adecuadamente en binario) con el alfabeto de entrada{0,1},
2. w es una cadena de ceros y unos, y
3. M acepta la entrada w.
Si este problema con entradas restringidas al alfabeto binario es indecidible, entonces con toda probabilidad el problema más general, en el que la MT puede utilizar cualquier alfabeto, será indecidible.
Enumeración de cadenas binarias
A continuación, necesitamos asignar enteros a todas las cadenas binarias, de modo que cada cadena se corresponda con un entero y que cada entero se corresponda con una cadena. Si w es una cadena binaria, tratamos 1wcomo el entero binario i. Entonces se considera que w es la i-ésima cadena. Es decir,ε es la primera cadena,0 es la segunda, 1 la tercera, 00 la cuarta, 01 la quinta, etc. De forma equivalente, las cadenas se ordenan de acuerdo con la longitud, y las cadenas de la misma longitud se ordenan alfabéticamente. De aquí en adelante, denominaremos w i a la cadena i-ésima.
Códigos para las máquinas de Turing
Nuestro siguiente objetivo es definir un código binario para las máquinas de Turing de modo que cada MT con el alfabeto de entrada {0,1}pueda interpretarse como una cadena binaria. Puesto que ya hemos visto cómo enumerar cadenas binarias, disponemos entonces de un medio de identificación de las máquinas de Turing mediante enteros, y podremos hablar de “la i-ésima máquina de Turing, Mi”. Para representar una MTM=(Q,{0,1},Γ,δ,q1,B,F)como una cadena binaria, primero tenemos que asignar números enteros al estado, los símbolos de cinta y las direcciones L y R.
Bibliografías.
2008 por PEARSON EDUCACIÓN S.A.Ribera del Loira, 2828042 Madrid
Introducción a la teoría de autómatas, lenguajes y computaciónHopcroft, J. E.; Motwani, R.; Ullman, J. D.
Página 1 | 1
Acapulco Gro. 10 de diciembre de 2020