Aula 16 - Indecidibilidade -------------------------- Classes de linguagens: - recursivamente enumeraveis (RE): que sao aceitas por uma MT - recursivas: aceitas por uma MT que sempre para, quer a palavra seja aceita ou nao - nao recursivamente enumeraveis (nao-RE): nao existe uma MT que aceite a linguagem Uma linguagem e´ DECIDIVEL se for recursiva e INDECIDIVEL, caso contrario. 1) Exemplo de uma linguagem nao-RE: linguagem da diagonalizacao (Ld) ----------------------------------------------------------------- Ld={w_i em {0,1}* | w_i e´ a codificacao de uma MT M tal que w_i nao pertence a L(M)} - Codificacao de uma MT em binario: Dada uma MT M=(Q, {0,1}, gama, delta, q1, B, F) e´ possivel codificar os elementos da maquina da seguinte forma: Q={q1,...qn}: q1 e´ codificado como 0^1, q2 e´ codificado como 0^2,... sendo q2 o unico estado final gama={X1,...Xs}, onde X1 corresponde a zero e e´ codificado como 0^1, X2 corresponde a 1 e e´ codificado como 0^2, X3 corresponde a B e e´ cofificado como 0^3, e os demais simbolos sao codificados como 0^n, n>3 as direcoes {L,R}: D^1=L e´ codificado como 0 e D^2=R como 00 delta(qi, X_j)=(q_k,X_l, D_m) e´ codificado da seguinte forma: 0^i 1 0^j 1 0^k 1 0^l 1 0^m Assim, o codigo de uma MT inteira consiste de todos os codigos para as suas transicoes separadas por "11". C_1 11 C_2 11 C_3 11 ... 11 C_n onde cada C_i corresponde a codificacao de uma transicao. Exemplo: M=({q1,q2,q3}, {0,1},{0,1,B}, delta, q1, B, {q2}), onde delta(q1,1)=(q3,0,R) 0100100010100 = C1 delta(q3,0)=(q1,1,R) 0001010100100 = C2 delta(q3,1)=(q2,0,R) 00010010010100 = C3 delta(q3,B)=(q3,1,L) 0001000100010010 = C4 - para codificar a MT e a entrada w para a maquina em uma mesma fita, pode ser usada a seguinte convencao: C1 11 C2 11 C3 11 C4 111 w - com esta codificacao podemos falar da i-esima MT: a MT M cujo codigo binario w_i, o i-esimo string binario. Muitos strings nao correspondem a qualquer MT (por ex. quando contem 2 uns consecutivos. Neste caso, consideramos que a MT w_i contem um unico estado e nenhuma transicao. Assim, L(M_i) = {}. - linguagem da diagonalizacao Ld: i\j 1 2 3 4 5 6 7 .... ------------------------------ 1 | 0 1 1 0 ... <-- vetor caracteristico da linguagem L(M_i): 2 | 1 1 0 0 ... 0 se w_j nao pertence a L(M_i) 3 | 0 0 1 1 ... 1 se w_j pertence a L(M_i) 4 | 0 1 0 1 ... 5 | 7 | Os valores da diagonal informam de M_i aceita w_i. Para construir L_d, a diagonal e´ complementada. No exemplo acima, ela comecaria com 1000. Assim, L_d conteria w_1 = epsilon, nao conteria w_2 a w_4 que sao 0, 1, 00 e assim por diante. Caracteristica do complemento da diagonal: ela discorda em pelo menos uma coluna com cada linha da tabela. Teorema 1: Ld nao e´ uma linguagem recursivamente enumeravel. Prova: Suponha que Ld seja L(M) para alguma MT M. Tendo em vista que Ld e´ uma linguagem sobre o alfabeto {0,1}, M estaria na lista de maquinas de Turing descrita acima. Assim, existe i tal que M_i=M. Agora, determinamos de w_i pertence a Ld: - se w_i esta´ em Ld entao M aceita w_i. Entretanto, por definicao w_i nao esta em Ld, ja´ que Ld contem somente os valores w_i tais que M_j nao aceita w_j. - se w_i nao esta´ em Ld, entao M_i nao aceita w_i. Portanto, por definicao w_i esta´ em Ld. Como w_i nao pode estar em Ld nem pode deixar de estar em Ld, concluimos que ha´ uma contradicao na suposicao de que M existe. Concluimos que Ld nao e´ RE. Linguagens RE, mas nao recursivas --------------------------------- - A existencia de uma MT que sempre para corresponde a nocao informal de algoritmo. - A pertinencia a uma linguagem L e´ decidivel se L for recursiva e indecidivel, caso contrario. - A existencia de um algoritmo para resolver um problema e´ muitas vezes mais importante que a existencia de uma MT para resolver o problema. Propriedades: ------------- Teorema 2: se L e´ uma linguagem recursiva, o complemento de L tambem e´. Prova: Seja L=L(M) de uma MT M que sempre para. Construimos uma maquina M-, que aceita o complemento de L da seguinte forma: - os estados de aceitacao de M passa a ser estados de nao aceitacao de M- - M- tem um novo estado de aceitao qf - para todo par (q,a), onde q e´ um estado de nao aceitacao de M e a um simbolo para o qual q nao tem transicao a partir de q, incluir delta(q,a) = (qf,a,R) Tendo em vista que M tem garantia de parar, M- tambem tem. Alem disso, M- aceita exatamente as palavras que M nao aceita. Assim, M- aceita o complemento de L. Teorema 3: se uma linguagem L e´ RE e seu complento e´ RE entao L e´ recursiva. Prova: basta rodar as MT que aceitam L e seu complemento em paralelo. Assim, dada uma linguagem L e sem complemento L' so´ e´ possivel que: 1. L e L' sao ambas recursivas 2. L e L' sao ambas nao-RE 3. L e´ RE e L' e´ nao-RE Exemplo de linguagem RE, mas nao recursiva: linguagem universal (Lu) -------------------------------------------------------------------- Lu = { (M,w) | M e´ a codificacao de uma MT e w pertence a L(M)} Construcao da MT U tal que Lu= M(U): 4 fitas: primeira: (M, w) como codificado para Ld segunda: fita simulada de M com os simbolos codificados como seq. de zeros separados por 1´s terceira: estado de M quarta: rascunho (se for necessario fazer deslocamentos de casas nas fitas 2 e 3 operacao: 1. examinar se a entrada na fita corresponde a codificacao de MT valida. Se nao for, para sem aceitar. 2. Inicializar fita 2 com w na forma codificada 3. Inicializar a fita 3 com o estado inicial 0 4. simular movimento de M: procura na fita 1 uma transicao 0^i 1 0^j 1 0^k 1 0^l 1 0^m tal que 0^i e´ o estado na fita 3 e O^j e´ o simbolo que comeca na posicao corrente da fita 2. Se encontrar: - muda o conteudo da fita 3 para 0^k (muda de estado) - substituir 0^j por 0^l na fita 2 - mover a cabeca de leitura/gravacao na fita de acordo com 0^m (L=0, R=00) Assim, U simula M com entrada w e portanto Lu e´ RE. Teorema 4: Lu nao e´ recursiva. Prova: Ideia: reducao de Ld para o complemento de Lu Suponha que Lu seja recursiva. Pelo Teorema 2, complemento de Lu (Lu') tambem e´ recursivo e portanto existe uma MT M que aceita Lu'. Vamos mostrar que a partir de M podemos construir uma MT M´ que aceita Ld. Como sabemos que Ld nao e´ RE, temos uma contradicao de que Lu e´ recursiva. Reducao: dada uma entrada w para M´, trocar a entrada por w111w e simular esta entrada por M. Suponha que M seja a i-esima MT M_i. Como M_i aceita Lu', o resultado sera´ de aceitacao se w_i nao pertence a L(M_i) e de nao aceitacao, caso contrario. Ou seja, M´=M_i aceita w se e somente se w pertence a Ld. Como sabemos que Ld nao e´ RE, concluimos que a suposicao da existencia de M que aceita o complemento de Lu e´ falsa. Como Lu e´ RE, mas seu complemento nao e´ RE, Lu nao e´ recursiva.