Teoria da Computabilidade

Prova de 1

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

• copia $x$ para a segunda fita;
• computa $f$ (usando $M_f$) sobre $x$;
• compara o output de $M_f$ com $y$, aceitando se estes forem iguais. Evidentemente que esta máquina reconhece $G_f$.

Agora suponha-se que $G_f$ é reconhecível e seja $R$ 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 $x$;
2. escolhe não-deterministicamente uma palavra $y \in \Sigma^*$ - uma palavra que vamos verificar se é o resultado de $f(x)$ - e coloca-a na fita 3;
3. coloca na segunda fita $x \text{\textdollar} y$;
4. executa $R$ sobre a segunda fita: se $R$ aceitar a palavra na fita 2, termina, caso contrário volta ao passo 2.

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

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

A prova de 2 é semelhante.

(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 $M$ for a máquina de Turing que decide $L$, basta trocar os estados de aceitação e rejeição para decidir $\overline{L}$.

(4) Sejam $M_1$ e $M_2$ máquinas de Turing que reconhecem $L_1$ e $L_2$, respetivamente. Considere-se a máquina de Turing $M$ com duas fitas. A máquina começa por copiar o input para a segunda fita. Então, executa $M_1$ na fita 1:

• se $M_1$ aceitar o input, $M$ termina no estado de aceitação; caso contrário, executa $M_2$ na fita 2:
• se $M_2$ aceitar o input, $M$ termina no estado de aceitação; caso contrário, $M$ termina no estado de rejeição.

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

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

(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 $M_1$ e $M_2$ máquinas de Turing que reconhecem $L_1$ e $L_2$, respetivamente. Definimos a máquina de Turing $N$ que escolhe não deterministicamente entre executar $M_1$ e $M_2$. Se a computação de uma destas máquinas terminar em aceitação, $N$ termina também em aceitação. $N$ reconhece $L_1 \cup L_2$ pelo que esta linguagem é reconhecível.

(4) Sejam $M_1$ e $M_2$ máquinas de Turing que reconhecem $L_1$ e $L_2$, respetivamente. Considere-se a máquina de Turing $N$ 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 $M_1$ na fita 1 e um passo da execução de $M_2$ na fita 2. Se uma das execuções terminar, então $N$ prossegue a execução da outra máquina no caso de ter terminado aceitando, e $N$ rejeita em caso contrário. Se a execução da outra máquina terminar, então $N$ aceita no caso de ter terminado aceitando, e rejeita em caso contrário. A máquina $N$ reconhece $L_1 \cap L_2$ pelo que esta linguagem é reconhecível.

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

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

Sejam agora $L$ e $\overline{L}$ linguagens reconhecidas por máquinas de Turing $R_1$ e $R_2$, respetivamente. Seja $D$ a máquina de Turing com duas fitas que copia o input da primeira fita para a segunda e executa, alternadamente, $R_1$ na primeira fita e $R_2$ na segunda. Como $L$ e $\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 $L$ é decidível.

Como $L_1 \leq L_2$, existe uma função total computável $f : \Sigma_1^* \to \Sigma_2^*$ tal que $\omega \in L_1 \Leftrightarrow f(\omega) \in L_2$. Seja $F$ a máquina de Turing que calcula esta função.
Como $L_2$ é decidível, é também decidida por uma máquina de Turing $D$.
Considere-se a seguinte máquina de Turing $M$:

• dado um input $\omega$, $M$ começa por computar $f(\omega)$ tal como $F$;
• computa $D$ sobre $f(\omega)$: se $D$ terminar $q_{ac}$, $M$ termina em aceitação, terminando em rejeição caso contrário. Esta máquina decide $L_1$.

A prova para reconhecimento é análoga.

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

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

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

Vamos provar que a linguagem $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) $L \neq \emptyset$, (2) $L \neq \mathcal{M}^{ \{a,b\} }$, e (3) $M \in L \wedge M \equiv M' \Rightarrow M' \in L$.

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

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