Máquinas de Turing: Enumerabilidade e Decidibilidade

Prévia do material em texto

Teoria da Computação 1
Máquinas de Turing: Enumerabilidade e Decidibilidade
Exercícios
Definição: Uma máquina de Turing M enumera uma linguagem L se M, quando iniciada a partir 
de uma fita em branco (Work Tape), roda para sempre e retorna todas e somente as strings em L, 
utilizando uma fita especial para impressão (Output Tape).
Problema 1: Mostre que uma linguagem é turing-reconhecível se e somente se existe algum 
enumerador para L, considerando L sobre um alfabeto {0,1}*.
Nota:
Seja o alfabeto {0,1}*. Para definir uma ordem lexicográfica dizemos que 0 sempre vem antes de 1. 
Dadas duas strings v e w, dizemos que v vem antes de w (v < w) se:
1. |v| < |w| (v é menor que w), ou
2. |v| = |w| e, no primeiro caracter em que v e w são diferentes, o caracter em v vem antes do caracter 
de w.
Por exemplo:
01110 < 00011011 110101 < 110110 11 < 000
Um enumerador lexicográfico para uma linguagem L é um enumerador em que as strings em L são 
impressas em ordem lexicográfica.
Solução:
Parte 1) Se temos um enumerador que enumera uma linguagem L, então uma MT M reconhece L:
M = “Sobre a entrada w:
1) Rode E. Sempre que E retorna uma saída, compare-a com w.
2) Se w aparece na saída de E em algum momento, aceite. Caso contrário continue rodando.”
Parte 2) Se uma MT M reconhece uma linguagem L, podemos construir um enumerador E para L 
usando o seguinte processo:
 
E = “Ignore a entrada
1) Repita o seguinte para i=1, 2, 3 …
2) Rode M por i passos sobre cada entrada w1, w2, … , wi.
3) Se quaisquer computações aceitam, imprima a wj correspondente.”
 
(Problema 3.16 Sipser, pagina 167): 
O algoritmo simplificado abaixo funcionaria?
E = “Ignore a entrada
1. Repita o seguinte para i=1, 2, 3 …
2. Rode M sobre cada entrada wi.
3. Se ela aceita imprima wi.”
 Rode M para: w1, w2, w3, w4, ….
Neste caso, o problema é que M pode não parar para alguma string wk. Neste caso, E nunca 
enumera uma string wi, tal que i>k.
Problema 2: Suponha uma linguagem L sobre um alfabeto {0,1}*. Prove:
a) Se L é decidível então L pode ser enumerado por uma máquina de Turing em ordem estritamente 
crescente, sem repetições. (Strings são ordenadas por tamanho, em quando do mesmo tamanho em 
ordem lexicográfica).
b) Se L for enumerável em ordem estritamente crescente, sem repetições, então L é decidível.
Solução:
a) Dada uma MT D que decide L, é possível construir um enumerador E para L como segue:
E = “Para cada w Є {0,1}* (lexicograficamente, e em ordem), simule D sobre a entrada w.
Se D aceita w então imprima w. Se D rejeita w, não imprima nada. 
Podemos notar que sendo D um decisor, ele pára em todas as entradas w, e assim, E será 
capaz de imprimir ou “saltar” cada elemento de {0,1}* em ordem.
b) Dado um enumerador E para a linguagem L, podemos construir um decisor D:
D = Sobre a entrada w, rode E até que seja impressa uma string de tamanho >= |w| + 1
Se E imprime w então aceita; senão rejeita.
(Aqui estamos considerando que L é uma linguagem infinita)
Exercício 4.2 (Sipser pg 192): Considere o problema de determinar se um AFD e uma expressão 
regular são equivalentes. Expresse esse problema como uma linguagem e mostre que ele é 
decidível.
Solução:
Seja a linguagem LEQ = {< A, R > | A é um AFD, R é uma expressão regular, e L(A) = L(R)}. 
Podemos construir uma MT que decide LEQ tendo os passos: 
T = “Sobre a entrada < A, R >:
1. Converta R no seu AFD A' correspondente.
2. Construa o AFD C (representando a diferença simétrica) que aceita as cadeias aceitas ou 
por A ou por A', mas não por ambas.
3. Verifique que L(C) é vazia. Neste caso, L(A) = L(A').
(ver teorema 4.4 para linguagem vazia e 4.5 para a construção de C.)
Exercício 4.6 (Sipser pg 193): Seja B o conjunto de todas as sequencias infinitas sobre {0,1}. 
Mostre que B é incontável, usando uma prova por diagonalização.
Solução:
Cada elemento em B é uma sequência infinita (b1, b2, b3, . . .), em que bi {∈ 0, 1}. Suponha que B 
seja contável. Então podemos definir uma função f de correspondência entre N e B, N={0,1,2,3 ...}.
Especificamente, para n N∈ , seja f(n) = (bn1, bn2, bn3, . . .):
n f(n) 
1 (b11, b12, b13, b14, b15, . . .)
2 (b21, b22, b23, b24, b25, . . .)
3 (b31, b32, b33, b34, b35, . . .)
4 (b41, b42, b43, b44, b45, . . .)
… …
Seja a sequência c = (c1, c2, c3, c4, c5, . . .) ∈ B sobre {0, 1}, onde ci = 1 − bii. Neste caso, se a 
sequência é:
n f(n)
1 (0, 1, 1, 0, 0, . . .)
2 (1, 0, 1, 0, 1, . . .)
3 (1, 1, 1, 1, 1, . . .)
4 (1, 0, 0, 1, 0, . . .)
… ...
então c = (1, 1, 0, 0, . . .). Assim, c B é diferente de cada sequência em pelo menos um bit. Então∈ 
c não é igual a f(n) para algum n, o que é uma contradição. Desta forma, B é incontável.