• Author / Uploaded
• Yahiko Pein

• Categories
• Algoritmos
• Prueba matemática
• Formalismo (Deductivo)
• Matemática discreta
• Matemática aplicada

Citation preview

1. LENGUAJE NO RECURSIVAMENTE ENUMERABLE Recuerde que un lenguaje L es recursivamente enumerable (RE) si L = L ( M ) para alguna máquina de Turing M. 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. El primer paso consiste en enunciar este problema como una cuestión acerca de la pertenencia a un determinado lenguaje. Por tanto, tenemos que determinar una codificación para las máquinas de Turing que sólo utilizan ceros y unos, independientemente de cuántos estados tengan la MT. Una vez que dispongamos de esta codificación, podremos tratar cualquier cadena binaria como si fuera una máquina de Turing. Si la cadena no es una representación bien formada de una MT, podemos interpretarlo como una representación de un MT sin movimientos. Por tanto, podemos pensar que cualquier cadena binaria representa una MT. Un objetivo intermedio, que además es el objeto de esta sección, implica al lenguaje

Ld

,

el “lenguaje de diagonalización”, formado por todas aquellas cadenas w tales que la MT Ld representada por w no acepta la entrada w. Demostraremos que no es aceptado por ninguna máquina de Turing. Recuerde que demostrando que no existe ninguna máquina de Turing para un lenguaje, estamos demostrando algo aún más restrictivo que el hecho de que el lenguaje sea indecidible (es decir, que no existe ningún algoritmo, o ninguna MT que siempre se pare). 1.1

Enumeración de cadenas binarias

Si w es una cadena binaria, tratamos 1w como 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 wi adelante, denominaremos a la cadena i-ésima. 1.2

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 Mi podremos hablar de “la i-ésima máquina de Turing, ”. Para representar una MT q1

M = ( Q ,{ 0 , 1 }, Γ, δ,

, 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. 

q1

Supondremos que los estados son q1

inicial siempre será

q2

,y

,

q2

qk

,...,

para algún k. El estado

será el único estado de aceptación. Observe

que, dado que podemos suponer que la MT se para cuando entra en un estado de aceptación, nunca existe la necesidad de que haya más de un estado de aceptación. 

X1

Supondremos que los símbolos de cinta son X1

m.

siempre será el símbolo 0,

X2

,

X2

será el 1 y

,..., X3

Xm

para algún

será B, el espacio

en blanco. No obstante, pueden asignarse otros símbolos de cinta a los restantes enteros de forma arbitraria. 

Denominaremos a la dirección L (izquierda) D2

D1

y a la dirección R (derecha)

.

Dado que el orden en que se asignan los enteros a los estados y símbolos de cinta de cada MT M puede ser diferente, existirá más de una codificación para cada MT. Sin embargo, este hecho no es importante, ya que vamos a demostrar que ninguna codificación Ld puede representar una MT M tal que L ( M ) = . Una vez que hemos asignado un entero a cada estado, símbolo y dirección, podemos q codificar la función de transición δ. Supongamos que una regla de transición es δ ( i , Xj

)=(

qk

,

X1

,

cadena mediante la cadena

Dm i

) , para los valores enteros i, j, k, l y m. Codificamos esta j

k

l

0 ,1 0 ,1 0 , 10 , 1 0

m

. Observe que, dado que i, j, k, l y m

valen, como mínimo, uno, no existen subcadenas de dos o más unos consecutivos en el código de una única transición. Un código para la MT completa TM M consta de todos los códigos correspondientes a las transiciones, en un cierto orden, separados por pares de unos:

donde cada una de las C corresponde al código de una transición de M. EJEMPLO1: Sea la MT

donde δ consta de las reglas siguientes:

Los códigos de cada una de estas reglas son, respectivamente:

Por ejemplo, la primera regla puede escribirse como δ ( D2

) , ya que 1 =

X2

Por tanto, su código es

X1

,0= 1

2

D2

yR= 3

1

2

0 ,1 0 , 10 , 1 0 ,1 0

código para M es entonces:

q1

,

X2

)=(

q3

,

X3

,

.

, como se ha indicado anteriormente. Un

Observe que existen otros muchos posibles códigos para M. En particular, los códigos de las cuatro transiciones pueden enumerarse en cualquiera de las 4! ordenaciones posibles, lo que nos da 24 códigos para M.

Figura 1: Tabla que representa la aceptación de cadenas por máquinas de Turing.

1.3

El lenguaje de diagonalización

La “máquina de Turing i-ésima”: es aquella MT M cuyo código es

wi

, la cadena

binaria i-ésima. Muchos enteros no se corresponden con ninguna MT. Por ejemplo, 11001 wi no comienza por 0, y 0010111010010100 tiene tres unos consecutivos. Si no es un código válido de MT, interpretaremos que

Mi

transición. Es decir, para dichos valores de i,

es una MT con un estado y ninguna Mi

es una máquina de Turing que se

detiene de forma inmediata para cualquier entrada. Por tanto, L (

Mi

) es θ si

wi

no es

un código válido de la MT. El lenguaje que

wi

Ld

, el lenguaje de diagonalización, es el conjunto de cadenas

no pertenece a L (

Mi

).

wi

tal

Es decir,

Ld

consta de todas las cadenas w tales que la MT M, cuyo código es w, no

acepta cuando se proporciona w como entrada. La razón por la que

Ld

se denomina lenguaje de “diagonalización” puede verse

fijándose en la Figura 1. Esta tabla indica para todo i y j, si la MT Mi acepta o no la cadena wj de entrada ; 1 signfica que “sí la acepta” y 0 indica que “no la acepta”.1 La fila iésima puede intrepretarse como el vector característico del lenguaje L (

Mi

) ; es decir,

los unos de esta fila indican las cadenas que pertenecen a este lenguaje. Los valores de la diagonal indican si

Mi

acepta

wi

. Para construir

Ld

, se

complementa la diagonal de la tabla. Por ejemplo, si la Figura 1 fuera la tabla correcta, Ld entonces la diagonal complementada comenzaría por 1, 0, 0, 0,.... Por tanto, contendría w1 =ε, no contendría w2 hasta w4, que son 0,1 y 00, etc. El proceso que consiste en complementar la diagonal para construir el vector característico de un lenguaje, que no puede ser el lenguaje que aparece en ninguna de las filas, se denomina diagonalización. Este proceso funciona porque el complementario de la diagonal es en sí mismo un vector característico que describe la pertenencia a un lenguaje, Ld que denominaremos, . Este vector característico difiere en alguna columna de todas las filas de la tabla mostrada en la Figura 1. Por tanto, el complementario de la diagonal no puede ser el vector característico de ninguna máquina de Turing. 1.4 Ld

Demostración de que

Ld

no es recursivamente enumerable

no es un lenguaje recursivamente enumerable. Es decir, no existe ninguna máquina

de Turing que acepte

Ld

.

DEMOSTRACIÓN. Supongamos que Ld

Ld

fuera L ( M ) para alguna MT M. Dado que

es un lenguaje sobre el alfabeto { 0 , 1 } , M debería estar en la lista de máquinas de

Turing que hemos construido, dado que incluye todas las MT cuyo alfabeto de entrada es Mi { 0 , 1 } . Por tanto, existe al menos un código para M, por ejemplo i; es decir, M = . Ahora veamos si wi pertenece a

Ld

.



Si

wi

Ld

definición de aquellas 

Ld

pertenece a

wj

wi

,

De manera similar, si

wi

Por tanto, por definición de Dado que

wi

no acepta

wj Ld

no pertenece a Ld

wi

,

wi

acepta Ld

no pertenece a

Mj

tales que

Mi

, entonces

. Pero entonces, por Ld

, porque

sólo contiene

. Mi

no acepta

wi

.

y no pertenecer a

Ld

,

, entonces Ld

pertenece a

no puede simultáneamente pertenecer a

Ld

.

concluimos que existe una contradicción en la suposición de que existe M. Es decir,

Ld

no es un lenguaje recursivamente enumerable.

2. PROBLEMAS INDECIDIBLES PARA LAS MAQUINAS DE TURING Reducciones P1

En general, si tenemos un algoritmo para convertir casos de un problema P2

de un problema reduce a

P2

P2

P1

. Por tanto, si

es no-RE, entonces

P1

no es recursivo, entonces

P1

P2

todo caso de

P2

P1

P2

se

es al menos no puede ser

cuya respuesta sea “sí”

cuya respuesta sea también “sí”, y todo caso de

sea “no” en un caso de

P2

P1

no puede ser RE. Como se muestra en la

Figura 1, una reducción tiene que convertir cualquier caso de en un caso de

P2

. Podemos utilizar esta demostración para comprobar que

tan complejo como recursivo. Si

que proporciona la misma respuesta, entonces decimos que

en casos

P1

cuya respuesta

cuya respuesta sea “no”. Observe que no es esencial que a

le corresponda uno o más casos de

habitual que sólo una pequeña fracción de

P2

P1

, y de hecho es bastante

sea el objetivo de la reducción.

P1

Formalmente, una reducción de P1

a P2 es una máquina de Turing que toma un caso de P2

de su cinta y se para cuando en su cinta hay un caso de

.

TEOREMA1 Si existe una reducción de P1

a) Si

P1

a

P2

es indecidible, entonces

, entonces: P2

también lo es.

Figura 1: Reducciones de casos positivos en positivos, y negativos en negativos. P1

b) Si

P2

es no-RE, entonces

también lo es. P1

DEMOSTRACIÓN. En primer lugar, suponemos que posible decidir sobre

P2

P2

P2

P1

decir, w pertenece a P1

P1 P1

a

P2

P2

. Aplicamos a w el algoritmo

. A continuación aplicamos el algoritmo que decide

a x. Si dicho algoritmo da como respuesta “sí”, entonces x está en

que hemos reducido

parte de

P2

a

para construir un algoritmo que decida sobre

. Suponemos que disponemos de un caso w de

que convierte w en un caso x de sobre

P1

, entonces podemos combinar la reducción de

con el algoritmo que decide sobre P1

es indecidible. Si es

, sabemos que la respuesta de

. Igualmente, si x no forma parte de

, y lo que responda a la cuestión “¿está x en

P2 P2

P1

P2

. Dado

a w es “sí”; es

entonces w no forma ?” será también la

P1

respuesta correcta a “¿está w en suposición de que entonces

P2

P1

?” Por tanto, hemos llegado a una contradicción de la

es indecidible. La conclusión es que si

P1

es indecidible,

también es lo es. P1

Consideremos ahora el apartado (b). Supongamos que P1

RE. Ahora tenemos un algoritmo para reducir procedimiento para reconocer su entrada pertenece a

P2

P2

a

P2

P2

es no-RE, pero

es

, pero sólo disponemos de un

; es decir, existe una MT que da como respuesta “sí” si P2

pero puede no pararse si su entrada no pertenece a

Como en el apartado (a), partimos de una instancia w de P2

el algoritmo de reducción en una instancia x de

P1

.

, la convertimos mediante

. Luego aplicamos la MT para

P2

a x. Si x se acepta, entonces w se acepta. Este procedimiento describe una MT (que puede no pararse) cuyo lenguaje es P1

w pertenece a P1

pertenece a

, entonces x pertenece a

, entonces x no pertenece a

P2 P2

P1

. Si

, por lo que esta MT aceptará w. Si w no . Luego la MT puede o no pararse, pero

seguro que no aceptará w. Dado que hemos supuesto que no existe ninguna MT para

P1

,

hemos demostrado por reducción al absurdo que tampoco existe ninguna MT para

P2

;

Le

.

es decir, si

P1

es no-RE, entonces

P2

es no-RE.

Máquinas de Turing que aceptan el lenguaje vacío Si L ( Por tanto,

Mi Le

) =θ, es decir, Mi no acepta ninguna entrada, entonces w pertenece a

es el lenguaje formado por todas aquellas codificaciones de MT cuyo

lenguaje es el lenguaje vacío. Por el contrario, si L ( entonces w pertenece a

Lne

. Por tanto,

Lne

Mi

) no es el lenguaje vacío,

es el lenguaje que consta de todos los

códigos de las máquinas de Turing que aceptan al menos una cadena de entrada.

Figura 2: Construcción de una MT no determinista que acepta

Lne

.

De aquí en adelante, resultará conveniente interpretar las cadenas como las máquinas de Turing que representan. Así, podemos definir los dos lenguajes que acabamos de mencionar como sigue: 

Le

={M|L(M)=θ}



Lne

= { M | L ( M )≠θ }

Observe que

Le

y

Lne

son lenguajes sobre el alfabeto binario { 0 , 1 } , y que son

complementarios entre sí. Veremos que no recursivo. Por el contrario,

Le

Lne

es el más “sencillo” de los dos y es RE pero

es no-RE.

TEOREMA 2 Lne

es recursivamente enumerable.

DEMOSTRACIÓN. Hay que demostrar que existe una MT que acepta

Lne

. Para

ello, lo más sencillo es describir una MT no determinista M, cuyo esquema se muestra en la Figura 2. El funcionamiento de M es el siguiente. 1. M toma como entrada el código de una MT

Mi

.

2. Utilizando su capacidad no determinista, M prueba con una entrada w que podría aceptar. 3. M comprueba si

Mi

Mi

acepta w. Para esta parte del proceso, M puede simular a

la MT universal U que acepta Lu. Mi 4. Si acepta w, entonces M acepta su propia entrada, que es

Mi

.

De esta forma, si

Mi

acepta aunque sea una sola cadena, M terminaría encontrándola Mi

(entre otras muchas, por supuesto), y aceptaría entonces ninguna cadena w sería aceptada por tanto, L ( M ) =

Lne

Lne

, por lo que M no aceptará

Mi Mi

) = θ, . Por

.

El siguiente paso consiste en demostrar que Lu a

Mi

. Sin embargo, si L (

Lne

no es recursivo. Para ello, reducimos

. Es decir, describiremos un algoritmo que transforme una entrada (M, w ) en

una salida M’ , el código de otra máquina de Turing, tal que w pertenezca a L ( M ) si y sólo si L ( M’ ) no es el lenguaje vacío. Es decir, M acepta w si y sólo si M’ acepta al menos una cadena. El truco está en que M’ ignora su entrada, en lugar de simular M para la entrada w. Si M acepta, entonces M’ acepta su propia entrada; por tanto, la aceptación de w por parte Lne de M es equivalente a que L (M’) no sea el lenguaje vacío. Si fuera recursivo, entonces tendríamos un algoritmo para determinar si M acepta o no la cadena w: construiríamos M’ y veríamos si L ( M’) = θ. TEOREMA 3 Lne

no es recursivo.

Figura 4: Esquema de la MT M’ construida a partir de ( M , w ) en el Teorema 3: M’ acepta una entrada arbitraria si y sólo si M acepta w.

DEMOSTRACIÓN. Seguiremos la misma línea que en la demostración anterior. Tenemos que diseñar un algoritmo que convierta una entrada, que es un par codificado en binario ( M , w ) , en una MT M’ tal que L ( M’)≠θ si y sólo si M acepta la entrada w. La construcción de M’ se muestra en la Figura 4. Como veremos, si M no acepta w, entonces

M’ no acepta ninguna de sus entradas; es decir, L ( M’) = θ. Sin embargo, si M acepta w, entonces M’ acepta todas las entradas y, por tanto, L ( M’) no será θ. M’ se diseña como sigue: 1. M’ ignora su propia entrada x. En su lugar, reemplaza su entrada por la cadena que representa la MT M y la cadena de entrada w. Puesto que M’ está diseñada para un par específico ( M , w ) , cuya longitud será por ejemplo n, podemos construir M’ q0 q1 qn q0 para disponer de una secuencia de estados , ,..., , donde es el estado inicial. a) En el estado

qi

, para i = 0 , 1 ,..., n − 1, M’ escribe el ( i + 1 ) -ésimo bit del

código de ( M , w ) , pasa al estado qi + 1 y se mueve hacia la derecha. qn b) En el estado , M’ se mueve hacia la derecha, si fuera necesario, reemplazando los símbolos no blancos (que corresponderán a la cola de x, si dicha entrada a M’ tiene una longitud mayor que n) por espacios en blanco. 2. Cuando M’ encuentra un espacio en blanco estando en el estado qn, utiliza una colección similar de estados para volver a posicionar su cabeza en el extremo izquierdo de la cinta. 3. Ahora, utilizando estados adicionales, M’ simula una MT universal U en su cinta actual. 4. Si U acepta, entonces M’ acepta. Si U nunca acepta, entonces M’ tampoco aceptará nunca. La anterior descripción de M’ debería bastar para convencerle de que se podría diseñar una máquina de Turing que transformara el código de M y la cadena w en el código correspondiente a M’. Es decir, existe un algoritmo que permite llevar a cabo la reducción Lu Lne de a . Vemos también que si M acepta w, entonces M’ aceptará cualquier entrada x que estuviera originalmente en su cinta. El hecho de que x sea ignorada es irrelevante; la definición de aceptación por una MT establece que lo que la MT acepta es lo que haya en su cinta antes de comenzar a operar. Por tanto, si M acepta w, entonces el Lne código correspondiente a M’ pertenece a . Inversamente, si M no acepta w, entonces M’ nunca acepta, independientemente de cuál sea su entrada. Por tanto, en este caso, el Lne Lu Lne código para M’ no pertenece a . Hemos reducido satisfactoriamente a aplicando el algoritmo que construye M’ a partir de M y w; podemos concluir que, dado

que

Lu

no es recursivo,

Lne

tampoco lo es. La existencia de esta reducción es

suficiente para completar la demostración. Sin embargo, para ilustrar la influencia de esta Lne reducción, vamos a llevar este argumento un paso más allá. Si fuera recursivo, entonces podríamos desarrollar un algoritmo para Lu de la forma siguiente: 1. Convertimos ( M , w ) en la MT M’ como anteriormente. Lne 2. Utilizamos el algoritmo hipotético para para determinar si resulta o no que L ( M’) = /0. En caso afirmativo, decimos que M no acepta w; y si L ( M’) ≠θ, entonces decimos que M acepta w. Dado que, de acuerdo con el Teorema 3, sabemos que no existe tal algoritmo para hemos llegado a una contradicción de la hipótesis que establecía que y concluimos que

Lne

Lne

Lu

,

era recursivo,

no es recursivo.

Ahora ya conocemos el estado de Le. Si Le fuera RE, entonces por el Teorema 9.4, tanto Lne Lne él como serían recursivos. Dado que, de acuerdo con el Teorema 4, no es recursivo, podemos concluir que: TEOREMA 4 Le

no es RE.