1. No category

1
Curso Básico de Computación
8 Indecibilidad
Ahora se considera la clase de lenguajes recursivos y recursivamente enumerables. El aspecto más interesante de este estudio trata de lenguajes cuyas
cadenas son interpretadas como códigos de instancias de problemas. Considere el problema de determinar si una MT arbitraria acepta la cadena vacı́a.
Este problema se puede formular como un problema de lenguaje codificado por
una MT con cadenas de 0’s y 1’s. El conjunto de todas las cadenas que codifican MT’s que aceptan la cadena vacı́a es un lenguaje que es recursivamente
enumerable pero no recursivo. De esto se concluye que no existen algoritmos
que decidan cuáles MT aceptan cadenas vacı́as y cuales no.
8.1 Problemas
Informalmente se usa la palabra problema para referirse a una pregunta tal
como: “¿Es una GLC ambigua?” En el caso del problema de ambigüedad, una
instancia del problema es una GLC particular. En general, una instancia de
un problema es una lista de argumentos, un argumento por cada parámetro
del problema. Restringimos nuestra atención a problemas con respuesta SiNo e instancias codificadas por cadenas sobre algún alfabeto finito, podemos
transformar la pregunta de si existe un algoritmo para resolver un problema a
si un lenguaje particular es o no recursivo.
Considere el problema de ambiguedad para GLC. Llamemos a la versión SiNo del problema AMB. Una versión más general del problema, llamada FIND,
requiere producir una palabra con dos o más árboles de derivación y responde
“no” en otro caso. Un algoritmo para FIND se puede usar para resolver AMB.
Si FIND produce una palabra w, entonces la respuesta es “sı́”; si FIND contesta “no”, entonces AMB también. Recı́procamente, dado un algoritmo para
AMB se produce un algoritmo para FIND. El algoritmo primero aplica AMB
a la gramática G. Si AMB responde “no” nuestro algoritmo responde “no”. Si
AMB responde“sı́”, el algoritmo sistematicamente comienza a generar todas
las palabras sobre el alfabeto terminal de G. Tan pronto como se genere una
palabra w, se examina para ver si tiene dos o más árboles de derivación. Note
que el algoritmo no comienza a generar palabras a menos que G sea ambigua,
de esta manera se encuentra alguna w y se imprime. Ası́ en efecto se tiene un
algoritmo.
El proceso por el cual se construye un algoritmo para un problema (como
FIND), y usa un supuesto algoritmo para otro (AMB), se llama una reducción
(de FIND a AMB). En general, cuando se reduce el problema A al problema B
se demuestra que B es por lo menos tan difı́cil como A. Ası́, en este caso, como
en muchos otros, el problema Si-No AMB no es más fácil que la versión más
general del problema. Más tarde se probará que no existe un algoritmo para
Feliú Sagols Troncoso
Matemáticas-Cinvestav
2
AMB. Por la reducción de AMB a FIND se concluye que no existe un algoritmo para FIND, ya que la existencia de un algoritmo para FIND implicarı́a
la existencia de un algoritmo para AMB, y serı́a una contradicción.
Trabajemos con la codificación de la gramática G. Dado que cada máquina
de Turing tienen un alfabeto fijo, no podemos trabajar directamente con la
notación G = (V, T, P, S). Podemos codificar este tipo de 4-tupla utilizando
cadenas binarias como sigue. A los metası́mbolos de la 4-tupla, esto es, los
paréntesis izquierdo y derecho, los corchetes, la coma y el →, son codificados
por 1, 10, 100, ...,105 , respectivamente. Al i-ésimo sı́mbolo de la gramática se
le codifica como 10i+5 . En esta codificación, no se puede saber con exactitud
cuáles son los sı́mbolos usados por terminales o noterminales.
Problemas decidibles e indecidibles
Un problema cuyo lenguaje es recursivo se dice decidible. En otro caso, el
problema es indecidible. Es decir, un problema es indecidible si no existe un
algoritmo que tome como entrada una instancia de un problema y determine
si la respuesta a esa instancia es “sı́” o “no”.
Una consecuencia no intuitiva de la definición de “indecidible” es que problemas con sólo una instancia son trivialmente decidibles.
La teorı́a de la indecibilidad trata de la existencia o no existencia de algoritmos para resolver problemas con un número infinito de instancias.
Propiedades de lenguajes recursivos y
recursivamente enumerables
Una gran cantidad de teoremas sobre indecibilidad se han probado reduciendo
un problema a otro. Esta reducción involucra combinar varias máquinas de
Turing para formar una máquina compuesta. Ahora describimos informalmente cómo se hacen estas construcciones.
Dado un algoritmo (programa para MT que siempre para), se puede permitir
que la MT compuesta ejecute una acción si el algoritmo acepta y otra si rechaza
su entrada. No se puede hacer esto si damos una MT arbitraria en vez de un
algoritmo, ya que si la MT rechaza su entrada, puede ser que corra por siempre, y la máquina compuesta nunca inicie la siguiente tarea. En los diagramas
que usemos para representar máquinas compuestas, una flecha hacia dentro de
una caja etiquetada con “inicio” indica la señal de inicio. Cajas sin señal de
inicio se asumen que comienzan a funcionar cuando la maquina compuesta lo
hace. Los algoritmos tienen dos salidas, “sı́” y “no”, que se pueden usar como
señal de inicio o como una respuesta para la máquina compuesta. Las MT
arbitrarias tienen sólo la salida “sı́”, que se usa para los mismos propósitos.
3
Curso Básico de Computación
Ahora se presentan propiedades básicas de cerradura de la clase de conjuntos
recursivos y r.e.
Teorema 8.1 El complemento de un lenguaje recursivo es recursivo.
Demostración: Sea L un lenguaje recursivo y M una Máquina de Turing
que se para con todas las entradas y acepta a L. Construya M 0 usando M de
tal manera que si M entra en un estado final con la entrada w, entonces M 0
se para sin aceptar la entrada. Si M se para sin aceptar la entrada, M 0 entra
a un estado final. La máquina M 0 es un algoritmo porque siempre ocurre uno
de estos eventos, M 0 es un algoritmo. Claramente L(M 0 ) es el complemento
de L y ası́ el complemento de L es un lenguaje recursivo. La construcción de
M 0 a partir de M se muestra en la siguiente figura:
Si
w
Si
No
M
No
Teorema 8.2: La unión de dos lenguajes recursivos es recursivo. La unión de
dos lenguajes recursivamente enumerables es recursivamente enumerable.
Demostración: Sea L1 y L2 lenguajes recursivos aceptados por los algoritmos M1 y M2 . Se construye M de modo que primero simula a M1 . Si M1
acepta, entonces M acepta. Si M1 rechaza, entonces M simula a M2 y acepta
si y sólo si M2 acepta. Ya que tanto M1 como M2 son algoritmos se tiene la
garantı́a que M siempre para. Claramente M acepta a L1 ∪ L2 .
Para lenguajes recursivamente enumerables la construcción anterior no funciona, ya que M1 puede no parar. En cambio M puede simular simultáneamente
M1 y M2 sobre cintas separadas. Si cualquiera de las dos acepta, entonces M
acepta. Las siguientes figuras muestran las dos construcciones.
Si
w
M
1
Inicio M
2
No
(a)
Si
Si
No
Feliú Sagols Troncoso
Matemáticas-Cinvestav
Si
4
Si
M
1
w
Si
M
2
(b)
Teorema 8.3: Si un lenguaje L y su complemento L̄ son ambos recursivamente enumerables, entonces L (y por lo tanto L̄) son recursivos.
Demostración: Sean M1 y M2 que aceptan a L y L̄, respectivamente. Se
construye M como en la siguiente figura para simular simultáneamente M1 y
M2 .
Si
Si
Si
No
M
1
w
M
2
M acepta a w si M1 acepta a w y rechaza a w si M2 acepta a w. Ya que w está
en L o L̄, sabemos que exactamente una de las máquinas M1 o M2 la acepta.
Ası́, M siempre dice “sı́” o “no”, pero nunca devuelve ambos resultados. Note
que no existe un limite a priori del tiempo que pueden tardar M1 o M2 antes
de aceptar, lo cierto que al menos uno de los dos lo hace. Dado que M es un
algoritmo que acepta a L, se sigue que L es recursivo.
Los Teoremas 8.1 y 8.3 tienen consecuencias importantes. Sea L y L̄ un par
de lenguajes complementarios. Entonces
1) Tanto L como L̄ son recursivos
2) Ninguno de L y L̄ son r.e. o
3) Uno de L y L̄ es r.e. pero no recursivo; el otro no es r.e.
Una técnica importante para demostrar que un problema es indecidible es demostrar por diagonalización que el complemento del lenguaje para el problema
no es r.e. Ası́, se aplica el caso (2) o (3).
8.3 La Máquina Universal de Turing y
un problema indecidible
5
Curso Básico de Computación
Ahora usaremos diagonalización para demostrar que un problema particular
es indecidible. El problema es: “¿La máquina de Turing M acepta la entrada
w?” Aqui, tanto M como w son parámetros del problema. Formalizando el
problema como un lenguaje se restringe w sobre el alfabeto {0, 1} y M tiene
como alfabeto de la cinta a {0, 1, B}. Como el problema restringido es indecidible, el problema más general seguramente también es indecidible. Escogemos
para trabajar la versión más restringida para simplificar la codificación de la
instancia del problema como cadenas.
Forma de codificar una máquina de
Turing
Para comenzar, codificamos las máquinas Turing con Σ = {0, 1}. Sea
M = (Q, {0, 1}, {0, 1, B}, δ, q1, B, {q2 })
una máquina de Turing con el alfabeto entrada {0, 1} y el blanco como el único
sı́mbolo adicional de la cinta. Además, asumimos que Q = {q1 , q2 , ..., qn } es
el conjunto de estados, y que q2 es el único estado final. El Teorema 7.10 nos
asegura que si L ⊆ (0 + 1)∗ es aceptado por alguna MT, entonces es aceptado
por una con alfabeto {0, 1, B}.
Es conveniente denotar a los sı́mbolos 0, 1, B con los sinónimos X1 , X2 , X3 ,
respectivamente. También a las direcciones L y R por los sinónimos D1 y D2 ,
respectivamente . Entonces un movimiento genérico δ(qi , Xj ) = (qk , Xl , Dm )
se codifica por la cadena binaria
0i 10j 10k 10l 10m
(8.1)
Un código binario para la máquina de Turing M es
111 código1 11 código2 11
· · · 11 códigor 111
(8.2)
donde cada códigoi es una cadena de la forma (8.1), y cada movimiento de M
se codifica por uno de los códigoi ’s. Los movimientos no necesitan estar en un
order en particular. Cualquier código para M se denota por hM i.
Cada cadena binaria se puede interpretar como el código de a lo más una
MT; muchas cadenas binarias no son código de ninguna MT. Para ver que la
decodificación es única, note que no hay cadenas de la forma (8.1) que tengan
dos 1’s seguidos, de tal forma que los códigoi ’s se pueden encontrar directamente. Si una cadena no comienza ni termina con tres unos, tiene tres unos
en una posición diferente del inicio o el final o tiene dos pares de unos que
delimitan una subcadena que no es de la forma 0i 10j 10k 10l 10m entonces la
Feliú Sagols Troncoso
Matemáticas-Cinvestav
6
cadena no representa a una MT.
El par M y w se representa por una cadena de la forma (8.2) seguida de
w. Tal cadena se denota por hM, wi.
Ejemplo: Sea M = ({q1 , q2 , q3 }, {0, 1}, {0, 1, B}, δ, q1, B, {q2 }) con los movimientos:
δ(q1 , 1) = (q3 , 0, R)
δ(q3 , 0) = (q1 , 1, R)
δ(q3 , 1) = (q2 , 0, R)
δ(q3 , B) = (q3 , 1, L)
Ası́, una cadena denotada por hM, 1011i es
111010010001010011000101010010011
000100100101001100010001000100101111011
Un lenguaje no r.e
Suponga que se tiene una lista de (0 + 1)∗ en orden canónico, donde wi es la
i-ésima palabra y Mj es la MT cuyo código, como en (8.2) es el entero j escrito
en binario. Imagine una tabla infinita que dice para toda i y para toda j si
wi ∈ L(Mj ).La figura ilustra tal tabla, 0 significa que wi ∈
/ L(Mj ) y 1 significa
wi ∈ L(Mj ).
j
1
0
1
1
0
...
2
1
1
0
0
...
3
0
0
1
0
...
4
0
1
0
1
...
.
...
...
...
4
...
3
...
2
..
i
1
Diagonal
Construimos un lenguaje Ld usando las entradas de la diagonal de la tabla para
determinar la pertenencia en Ld . Para garantizar que no hay MT que acepte
a Ld , insistimos en que wi ∈ Ld si y sólo si la entrada (i, i) es 0, es decir, si
Mi no acepta a wi . Suponga que alguna MT Mj acepta a Ld . Entonces nos
enfrentamos a la siguiente contradicción. si wj ∈ Ld , entonces la entrada (j, j)
es 0, implica que wj ∈
/ L(Mj ) y contradecimos Ld = L(Mj ). Por otra parte,
si wj ∈
/ Ld , entonces la entrada (j, j) es 1, implica que wj ∈ L(Mj ), lo cual
7
Curso Básico de Computación
también contradice Ld = L(Mj ). Como wj pertenece o no pertenece a Ld , se
concluye que la suposición Ld = L(Mj ) es falsa. Ası́, no hay MT en la lista
que acepte a Ld , y por el Teorema 7.10, no hay MT que acepte a Ld . Ası́, se
probó
Lema 8.1 Ld no es r.e.
El lenguaje universal
Definimos Lu , el “lenguaje universal” como {hM, wi | M acepta a w}. Llamamos a Lu “universal” ya que la pregunta de si cualquier cadena particular
w ∈ (0 + 1)∗ es aceptada por cualquier MT particular M es equivalente a la
pregunta de si hM 0 , wi ∈ Lu , donde M 0 es la MT cuyo alfabeto de la cinta es
{0, 1, B} equivalente a M construido como en el Teorema 7.10.
Teorema 8.4 Lu es recursivamente enumerable.
Demostración: Vamos a exhibir una máquina de Turing M1 con tres cintas que acepta a Lu . La primera cinta de M1 es la cinta de entrada, y la
cabeza de lectura de esa cinta se usa para buscar los movimientos de la MT M
cuando recibe el código hM, wi como entrada. Note que los movimientos de
M se localizan entre los dos primeros bloques de tres 1’s. La segunda cinta de
M1 será usada para simular la cinta de M . El alfabeto de M es {0, 1, B}, de
modo que cada sı́mbolo de la cinta de M puede ser almacenado en una celda
de la segunda cinta de M1 . Observe que si no restringieramos el alfabeto de
M , tendrı́amos que usar muchas celdas de la cinta de M1 para simular una
de las una de las celdas de M , pero la simulación podrı́a ser llevada a cabo
con un poco más de trabajo. La Tercer cinta contiene el estado de M , con qi
representado por oi . El comportamiento de M1 puede inferirse fácilmente a
partir de la codificación de la MT.
La existencia de M1 es suficiente para probar el Teorema 8.4. Sin embargo,
por los Teoremas 7.2 y 7.10, se puede encontrar una MT con una cinta semiinfinita y alfabeto {0, 1, B} que acepte a Lu . Llamamos a esta MT Mu , la
máquina universal de Turing.
Por el Lema 8.1, el lenguaje diagonal Ld no es r.e. y por lo tanto no
recursivo. Ası́, por el Teorema 8.1, L̄d no es recursivo. Note que L̄d
{wi | Mi acepta a wi }. Podemos probar que el lenguaje universal Lu
{hM, wi | M acepta a w} no es recursivo reduciendo L̄d a Lu . Ası́ Lu
un ejemplo de un lenguaje que es r.e. pero no es recursivo. De hecho, L̄d
otro ejemplo de tal lenguaje.
es
=
=
es
es
Teorema 8.5 Lu no es recursivo.
Demostración: Suponga que A es un algoritmo que reconoce a Lu . Entonces
puede reconocer a L̄d de la siguiente manera. Dada una cadena w ∈ (0 + 1)∗ ,
Feliú Sagols Troncoso
Matemáticas-Cinvestav
8
determine por un sencillo cálculo el valor de i tal que w = wi . El entero i
en binario es el código para alguna MT Mi . Se da como entrada hMi , wi i al
algoritmo A y se acepta a w si y sólo si Mi acepta a wi . La construcción se
muestra en la siguiente figura:
<M i , wi >
w
Convertir
Hipotetico
A para L u
Si
Si
No
No
Construir algoritmo para L d
Es fácil verificar que el algoritmo construido acepta a w si y sólo si w = wi y
wi ∈ L(Mi ). Ası́, se tiene un algoritmo para L̄d . Ya que no existe tal algoritmo, nuestra suposición, de que el algoritmo A para Lu existe, es falsa. Por
lo tanto, Lu es r.e. pero no recursivo.
8.4 Teorema de Rice y algunos
problemas indecidibles
Ahora tenemos un ejemplo de un lenguaje r.e que no es recursivo. El problema asociado “M acepta a w” es indecidible, y podemos usar este hecho para
demostrar que otros problemas son indecidibles.
Ejemplo: Considérese el siguiente problema: “¿Es L(M ) 6= ∅?” Sea hM i una
codificación de M como en (8.2). Defı́nanse
Lne = {hM i|L(M ) 6= ∅} y Le = {hM i|L(M ) = ∅}.
Nótese que Le y Lne son complementos uno del otro, como cada cadena binaria denota alguna MT; aquellas con un mal formato denotarán las MT’s sin
movimientos. Todas estas cadenas están en Le . Se afirma que Lne es r.e. pero
no recursivo y que Le no es r.e.
Primero se probará que Lne es r.e. construyendo una MT M que reconozca
codificaciones de MT’s que aceptan conjuntos no vacı́os. Dada una entrada
hMi i, M adivina de manera no determinı́stica una cadena x aceptada por Mi
y verifica que, en efecto, Mi acepta a x simulando Mi sobre la entrada x. Este
paso también puede llevarse a cabo determinı́sticamente si se usa la pareja
generadora descrita en la sección 7.7. Para cada par (j, k) se simula Mi sobre
la j-ésima cadena binaria (en orden canónico) para k pasos. Si Mi acepta,
entonces M acepta hMi i.
Ahora se mostrará que Le no es recursivo. Supóngase que lo fuera. Entonces
se podrı́a construir un algoritmo para Lu , lo que vioları́a el Teorema 8.5. Sea
9
Curso Básico de Computación
A un algoritmo que acepta Le . Existe un algoritmo B que, dada hM, wi, construye una MT M 0 que acepta ∅ si M no acepta w y que acepta (0 + 1)∗ si M
acepta a w. El diagrama de M 0 se muestra en la siguiente figura. La máquina
M 0 ignora su entrada x, y en su lugar, simula M sobre la entrada w, aceptando
si M acepta a w.
Si
w
x
Si
M
M’
Nótese que M 0 no es B. En vez de esto, B es como un compilador que toma
hM, wi como un ”programa fuente” y produce M 0 como un ”programa objeto”.
Hasta aquı́ se ha descrito lo que B debe hacer, pero no cómo lo hace.
La construcción de B es sencilla, toma hM, wi y aisla w. La cadena w tiene
longitud n, por decir, w = a1 a2 · · · an . El algoritmo B crea n + 3 estados
q1 , q2 , · · · , qn+3 con movimientos
δ (q1 , X) = (q2 , $, R) para cualquier X
(imprime el marcador),
δ (qi , X) = (qi+1 , ai−1 , R) para cualquier X y
2 ≤ i ≤ n + 1 (imprime w),
δ (qn+2 , X) = (qn+2 , B, R) para X 6= B
(borra sobre la cinta),
δ (qn+2 , B) = (qn+3 , B, L) ,
δ (qn+3 , X) = (qn+3 , X, L) para X 6= B
(encuentra el marcador).
Después de producir las codificaciones para estos movimientos, B suma n + 3
a los ı́ndices de los estados de M e incluye el movimiento
δ(qn+3 , $) = (qn+4 , $, R)/*comienza M */
y todos los movimientos de M en su MT generada. La MT resultante tiene
un sı́mbolo extra en la cinta $, pero por el Teorema 7.10 se puede construir
M 0 con el alfabeto de cinta {0, 1, B}, y son seguridad, se puede hacer que q2
sea el estado de aceptación. Este paso completa el algoritmo B, y su salida es
la MT M 0 de la figura anterior.
Ahora supóngase que el algoritmo A que acepta Le existe. Entonces se construye un algoritmo C para Lu como en la figura siguiente:
Feliú Sagols Troncoso
< M, w >
Matemáticas-Cinvestav 10
M’
B
Si
No
A
C
Si
No
Si M acepta a w, entonces L(M 0 ) 6= ∅; ası́ A dice “no” y C dice “si”. Si M no
acepta a w, entonces L(M 0 ) = ∅, A dice “si” y C dice “no”. Por el Teorema
8.5, C no existe, luego, A tampoco existe. Ası́, Le no es recursivo. Si Lne
fuera recursivo, por el Teorema 8.1, Le lo serı́a también. De esta manera, Lne
es r.e. pero no recursivo. Si Le fuese r.e., entonces por el Teorema 8.3, Le y
Lne serı́an recursivos. Luego, Le no es r.e.
Ejemplo: Considere el lenguaje
Lr = {hM i | L(M ) es recursivo}
y
Lnr = {hM i | L(M ) no es recursivo}
Note que Lr no es {hM i | M se para con todas las entradas}, aunque éste
incluye el último lenguaje. Una MT M puede aceptar un lenguaje recursivo
aún cuando M pueda ciclarse con algunas palabras que no están en L(M );
algunas otras MT equivalentes a M deben parar siempre. Afirmamos que ni
Lr ni Lnr son r.e.
Suponga que Lr fue r.e. Entonces podemos construir una MT para L̄u la cual
sabemos que no existe. Sea Mr la MT que accepta a Lr . Podemos construir
un algoritmo A que tome como entrada a hM, wi y produzca como salida una
MT M 0 tal que
∅ si M no acepta a w
0
L(M ) =
Lu si M acepta a w
Note que Lu no es recursivo, de esta manera M 0 acepta un lenguaje recursivo
si y sólo si M no acepta a w. El plano de M 0 se muestra en la siguiente figura:
w
Si
Inicio
M
Si
Mu
x
M’
Dado A y Mr se puede construir una MT que acepte a L̄u , en la siguiente figura
se muestra el comportamiento.
< M, w >
A
M’
Mr
Si
Si
11
Curso Básico de Computación
Con la entrada hM, wi la MT usa A para producir M 0 , usa Mr para determinar si el conjunto aceptado por M 0 es recursivo, y acepta si y sólo si L(M 0 ) es
recursivo. Pero L(M 0 ) es recursivo si y sólo si L(M 0 ) = ∅, lo que significa que
M no acepta a w. Ası́ la MT de la figura anterior acepta a hM, wi si y sólo si
hM, wi está en L̄u .
Para Lnr , suponga que tiene una MT Mnr que acepta a Lnr . Entonces se puede
usar Mnr y un algoritmo B, para aceptar L̄u . B toma como entrada a hM, wi
y produce como salida una MT M 0 tal que
∗
Σ si M acepta a w
0
L(M ) =
Lu si M no acepta a w
Ası́ M 0 acepta un lenguaje recursivo si y sólo si M acepta a w. M 0 , la cual
debe producir B, se muestra en la siguiente figura
Si
M
w
Si
Si
Mu
x
M’
(a)
Y una MT que acepte a L̄u dados B y Mnr se muestra en
< M, w >
B
M’
M nr
Si
Si
(b)
La MT anterior acepta hM, wi si y sólo si L(M 0 ) no es recursivo, o equivalentemente, si y sólo si M no acepta a w. Es decir, la MT acepta a hM, wi si
y sólo si hM, wi está en L̄u . Como ya tenemos demostrado que no existe tal
MT, la suposición de que Mnr existe es falsa. Y se concluye que Lnr no es r.e.
Teorema de Rice para conjuntos de
ı́ndice recursivo
En el ejemplo anterior se demostró que no se puede decidir si el conjunto aceptado por una MT es vacı́o o recursivo. La técnica de la demostración también
se puede usar para demostrar que no se puede decidir si el conjunto aceptado
es finito, infinito, regular, libre de contexto, si tiene un número par de cadenas, etc. Entonces ¿qué podemos decidir acerca del conjunto aceptado por
una MT?
Sea L un conjunto de lenguajes r.e., cada uno de los cuales es un subconjunto
de (0 + 1)∗ . Se dice que L es una propiedad de los lenguajes r.e. Un conjunto
L tiene la propiedad L si L es un elemento de L. L es una propiedad trivial
si L es vacı́o o si L consiste de todos los lenguajes r.e. Sea LL el conjunto
{hM i | L(M ) ∈ L}
Feliú Sagols Troncoso
Matemáticas-Cinvestav 12
Teorema 8.6 (Teorema de Rice) Cualquier propiedad no trivial L de los
lenguajes r.e. es indecidible.
Demostración: Sin pérdida de generalidad asumimos que ∅ no está en L
(en otro caso considere L). Como L es no trivial, existe L con la propiedad
L. Sea ML una MT que acepta a L. Suponga que L es decidible. Entonces
existe un algoritmo ML que acepta a LL . Usamos ML y ML para construir un
algoritmo para Lu . Primero construya un algoritmo A que tome hM, wi como
entrada y produzca como salida a hM 0 i, donde L(M 0 ) está en L si y sólo si M
acepta a w.
El diseño de M 0 se muestra en la siguiente figura:
w
x
Si Inicio
M
Si
ML
Si
M’
Primero M 0 ignora todas las entradas y simula M en w. Si M no acepta a w,
entonces M 0 no acepta a x. Si M acepta a w, entonces M 0 simula a ML en x,
aceptando a x si y sólo si ML acepta a x. Ası́, M 0 acepta a ∅ o L dependiendo
de si M acepta w o no.
Podemos usar la máquina ML hipotética para determinar si L(M 0 ) está en
L. Como L(M 0 ) está en L si y sólo si hM, wi está en Lu , se tiene un algoritmo
que reconoce a Lu , lo cual es una contradicción. Ası́, L debe ser indecidible.
El Teorema 8.6 tiene una gran variedad de consecuencias, algunas se resumen
en el siguiente corolario.
Corolario: Las siguientes propiedades de los conjuntos r.e. no son decidibles :
a) vacuidad
b) finitud
c) regularidad
d) libertad de contexto
Teorema de Rice para conjuntos de
ı́ndice recursivamente enumerable
La condición bajo la cual un conjunto LL es r.e. es mucho más complicada. Se
debe demostrar que LL es r.e. si y sólo si L satisface las siguientes condiciones:
13
Curso Básico de Computación
1) Si L está en L y L ⊆ L0 , para algún L0 r.e., entonces L0 está en L (la
propiedad de contención).
2) Si L es un lenguaje infinito en L, entonces existe un subconjunto finito de
L en L.
3) El conjunto de lenguajes finitos en L es enumerable, en el sentido que existe
una MT que genera la (posible) cadena infinita código1 #código2 #...,
donde códigoi es un código para el i-ésimo lenguaje infinito en L (en
cualquier orden). El código para el lenguaje finito {w1 , w2 , ..., wn } es
justo w1 , w2 , ..., wn .
Probemos estás caracterizaciones con una serie de lemas.
Lema 8.2 Si L no tiene la propiedad de contención, entonces LL no es r.e.
Demostración: Generalizamos la demostración que Lnr no es r.e. Sea L1
en L, L1 ⊆ L2 , de modo que L2 no está en L. Se construye el algoritmo A que
toma como entrada hM, wi y produce como salida la MT M 0 con el comportamiento que se muestra en la siguiente figura:
Si
M1
x
w
Si
Inicio
Si
Si
M2
M
M’
donde M1 y M2 aceptan a L1 y L2 respectivamente. Si M acepta a w, entonces se inicia M2 , y M 0 acepta a x si x está en L1 o L2 . Si M no acepta a
w, entonces M2 nunca empieza, de esta manera M 0 acepta a x si y sólo si x
está en L1 . Como L1 ⊆ L2 ,
L2 si M acepta a w
0
L(M ) =
L1 si M no acepta a w
Ası́, L(M 0 ) está en L si y sólo si M no acepta a w. Se deja al lector el diseño del
compilador A que toma a hM, wi como entrada y las conecta con la máquina
de Turing fija M1 y M2 para construir M 0 . Ya construido A, se puede usar a
MT ML de LL para aceptar a L̄u , como se muestra en la siguiente figura:
< M, w >
A
M’
ML
Si
Si
Esta MT acepta a hM, wi si y sólo si M 0 acepta un lenguaje en L, o equivalentemente, si y sólo si M no acepta a w. Ası́ L̄u serı́a r.e. Como esto último
no es cierto concluimos que LL no es r.e.
Feliú Sagols Troncoso
Matemáticas-Cinvestav 14
Lema 8.3 Si L tiene un lenguaje infinito L tal que no hay subconjuntos finitos
de L que estén en L, entonces LL no es r.e.
Demostración: Bajo el supuesto que LL es r.e vamos a probar que L̄u es r.e.
Sea M1 una MT que acepta a L. Construya el algoritmo A que toma el par
hM, wi como entrada y produce como salida una MT M 0 que acepta a L si
w no está en L(M ) y acepta algún subconjunto finito de L en otro caso. El
diseño de L0 se muestra en la siguiente figura:
Inicio, simular para | x | movimientos
Si
x
M1
w
M’
M
Si
No "Si" después
de | x| movimientos
M 0 simula a M1 con la entrada x. Si M1 acepta a x, entonces M 0 simula a M
con w durante |x| movimientos. Si M no acepta a w después de |x| movimientos, entonces M 0 acepta a x.
Si w está en L(M ), entonces M acepta a w después de algún número de
movimientos, digamos j. Entonces L(M 0 ) = {x | x ∈ L y |x| < j}, el cual es
un subconjunto finito de L. Si w no está en L(M ), entonces L(M 0 ) = L. Por
lo tanto, si M no acepta a w, L(M 0 ) está en L, y si M acepta a w, L(M 0 ), es
un subconjunto finito de L, que no está en L por hipótesis del lema. Con el
argumento estandar que hemos venido manejando se puede probar que si LL
es r.e., también lo es L̄u . Como el último no es r.e., se concluye que el primero
tampoco lo es.
Lema 8.4 Si LL es r.e., entonces la lista de códigos binarios para el conjunto
finito en L es enumerable.
Demostración: Usamos el par generador descrito en la Sección 7.7. Cuando
(i, j) se genera, tomamos a i como el código binario de un conjunto finito,
asumimos que 0 es el código para la coma, 10 es el código para el cero, y
11 es el código para 1. Podemos construir de manera directa a la MT M (i)
que acepta exactamente las palabras en el lenguaje finito representado por i.
Entonces simula el enumerador para LL con j pasos. Si se tiene impreso a
M (i) , se imprime el código para el conjunto finito representado por i, es decir,
la representación binaria de i mismo, seguido de un sı́mbolo delimitador #.
En cualquier caso, después la simulación regresa el control al par generador,
el cual genera el siguiente par (i, j).
Teorema 8.7 LL es r.e. si y sólo si
1) Si L está en L y L ⊆ L0 , para algún L0 r.e., entonces L0 está en L.
2) Si L es un lenguaje infinito en L, entonces existe un subconjunto finito L0
en L que está en L.
15
Curso Básico de Computación
3) El conjunto de lenguajes finitos en L es enumerable.
Demostración: La parte del “sólo sı́” son los Lemas 8.2, 8.3 y 8.4. Para la
parte del “sı́”, suponga que se tiene (1), (2) y (3). Se construye la MT M1 que
reconoce a hM i si y sólo si L(M ) está en L. M1 genera pares (i, j) usando el
generador de pares. En respuesta a (i, j), M1 simula a M2 , que es un enumerador de un conjunto finito en L, para i pasos. Sabemos que M2 existe por la
condición (3). Sea L1 el último conjunto completamente impreso en la salida
de M2 . Entonces se simula a M durante j pasos en cada palabra de L1 . Si M
acepta todas las palabras en L1 , entonces M1 acepta a hM i . Si no, M1 genera
el siguiente par (i, j).
Usamos la condición (1) y (2) para demostrar que L(M1 ) = LL . Suponga que
L está en LL , y sea M cualquier MT con L(M ) = L. Por la condición (2),
existe un conjunto finito L0 ⊆ L en L. Sea L0 el lenguaje generado después i
pasos por M2 , y sea j el número máximo de pasos que requiere M para aceptar
una palabra en L0 . Entonces cuando M1 genera (i, j) acepta hM i.
Recı́procamente, suponga que M1 acepta hM i. Entonces existe algún (i, j)
tal que dentro de j pasos M acepta cada palabra en algún lenguaje finito L0
tal que M2 genera a L0 dentro de los primeros i pasos. Entonces L0 está en L,
y L0 ⊆ L(M ). Por la condición (1), L(M ) está en L. De tal manera hM i está
en LL . Concluimos que L(M1 ) = LL .
El Teorema 8.7 tiene una gran variedad de consecuencias. Se resumen algunas
de ellas como corolarios.
Corolario 1 Las siguientes propiedades de los conjuntos r.e. no son r.e.
a) L = ∅.
b) L = Σ∗ .
c) L es recursivo.
d) L no es recursivo.
e) L es un singleton (tiene exactamente un miembro).
f) L es un conjunto regular.
g) L − Lu 6= ∅.
Demostración: En cada caso la condición 1 se viola, excepto para (b), donde
(2) se viola, y (g), donde (3) se viola.
Corolario 2 Las siguientes propiedades de las conjuntos r.e. son r.e
a) L 6= ∅.
Feliú Sagols Troncoso
Matemáticas-Cinvestav 16
b) L contiene al menos 10 miembros.
c) w ∈ L para alguna palabra fija w.
d) L ∩ Lu 6= ∅.
Problemas acerca de las máquinas de
Turing
¿El Teorema 8.6 dice todo sobre si la MT es indecidible? La respuesta es
no. Este teorema tiene que ver con propiedades del lenguaje aceptado, no
propiedades de la máquina de Turing misma. Por ejemplo, la pregunta “¿Dada
una MT tiene un número par de estados?” es claramente decidible.
Ejemplo: No se puede decidir si una máquina de Turing con alfabeto {0, 1, B}
imprime alguna vez tres 1’s consecutivos sobre su cinta. Para cada máquina de
ci , la cual simula sobre cinta en blanco
Turing Mi se construye una máquina M
ci usa 01 para codificar un 0 y 10
Mi sobre cinta en blanco. Sin embargo, M
ci
para codificar un 1. Si la cinta de Mi tiene un 0 en la celda j, entonces M
ci
tiene 01 en las celdas 2j − 1 y 2j. Si Mi cambia un sı́mbolo, entonces M
ci
cambia el correspondiente 1 a 0, luego el respectivo 0 a 1. Se puede diseñar M
ci puede
para que nunca tenga tres 1’s consecutivos sobre su cinta. Más aún, M
ci imprima tres 1’s consecutivos y pare.
modificarse para que si Mi acepta, M
c
Ası́, Mi imprime tres 1’s consecutivos si y sólo si Mi acepta . Por el Teorema
8.6, no se puede decidir si una MT acepta , ya que el enunciado “ está en L”
no es trivial. Ası́, la pregunta de saber si una MT arbitraria imprime alguna
vez tres 1’s consecutivos no es decidible.
Ejemplo: ¿Es decidible si una MT que inicia sobre una cinta en blanco, visita
cualquier celda cuatro o más veces?. Si la máquina de Turing nunca visita una
celda cuatro o más veces, entonces cada secuencia de cruce (secuencia de estados en los cuales la frontera entre celdas es atravezada, asumiendo cambio
de estados antes de que la cabeza se mueva) es de longitud a lo más tres. Pero
hay un número finito de secuencias de cruce de longitud tres o menos. Ası́
puede suceder que la máquina de Turing permanezca dentro de una cantidad
fija de celdas de cinta, en cuyo caso las técnicas de autómatas finitos responden
la pregunta, o se repite alguna secuencia de cruce. Pero si alguna secuencia
de cruce se repite, entonces la MT se mueve a la derecha con algún patrón
facilmente detectable, y la pregunta de nuevo es decidible.
8.5 Indecidibilidad del problema de
correspondencia de Post