![Page 1: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/1.jpg)
5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos.
5.1 Esquemas de representación de Máquinas de Turing.5.2 Propiedades de cierre.5.3 Codificación de Máquinas de Turing.5.4 Un lenguaje no recursivamente enumerable: Lenguaje diagonal.5.5 Un lenguaje rcursivamente enumerable no recursivo: Lenguaje Universal.
![Page 2: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/2.jpg)
x SI
NOM
M. T. Aceptora que se detiene para todas las entradas:
Máquina de Turing Generadora x
M
Máquina de Turing que utiliza a otra Máquinas de Turing como subrutina:x SI
NOSTART
M
x SI
M
Máquina de Turing Aceptora que puede no deternerse para alguna entrada:
5.1 Esquemas de representación de Máquinas de Turing
![Page 3: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/3.jpg)
5.2 Propiedades de cierre1. La clase de los Lenguajes Recursivamente Enumerables es cerrada bajo UNIÓN.
M1
M2
x x
x
SI
SI
SI
M
2. La clase de los Lenguajes Recursivos es cerrada bajo la operación UNIÓN.
M1
M2
x x
x
SI
SI
SI
NONO
NO
STARTM
L1 L0 M1: L(M1) = L1
L2 L0 M2: L(M1) = L2
L(M) = L1 L2
L1 LR M1: L(M1) = L1
L2 LR M2: L(M2) = L2
L(M) = L1 L2
![Page 4: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/4.jpg)
3. La clase de los Lenguajes Recursivos es cerrada bajo la COMPLEMENTACIÓN
M
xx SI SI
NONO
M
4. Un Lenguaje es Recursivo si y solo si él y su complementario son Recursivamente Enumerables.
M1
x x SI
NO
SI
M
L LR M: L(M) = L
L(M) = L
L LR M1: L(M1) = L
a) L LR L L0
L(M) = L(M1) = L L L0
b) L LR L L0
![Page 5: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/5.jpg)
M1
1M
x x
x
SI SI
M
NOSI
b) L, L L0 L LR
L L0 M1: L(M1) = L
L L0 M1: L(M1) = L
L(M) = L(M1) = L y M se detiene siempre L LR
Ejercicio
M1
M2
x x
x
SI
SI
SI
NO
NO
NO
STARTM
b) L1, L2 LR L1 L2 LR
![Page 6: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/6.jpg)
A partir de 4, dado cualquier par L, L siempre se dará una de las tres posibilidades
LR
L0L, L
L, L
L, L
Una forma de demostrar que un lenguaje no es recursivamente enumerable esdemostrar que su complementario es r.e. no recursivo.
![Page 7: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/7.jpg)
5. La clase de los Lenguajes Recursivos es cerrada bajo INTERSECCIÓN.
M1
M2
x x
x
SI
SI
SI
NONO
NO
STARTM
6. La clase de los Lenguajes Recursivamente Enumerables es cerrada bajo la INTERSECCIÓN.
M1
M2
x x
x
SI SI
SISTART
M
L1 LR M1: L(M1) = L1
L2 LR M2: L(M2) = L2
L(M) = L(M1) L(M2) = L1 L2
L1 L0 M1: L(M1) = L1
L2 L0 M2: L(M2) = L2
L(M) = L(M1) L(M2) = L1 L2
![Page 8: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/8.jpg)
7. La clase de los Lenguajes Recursivos es cerrada bajo la CONCATENACIÓN.
M1
M2
x1 x
x
SI SI
SISTART
M
NO
Ax2
NO
NO
*
NO
x x
x
SI
START
L1 LR M1: L(M1) = L1
L2 LR M2: L(M2) = L2
x L1 L2 x = x1 x2, x1 L1, x2 L2
Funcionamiento de M:• El módulo A divide x en dos mitades x1 y x2 comenzando por x1 = y x2 = x.• La primera mitad se pasa a M1, la segunda posiblemente a M2.• Cada vez que se vuelve a activar A, | x1 | aumenta una unidad hasta x1 = x• Si ninguna partición devuelve SI, el módulo A activa NO.
![Page 9: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/9.jpg)
5.3 Codificación de Máquinas de Turing.
Objetivo: Codificar una M.T. con {0,1}.Sup L (0+1)* rec. enumerable M con = {0, 1, B} tal que L = L(M).Sea M = ({q1, q2,..., qn}, {0, 1}, {0, 1, B}, , q1, B, {q2})
Codificación de un movimiento Sea (qi, Xj) = (qk, Xl, Dm) con
1 i, k n1 j, l 31 m 2
X1 = 0X2 = 1X3= B
D1 = LD2 = R
Se codifica de forma unívoca como 0i10j10k10l10m
Una M.T. se codifica como111código111código211...11códigor111
Una M.T. puede tener varios códigos, pero la decodificación es única.
A una codificación de una M.T M le llamamos <M>El par (máquina M, entrada w) lo denominamos < M, w>
![Page 10: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/10.jpg)
5.4 Un lenguaje no recursivamente enumerable: Lenguaje diagonal.
Se emplea el mismo argumento que para demostrar que el conjunto de las funcionesf : N {0,1} no es numerable.Si lo fuera, se tendría A = {f1, f2, f3, ...}. Construimos f: f (i) = fi (i) + 1(mod 2).Si f A se tendría f = fj y sin embargo f (j) fj (j).Supongamos una tabla infinita en la que:
• En la primera columna se colocan las palabras de (0 + 1)* en orden canónico.• En la primera fila índices de M.T. • (i, j) = 1 si la palabra i es aceptada por la máquina que se codifica en binario como j.• (i, j) = 0 si la palabra i no es aceptada por la máq. que se codifica en binario como j.
1 2 3 4 5 6 ...1 234
palabras de (0 + 1)*
en orden canónico
números que en binario son
códigos de M.T. (no todos)
![Page 11: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/11.jpg)
Consideramos la diagonal de la tabla anterior y construimos
Ld = {wi : wi L(Mi)}
- Si (i, i) = 0 wi Ld - Si (i, i) = 1 wi Ld
Ld no es recursivamente enumerable:
-Supongamos que sí lo es M : L(M) = Ld .-En las columnas están todas las M.T. j : Mj = M. Entonces
• Si xj Ld = L(Mj) (j, j) = 0 xj L(Mj) (contradicción)• Si xj Ld = L(Mj) (j, j) = 1 xj L(Mj)
Luego no existe M.T. capaz de reconocer Ld .
Consecuencia Ld es • no recursivamente enumerable• recursivamente enumerable no recursivo
![Page 12: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/12.jpg)
Dados los problemas A y B, decimos que A se reduce a B (A B) si, conocidoun algoritmo que resuelve B, se puede resolver A.
Reducción de un problema a otro.
Si A B entonces A es por lo menos tan duro como B
Ejemplo
AMB. Instancia: G = (N, , P, S) Cuestión: ¿Es G ambigua? Respuesta: Si/No
FIND. Instancia: G = (N, , P, S) Cuestión: Encontrar w L(G): w posee más de un árbol de derivación. Respuesta: w /No
AMB FIND
![Page 13: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/13.jpg)
5.5 Un lenguaje reursivamente enumerable no recursivo: Lenguaje Universal.
Veamos que LU = {< M, w> : w L(M)} es:1. Recursivamente enumerable.2. No Recursivo.
1. Sea M1 la máquina con tres pistas:La 1ª es la cinta de entrada (contiene < M, w> ).La 2ª simula la cinta de M.La 3ª guarde el estado de M.
inicialmente están en blanco
Operaciones que tiene que realizar: - Comprobar que la entrada es correcta. - Inicializar la 2ª cinta con w. - Inicializar la 3ª cinta con 0. (código de q1= estado inicial)
Comportamiento de M1
- Si en la 3ª cinta aparece “00” (cód. de q2= estado final) M1 para y acepta < M, w> .- Si en la 3ª cinta hay 0i y en la segunda 0j, se busca en la 1ª un fragmento 0i10j1...- Si no se encuentra ese fragmento, M1 para y rechaza < M, w> .- Si se encuentra .....
w es aceptada por M < M, w> es aceptada por M1
![Page 14: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/14.jpg)
2. Veamos que LU es no Recursivo.
Sabemos que Ld es • no recursivamente enumerable• recursivamente enumerable no recursivo
Sea Ld = {wi : wi L(Mi)}
Veamos que Ld se puede reducir a LU. (si reconocemos LU, tambien Ld )
Supongamos que M1 : L(M1) = LU y M1 para ante todas las entradas
M1< Mi, wi>S
N
wi L(Mi) wi Ld
wi L(Mi) wi Ld
< Mi, wi> LU
< Mi, wi> LU
Luego si LU fuese recursivo también lo sería Ld (contradicción)
w
conversión
![Page 15: 5. Propiedades de los Lenguajes Recursivamente Enumerables y de los Lenguajes Recursivos. 5.1 Esquemas de representación de Máquinas de Turing. 5.2 Propiedades](https://reader033.vdocumento.com/reader033/viewer/2022061300/54cfe6ac49795911798b4c2f/html5/thumbnails/15.jpg)
• L es un lenguaje de tipo 0 L es recursivamente enumerable
Autómata de memoria acotada linealmente (AMLL):- M.T. no determinista con la entrada enmarcada entre dos símbolos ($ y # por ejemplo).- Los movimientos que hace la cabeza no pueden salirse de los límites.- Las marcas no pueden ser sustituidas.
• L es un lenguaje de tipo 1 L es aceptado por un AMLL
L. R. E. = Tipo 0
L. R.Tipo 1