Teoria da Computabilidade

Computabilidade e decidibilidade

Os problemas relevantes que estudamos são problemas de decisão e reconhecimento de linguagens, ou cálculo de funções. É então relevante definir formalmente o que significa reconhecer/decidir uma linguagem e calcular uma função.

Para um alfabeto Σ\Sigma, uma linguagem LΣL \subset \Sigma^* e uma função f:ΣΣf: \Sigma^* \to \Sigma^*, dizemos que:

  • Uma linguagem LL diz-se reconhecível se existe uma máquina de Turing MM com alfabeto de entrada/saída Σ\Sigma tal que Lac(M)=LL_{ac}(M) = L. Denotamos por RΣ\mathcal{R}^\Sigma o conjunto de todas as linguagens reconhecíveis sobre o alfabeto Σ\Sigma.
  • Uma linguagem LL diz-se decidível se existe uma máquina de Turing MM com alfabeto de entrada/saída Σ\Sigma tal que Lac(M)=LL_{ac}(M) = L e Lrj(M)=LL_{rj}(M) = \overline{L}. Denotamos por DΣ\mathcal{D}^\Sigma o conjunto de todas as linguagens decidíveis sobre o alfabeto Σ\Sigma.
  • Uma função ff diz-se computável se existe uma máquina de Turing MM com alfabeto de entrada/saída Σ\Sigma tal que f=ϕMf = \phi_M. Denotamos por CΣ\mathcal{C}^\Sigma o conjunto de todas as funções computáveis sobre o alfabeto Σ\Sigma.

O seguinte resultado diz-nos que podemos concentrar-nos apenas em reconhecer/decidir linguagens:

Proposição

Seja Σ\Sigma um alfabeto. Sejam f:ΣΣf: \Sigma^* \to \Sigma^* uma função e Gf={x$y:f(x)=y}G_f = \{ x \text{\textdollar} y : f(x) = y \}, com $Σ\text{\textdollar} \notin \Sigma. Então:

  1. ff é computável se e só se GfG_f é reconhecível;
  2. se ff é total, ff é computável se e só se GfG_f é decidível.
Prova

Prova de 1

Suponha-se que ff é computável e considere-se a máquina de Turing MfM_f que computa ff. Criamos uma máquina de Turing com duas fitas que:

  • copia xx para a segunda fita;
  • computa ff (usando MfM_f) sobre xx;
  • compara o output de MfM_f com yy, aceitando se estes forem iguais. Evidentemente que esta máquina reconhece GfG_f.

Agora suponha-se que GfG_f é reconhecível e seja RR a máquina de Turing que a reconhece. Considere-se a máquina de Turing com 3 fitas tal que:

  1. na primeira fita está o input xx;
  2. escolhe não-deterministicamente uma palavra yΣy \in \Sigma^* - uma palavra que vamos verificar se é o resultado de f(x)f(x) - e coloca-a na fita 3;
  3. coloca na segunda fita x$yx \text{\textdollar} y;
  4. executa RR sobre a segunda fita: se RR aceitar a palavra na fita 2, termina, caso contrário volta ao passo 2.

Esta máquina calcula ff: quando termina (pois RR aceitou a palavra na segunda fita), a palavra yy (o output esperado) está na última fita (onde o output deve estar).

Observe-se que, para cada xΣx \in \Sigma^* , existe no máximo uma palavra do tipo x$yx\text{\textdollar}y que é reconhecida por RR. Logo, a árvore de computações desta máquina para o input xx tem no máximo uma computação de aceitação.

A prova de 2 é semelhante.

Propriedades

Nesta secção vão ser enunciadas várias propriedades sobre a decibilidade de linguagens. É bastante relevante entender a justificação por detrás destas propriedades. Muitas vezes estas justificações usam raciocínios muito semelhantes aos que podem ser usar para justificar a decibilidade de outras linguagens. Nomeadamente, vai ser usada muitas vezes (nesta e na próxima secção) a ideia de definir uma máquina que decida uma linguagem a partir de máquinas que decidem linguagens já conhecidas. Esta ideia é muito importante e útil.

Seja Σ\Sigma um alfabeto e L,L1,L2ΣL, L_1, L_2 \subset \Sigma^* linguagens decidíveis. Então,

  1. \emptyset,
  2. Σ\Sigma^*,
  3. L\overline{L}
  4. L1L2L_1 \cup L_2,
  5. L1L2L_1 \cap L_2,
  6. L1L2L_1 \setminus L_2

são linguagens decidíveis.

Prova

(1) Basta considerar que a máquina de Turing que ao receber qualquer input vai para o estado de rejeição reconhece \emptyset;

(2) Basta considerar que a máquina de Turing que ao receber qualquer input vai para o estado de aceitação reconhece Σ\Sigma^*;

(3) Se MM for a máquina de Turing que decide LL, basta trocar os estados de aceitação e rejeição para decidir L\overline{L}.

(4) Sejam M1M_1 e M2M_2 máquinas de Turing que reconhecem L1L_1 e L2L_2, respetivamente. Considere-se a máquina de Turing MM com duas fitas. A máquina começa por copiar o input para a segunda fita. Então, executa M1M_1 na fita 1:

  • se M1M_1 aceitar o input, MM termina no estado de aceitação; caso contrário, executa M2M_2 na fita 2:
  • se M2M_2 aceitar o input, MM termina no estado de aceitação; caso contrário, MM termina no estado de rejeição.

(5) Basta observar que L1L2=L1L2L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}}. Como L1L_1 e L2L_2 são decidíveis, L1\overline{L_1} e L2\overline{L_2} também o são. Então, segundo 4., L1L2\overline{L_1} \cap \overline{L_2} também é decidível e, mais uma vez, L1L2\overline{\overline{L_1} \cap \overline{L_2}}.

(6) Basta observar que L1L2=L1L2L_1 \setminus L_2 = L_1 \cap \overline{L_2}. Como L2L_2 é decidível, L2\overline{L_2} é decidível e segundo 4. L1L2L_1 \cap \overline{L_2} é decidível.

Seja Σ\Sigma um alfabeto e L,L1,L2ΣL, L_1, L_2 \subset \Sigma^* linguagens reconhecíveis. Então,

  1. \emptyset,
  2. Σ\Sigma^*,
  3. L1L2L_1 \cup L_2,
  4. L1L2L_1 \cap L_2,

são linguagens reconhecíveis.

Prova

(1) \emptyset é decidível e todas as linguagens decidíveis são reconhecíveis;

(2) Σ\Sigma^* é decidível e todas as linguagens decidíveis são reconhecíveis;

(3) Sejam M1M_1 e M2M_2 máquinas de Turing que reconhecem L1L_1 e L2L_2, respetivamente. Definimos a máquina de Turing NN que escolhe não deterministicamente entre executar M1M_1 e M2M_2. Se a computação de uma destas máquinas terminar em aceitação, NN termina também em aceitação. NN reconhece L1L2L_1 \cup L_2 pelo que esta linguagem é reconhecível.

(4) Sejam M1M_1 e M2M_2 máquinas de Turing que reconhecem L1L_1 e L2L_2, respetivamente. Considere-se a máquina de Turing NN com duas fitas que, ao receber ωΣ\omega \in \Sigma^* como input, copia ω\omega para a fita 2 e, de seguida, executa alternadamente um passo da execução de M1M_1 na fita 1 e um passo da execução de M2M_2 na fita 2. Se uma das execuções terminar, então NN prossegue a execução da outra máquina no caso de ter terminado aceitando, e NN rejeita em caso contrário. Se a execução da outra máquina terminar, então NN aceita no caso de ter terminado aceitando, e rejeita em caso contrário. A máquina NN reconhece L1L2L_1 \cap L_2 pelo que esta linguagem é reconhecível.

Se L1L_1 for reconhecível e L2L_2 for decidível, então L1L2L_1 \setminus L_2 é reconhecível.

Prova

Se L2L_2 é decidível, L2\overline{L_2} é também decidível e, consequentemente, reconhecível. Como vimos acima, se L1L_1 e L2\overline{L_2} são reconhecíveis, então L1L2=L1L2L_1 \cap \overline{L_2} = L_1 \setminus L_2 é reconhecível.

NOTA

Note-se como já não é verdade que se LL é reconhecível então L\overline{L} também o é: basta que haja uma palavra em L\overline{L} cuja computação não termine na máquina que reconhece LL para que isto não seja verdade.

Seja LL uma linguagem sobre o alfabeto Σ\Sigma. Então, LL é decidível se e só se LL e L\overline{L} forem reconhecíveis.

Prova

Se LL for decidível, então LL e L\overline{L} são decidíveis e portanto reconhecíveis.

Sejam agora LL e L\overline{L} linguagens reconhecidas por máquinas de Turing R1R_1 e R2R_2, respetivamente. Seja DD a máquina de Turing com duas fitas que copia o input da primeira fita para a segunda e executa, alternadamente, R1R_1 na primeira fita e R2R_2 na segunda. Como LL e L\overline{L} são reconhecíveis, uma destas computações acaba eventualmente. Se for a computação na primeira fita, aceitamos, caso contrário, rejeitamos.
De qualquer forma a computação termina e LL é decidível.

Redução Computável

Nas provas acima e no capítulo anterior, por vezes pegamos em máquinas de Turing que já conhecíamos para criar máquinas de Turing que resolviam problemas que ainda não tínhamos resolvido. A ideia de redução computável consiste exatamente nisso:

Sejam L1L_1 e L2L_2 linguagens sobre os alfabetos Σ1\Sigma_1 e Σ2\Sigma_2, respetivamente. Dizemos que há uma redução computável de L1L_1 para L2L_2, ou simplesmente que L1L_1 se reduz a L2L_2, o que denotamos por L1L2L_1 \leq L_2 se existe uma função total computável f:Σ1Σ2f: \Sigma_1^* \to \Sigma_2^* tal que, para cada ωΣ1\omega \in \Sigma_1^*,

ωL1f(ω)L2\omega \in L_1 \Leftrightarrow f(\omega) \in L_2

Proposição

Sejam L1L_1 e L2L_2 linguagens sobre Σ1\Sigma_1 e Σ2\Sigma_2, respetivamente. Se L1L2L_1 \leq L_2 e L2L_2 é decidível (resp. reconhecível) então L1L_1 é decidível (resp. reconhecível).

Prova

Como L1L2L_1 \leq L_2, existe uma função total computável f:Σ1Σ2f : \Sigma_1^* \to \Sigma_2^* tal que ωL1f(ω)L2\omega \in L_1 \Leftrightarrow f(\omega) \in L_2. Seja FF a máquina de Turing que calcula esta função.
Como L2L_2 é decidível, é também decidida por uma máquina de Turing DD.
Considere-se a seguinte máquina de Turing MM:

  • dado um input ω\omega, MM começa por computar f(ω)f(\omega) tal como FF;
  • computa DD sobre f(ω)f(\omega): se DD terminar qacq_{ac}, MM termina em aceitação, terminando em rejeição caso contrário. Esta máquina decide L1L_1.

A prova para reconhecimento é análoga.

Nota

Para usarmos a ideia de redução computável basta então encontrar uma função ff que reduza uma linguagem L1L_1 a outra L2L_2. Para esta função ff é essencial provar que:

  • ela é total - está definida para todo o input;
  • ela é computável - existe uma máquina de Turing que a computa;
  • satisfaz a propriedade ωL1f(ω)L2\omega \in L_1 \Leftrightarrow f(\omega) \in L_2

Claro está, se alguma destas propriedades não se verificar, a redução computável não está bem definida.

A proposição acima não é no entanto suficiente para verificar se uma linguagem não é computável.

Dado um alfabeto Σ\Sigma distinguimos as seguintes linguagens:

  • LacΣ={M$ω:MMΣ,ωLac(M)}\mathcal{L}_{ac}^\Sigma = \{ M \text{\textdollar} \omega : M \in \mathcal{M}^\Sigma, \omega \in L_{ac}(M) \} - o problema da aceitação;
  • LrjΣ={M$ω:MMΣ,ωLrj(M)}\mathcal{L}_{rj}^\Sigma = \{ M \text{\textdollar} \omega : M \in \mathcal{M}^\Sigma, \omega \in L_{rj}(M) \} - o problema da rejeição;
  • LsuΣ=LacΣLrjΣ\mathcal{L}_{su}^\Sigma = \mathcal{L}_{ac}^\Sigma \cup \mathcal{L}_{rj}^\Sigma - o problema da computação bem sucedida;
  • LabΣ={M$ω:MMΣ e a computac¸a˜o de M sobre ω aborta }\mathcal{L}_{ab}^\Sigma = \{ M \text{\textdollar} \omega : M \in \mathcal{M}^\Sigma \text{ e a computação de } M \text{ sobre } \omega \text{ aborta } \} - o problema do abortamento;
  • LteΣ=LsuΣLabΣ\mathcal{L}_{te}^\Sigma = \mathcal{L}_{su}^\Sigma \cup \mathcal{L}_{ab}^\Sigma - o problema da terminação.

De forma mais intuitiva, podemos pensar que a linguagem LacΣ\mathcal{L}_{ac}^\Sigma consiste nos pares (M,ω)MΣ×Σ(M, \omega) \in \mathcal{M}^\Sigma \times \Sigma^* constituídos por uma máquina de Turing MM e uma palavra ω\omega tais que ωLac(M)\omega \in L_{ac}(M), isto é, ω\omega é aceite por MM.
De forma a podermos representar estes pares por uma palavra, usamos a representação canónica de máquinas, separando esta representação da palavra input por um $\text{\textdollar}. De forma semelhante, LrjΣ\mathcal{L}_{rj}^\Sigma contém pares (M,ω)MΣ×Σ(M, \omega) \in \mathcal{M}^\Sigma \times \Sigma^* tais que ωLrj(M)\omega \in L_{rj}(M), LsuΣ\mathcal{L}_{su}^\Sigma os pares tais que ωLac(M)Lrj(M)\omega \in L_{ac}(M) \cup L_{rj}(M), e por aí em diante.

Proposição

Para um alfabeto Σ\Sigma, as linguagens LacΣ\mathcal{L}_{ac}^\Sigma, LrjΣ\mathcal{L}_{rj}^\Sigma, LsuΣ\mathcal{L}_{su}^\Sigma, LabΣ\mathcal{L}_{ab}^\Sigma e LteΣ\mathcal{L}_{te}^\Sigma são reconhecíveis mas não são decidíveis.

Prova

As demonstrações para as 5 linguagens são semelhantes, pelo que vamos centrar-nos apenas em LteΣ\mathcal{L}_{te}^\Sigma.

Para mostrar que esta linguagem é reconhecível basta calcular para um input M$ωM \text{\textdollar} \omega o valor de rep(ω)rep(\omega) e depois simular MM sobre rep(ω)rep(\omega) como na máquina universal, aceitando assim que a computação de MM sobre rep(ω)rep(\omega) termine (aceitando, rejeitando ou abortando).

Assuma-se agora então que LteΣ\mathcal{L}_{te}^\Sigma é decidível.
Nesse caso existe uma máquina de Turing DD que a decide. Construímos a seguinte máquina TT. Para cada input MM, TT começa por simular DD sobre M$MM \text{\textdollar} M. Se DD aceitar, TT entra num ciclo infinito. Caso contrário, TT aceita.
Verificamos que MM é aceite por TT se e só se a computação de MM dado o input MM não termina.
Como isto se verifica para qualquer máquina de Turing MM temos que, em particular, se M=TM = T, TT é aceite por TT se e só se a computação de TT dado o input TT não termina. Ou seja, TT dado o input termina se e só se TT dado o input TT não termina.
Como isto é uma contradição, conclui-se que a linguagem não é decidível.

Neste vídeo podemos encontrar esta demonstração apresentada de uma forma mais leve.

Nota

O resultado enunciado acima permite-nos provar a indecidibilidade de uma linguagem LL mostrando que uma das linguagens enunciadas reduz a LL (se LL fosse decidível então qualquer linguagem que reduza a ela deve também ser decidível). No entanto é importante perceber o raciocínio por trás da prova, já que raciocínios semelhantes a este podem também ser aplicados frequentemente.

Corolário

Para um alfabeto Σ\Sigma, as linguagens LacΣ\overline{\mathcal{L}_{ac}^\Sigma}, LrjΣ\overline{\mathcal{L}_{rj}^\Sigma}, LsuΣ\overline{\mathcal{L}_{su}^\Sigma}, LabΣ\overline{\mathcal{L}_{ab}^\Sigma} e LteΣ\overline{\mathcal{L}_{te}^\Sigma} não são reconhecíveis.

Teorema de Rice

O seguinte teorema é uma ferramenta bastante genérica para demonstrar a indecidibilidade de linguagens constituídas por máquinas de Turing cujas linguagens satisfaçam alguma propriedade não-trivial.

Teorema de Rice

Sejam Σ\Sigma um alfabeto e LMΣL \subset \mathcal{M}^\Sigma tal que se M1LM_1 \in L e M1M2M_1 \equiv M_2, então M2LM_2 \in L.
Se LMΣ\emptyset \neq L \neq \mathcal{M}^\Sigma então LL é indecidível.

Exemplo

Vamos provar que a linguagem L={MM{a,b}:Lac(M) eˊ um conjunto infinito}L = \{ M \in \mathcal{M}^{ \{a,b\} } : L_{ac}(M) \text{ é um conjunto infinito} \} é indecidível.

Segundo o Teorema de Rice basta mostrar que (1) LL \neq \emptyset, (2) LM{a,b}L \neq \mathcal{M}^{ \{a,b\} }, e (3) MLMMMLM \in L \wedge M \equiv M' \Rightarrow M' \in L.

  1. A máquina de Turing sobre {a,b}\{a,b\} que aceita todas as palavras está em LL. Então LL \neq \emptyset.
  2. A máquina de Turing sobre {a,b}\{a,b\} que não aceita nenhuma palavra não está em LL. Então LM{a,b}L \neq \mathcal{M}^{\{a,b\}}.
  3. Seja MLM \in L. Se MMM' \equiv M, então o seu alfabeto é {a,b}\{a,b\} e MM' aceita infinitas palavras, pelo que MLM' \in L.

Podemos então concluir, segundo o Teorema de Rice, que LL é indecidível.