Revisão Final: Máquinas de Turing, Decidibilidade e Complexidade

Revisão Final de Teoria da Computação

1) Problemas de Decidibilidade e Reconhecimento

1a) Linguagem L: Máquina de Turing (MT) e Movimentos

L = {<M,w> | M move para a direita exatamente 2 vezes quando roda sobre w}

M só pode ler os 2 primeiros caracteres da entrada.

O número de configurações distintas de M é maxconf = |alfabeto da fita|⁵ · |K|. Se M entrar de novo na mesma configuração, ele fará a mesma coisa que fez na primeira vez.

Algoritmo de Decisão:

Rode M em w por maxconf + 1 passos ou até parar ou mover para a direita 3 vezes. Guarde quantas vezes moveu para a direita. Se não parar naturalmente, está em loop infinito.

• Se parou e moveu para a direita 2 vezes, aceite.
• Se parou e moveu para a direita diferente de 2 vezes, rejeite.
• Se moveu para a direita 3 vezes, rejeite.
• Se não moveu para a direita até agora, rejeite (está em loop).
• Se moveu somente 1 vez para a direita, rejeite.
• Se moveu para a direita 2 vezes, continue até atingir o limite de passos. Se continuou 2 vezes para a direita, aceite.
• De outro modo, rejeite.

1b) Linguagem T: Aceitação de MTs

T = {<M> | M é MT que aceita w^R sempre que aceita w}.

1c) Linguagem A: AFD e Cadeias com Número Ímpar de 1s

A = {<M> | M é AFD que não aceita nenhuma cadeia tendo número ímpar de 1}

Processo de Decisão sobre entrada <M>:

1. Construa AFD O que aceite toda cadeia tendo número ímpar de 1.
2. Construa AFD B tal que L(B) = L(M) ∩ L(O).
3. Teste se L(B) = Φ (Vazio) usando o decidor de Vazio para AFD (V_AFD).
4. Se V_AFD aceita, aceite. Se rejeita, rejeite.

1d) Linguagem Q: GLC e Interseção com Linguagem Regular

Q = {<G> | G é GLC sobre {0,1} e 1* ∩ L(G) ≠ Φ}

Linguagens Livres de Contexto (LLC) são fechadas sob interseção com Linguagens Regulares (LR). (LLC ∩ LR = LLC).

Processo de Decisão sobre a entrada <G>:

1. Construa GLC H tal que L(H) = 1* ∩ L(G).
2. Teste se L(H) = Φ usando o decidor de Vazio para GLC (V_GLC), R.
3. Se R aceita, rejeite. Se rejeita, aceite.

2) Propriedades de Classes de Linguagens

2a) Interseção de Linguagens Turing-Reconhecíveis

É possível que L₁ e L₂ sejam Turing-reconhecíveis, mas não decidíveis, e que L₁ ∩ L₂ seja decidível?

Resposta: Sim. Exemplo: PCP ∩ H = Φ, onde PCP é o Problema da Correspondência de Post e H é a Linguagem da Parada. A linguagem vazia (Φ) é regular e, portanto, decidível.

2b) Fechamento de LLC sob Interseção

É possível que, sendo L₁ e L₂ Linguagens Livres de Contexto (LLC), L₁ ∩ L₂ não seja LLC?

Resposta: Sim. As LLCs não são fechadas sob interseção.

Exemplo:

• L₁ = {aⁿ bⁿ c^m | n ≥ 0, m ≥ 0}, que é LLC.
• L₂ = {a^m bⁿ cⁿ | n ≥ 0, m ≥ 0}, que também é LLC.

A interseção L₁ ∩ L₂ = {aⁿ bⁿ cⁿ | n ≥ 0}, que não é LLC.

2c) Fechamento de Linguagens Recursivamente Enumeráveis

A classe das linguagens recursivamente enumeráveis não é fechada sob complemento.

Justificativa: A Linguagem da Parada (H) é reconhecível (recursivamente enumerável), mas seu complemento ($¯{H}$) não é reconhecível. (Resultado clássico).

2d) Redutibilidade e Decidibilidade de L1

É possível que L₁ ≤ L₂ (L₁ é redutível a L₂) e L₂ for Turing-reconhecível, então L₁ é decidível?

Resposta: Sim, é possível.

Exemplo: Seja L₁ = {a} (decidível) e L₂ = H (Linguagem da Parada, Turing-reconhecível, mas não decidível). {a} ≤ H, mas {a} é decidível.

3) Classe de Complexidade: SOMA-SUB

SOMA-SUB = {<S,k> | S é um conjunto de inteiros e existe um subconjunto de S cuja soma é k}

Deve-se dizer a classe de complexidade, justificando a resposta.

Classe de Complexidade: NP

Justificativa: SOMA-SUB (que é equivalente ao problema SUBSET-SUM) pertence à classe NP, pois existe um verificador determinístico em tempo polinomial.

Um verificador determinístico V checa o tamanho do certificado c (o subconjunto). Se for maior que |S|, rejeite. Senão, soma os elementos de c. Se a soma for igual a k, aceite. Caso contrário, rejeite.

O verificador V roda em tempo polinomial porque:

• Ele checa o tamanho de c em tempo $O(|S|)$.
• Ele soma os elementos de c em tempo $O(|c|)$.
• Ele compara a soma com k em $O(k)$.

Portanto, o tempo de V pertence a $O(|<S,k>|)$, confirmando que SOMA-SUB ∈ NP.