Lista de exercicios

Prévia do material em texto

Lista de Exerc´ıcios de Teoria da Computac¸a˜o
Campus de Sorocaba da UFSCar
Prof. Jose´ de Oliveira Guimara˜es
Para facilitar a resoluc¸a˜o dos exerc´ıcios, voceˆ pode assumir que o alfabeto da MT e´ composto
apenas por 0, 1 e espac¸o. A menos de menc¸a˜o em contra´rio, todas as entradas para uma MT e´
um nu´mero inteiro em bina´rio. Usamos < a, b > para a codificac¸a˜o dos nu´meros a e b. Enta˜o uma
codificac¸a˜o poss´ıvel poderia ser
< ., . >: N2−→N tal que < a, b >= 2a(2b + 1)	 1
no qual x 	 y e´ igual a x − y se x − y > 0 ou 0 caso contra´rio. Esta codificac¸a˜o e´ uma func¸a˜o
bijetora (na˜o precisaria ser). A func¸a˜o sg : N−→N retorna 1 se x > 0 e 0 se x = 0.
Usamos < M > para a codificac¸a˜o da MT M e M(x) para o resultado que a MT M produz
com entrada x. Se M na˜o parar a sua execuc¸a˜o, escrevemos M(x) ↑. Se parar, podemos escrever
M(x) ↓. Um enumerador e´ uma MT com duas fitas que ignora a sua entrada e escreve nu´meros
na segunda fita, separados por brancos. Os nu´meros da segunda fita fazem parte de um conjunto
recursivamente enumera´vel.
Seja S o conjunto de todas as linguagens sobre {0, 1}, 2N o conjunto de todas as func¸o˜es de
N em {0, 1}, NN o conjunto de todas as func¸o˜es de N em N, T o conjunto de todas as ma´quinas
de Turing e TD o conjunto de todas as MT de decisa˜o (a cada uma delas esta´ associada uma
linguagem).
Usamos (*) para os exerc´ıcios mais importantes.
Questo˜es
1. (*) Desenhe a a´rvore de execuc¸a˜o de uma MT na˜o determin´ıstica de decisa˜o com certa entrada
x, mostrando todos os poss´ıveis casos (retorna 0, 1 ou na˜o pa´ra). Esta questa˜o pede apenas um
esboc¸o do que pode acontecer, na˜o e´ necessa´rio utilizar um exemplo real de MT. O que representa
cada ve´rtice da a´rvore? E as folhas?
2. Baseado na a´rvore da questa˜o anterior, mostre porqueˆ a simulac¸a˜o de uma MTND por uma
MT determin´ıstica que utiliza busca em profundidade na a´rvore de execuc¸a˜o na˜o funciona.
3. Explique como funciona uma MT determin´ıstica M que simula a execuc¸a˜o de uma MT na˜o
determin´ıstica N .
4. Fac¸a uma MT que soma dois nu´meros dados como entrada em una´rio e separados por um u´nico
branco.
5. Fac¸a uma MT que soma dois nu´meros dados como entrada em bina´rio.
6. Fac¸a uma MT que decida a linguagem L = {2 ∗ n : n ∈ N}.
7. (*) Fac¸a uma MT que decida a linguagem L = {2n : n ∈ N}.
1
8. Explique as diferenc¸as entre uma MT e um autoˆmato finito.
9. Um certo tipo de MT chamado de MTDir permite apenas movimentos para a direita. Este tipo
de ma´quina de Turing permite realizar qualquer computac¸a˜o? Sena˜o, elas teˆm o poder de qual
outro tipo de autoˆmato?
10. Um certo tipo de MT chamado de MTDir2 permite apenas movimentos para a direita e, apo´s
um destes movimentos, um u´nico movimento para a esquerda, depois do qual deve ser feito um
outro movimento para a direita. Se a ma´quina tenta fazer dois movimentos para a esquerda em
sequeˆncia ela pa´ra. Este tipo de ma´quina de Turing permite realizar qualquer computac¸a˜o? Sena˜o,
elas teˆm o poder de qual outro autoˆmato?
11. Explique as diferenc¸as entre uma MT e uma MT de decisa˜o.
12. (*) Seja M uma ma´quina de Turing qualquer (que sempre toma um elemento de Σ? como
paraˆmetro). Enta˜o
M ′(x) = if M(x) > 0 then 1 else 0 e´ uma MT de decisa˜o?
13. Toda MT que retorna 0 ou 1, quando termina, e´ uma MT de decisa˜o?
14. Toda MT que sempre termina e´ uma MT de decisa˜o?
15. Mostre como construir uma MT de uma u´nica fita que simula uma MT com duas fitas.
16. (*) Mostre como construir uma MT de uma u´nica fita que simula uma MT com k > 1 fitas.
17. M e´ uma MT com uma fita infinita em ambas as direc¸o˜es. Construa uma MT M ′ com uma
fita infinita em apenas uma das direc¸o˜es que simula M .
18. M e´ uma MT com uma fita infinita em apenas uma das direc¸o˜es (como as MT do livro
do Sipser). Construa uma MT M ′ com uma fita infinita em ambas as direc¸o˜es que simula M .
Cuidado, na˜o e´ completamente trivial.
19. Uma MT com uma fita com ce´lulas numeradas 0, 1, 2, . . . possui mais ce´lulas do que uma MT
com ce´lulas numeradas . . .− 2,−1, 0, 1, 2, . . .? Prove a sua afirmac¸a˜o.
20. (*) Uma MT com k > 1 fitas possui mais ce´lulas do que uma MT com uma u´nica fita? Prove!
21. Que conceitos estudados na disciplina “Matema´tica Discreta” esta˜o sendo utilizados em “Teoria
da Computac¸a˜o”?
22. Cada linguagem recursiva esta´ associada a pelo menos uma ma´quina de Turing. O conjunto
das MTs e´ enumera´vel. Prove que Rec, o conjunto de todas as linguagens recursivas e´ enumera´vel.
23. Sendo L uma linguagem qualquer, prove que L e´ enumera´vel (S e´ enumera´vel se S ∼ N ou S
e´ finito).
2
24. (*) Prove que existem linguagens que na˜o podem ser decididas por nenhuma MT.
25. (*) Enuncie o teorema de Church-Turing (algumas vezes chamado apenas de Teorema de
Church). Explique-o.
26. Deˆ exemplo de uma linguagem recursivamente enumera´vel (computacionalmente enumera´vel).
27. (*) Deˆ exemplo de uma linguagem recursivamente enumera´vel (r.e ou c.e.) que na˜o seja
recursiva.
28. (*) Fac¸a um enumerador para o conjunto dos nu´meros pares.
29. Deˆ exemplo de uma linguagem que na˜o seja r.e.
30. Fac¸a uma MT que escreva os nu´meros inteiros na fita, sendo dois nu´meros separados por
branco. Isto e´, fac¸a um enumerador para o conjunto N. Naturalmente, a ma´quina nunca ira´ parar.
31. (*) Dada uma MT M , podemos construir uma outra ma´quina de Turing N com treˆs fitas que
escreve na primeira fita os nu´meros inteiros, sendo dois deles separados por um branco e simule:
(a) o primeiro passo da execuc¸a˜o de M com entrada 0. As simulac¸o˜es sa˜o feitas na segunda fita;
(b) o segundo passo da execuc¸a˜o de M com entrada 0 e o primeiro passo da execuc¸a˜o de M com
entrada 1;
(c) o terceiro passo da execuc¸a˜o de M(0), o segundo passo de M(1), o primeiro passo de M(2);
(d) e assim por diante.
Quando uma computac¸a˜o pa´ra, a entrada e´ escrita na terceira fita, precedida de um espac¸o em
branco. Isto e´, quando M(n) pa´ra, unionsqn e´ escrito na terceira fita. Formalize o algoritmo dado acima
usando s´ımbolos para “o n-e´simo passo da execuc¸a˜o de M(x)”.
32. Dada uma MT M , descreva uma outra ma´quina de Turing que enumere o domı´nio de M , isto
e´, o conjunto {x : M(x) ↓}.
33. Usando a mesma te´cnica da questa˜o anterior, e´ poss´ıvel enumerar os elementos do conjunto
{x : M(x) ↑} ?
34. (*) Prove que, se uma linguagem L e´ recursiva, enta˜o L e´ r.e.
35. (*) Prove que, se L e´ recursiva, Lc = Σ? − L e´ recursiva.
36. (*) Prove que, se L e Lc sa˜o recursivamente enumera´veis, L e Lc sa˜o recursivas.
37. (*) Sejam ML e MK MTs que decidem as linguagens L e K, respectivamente. Escreva a
linguagem decidida por cada uma das ma´quinas abaixo.
(a) M1(x) = sg(ML(x) + MK(x))
3
(b) M2(x) = ML(x) ∗ (1−MK(x))
(c) M3(x) = ML(x) ∗MK(x)
(d) M4(x) = 1−ML(x)
(e) M5(x) = 1−M1(x)
38. (*) Considere um procedimento
int teste(X, Y) {
return 1 - Resultado(X, Y);
}
no qual:
(a) X e Y sa˜o inteiros (na˜o limitados a quatro bytes);
(b) <teste> e´ uma codificac¸a˜o de teste (o nu´mero inteiro que representa esta func¸a˜o);
(c) Resultado e´ uma func¸a˜o que toma uma codificac¸a˜o de uma MT M de decisa˜o como primeiro
paraˆmetro e uma entrada x para esta MT como segundo paraˆmetro e retorna o resultado de
M(x).
Enta˜o podemos fazer
teste(<teste>, <teste>)
O que provamos? Explique detalhadamente o seu racioc´ınio.
39. (*) O que e´ uma MT Universal? Quantas MT universais existem? Uma MT universal sempre
pa´ra o seu processamento?
40. Seja U uma MT Universal que e´ executada como U(< M >, x) e que retorna na˜o M(x) mas
M(x) + 1 (assim U nunca retorna 0). Seja Us(< M >, x) a aplicac¸a˜o de U por s passos. Se depois
de s passos a ma´quina M parou, o valor retornado por U e´ M(x). Sena˜o Us(< M >, x) = 0.
Descreva o conjuntoSM = {x : ∃s Us(< M >, x) > 0}
Observe que fixamos a ma´quina M . Para cada M ha´ um conjunto diferente.
41. (*) Uma MT M computa uma certa func¸a˜o f (enta˜o M sempre pa´ra a sua execuc¸a˜o). Mostre
que existem infinitas MTs que computam f . Mostre como construir explicitamente estas ma´quinas.
42. Seja M0,M1,M2, . . . uma enumerac¸a˜o de todas as ma´quinas de Turing que sempre param a
sua execuc¸a˜o (admita que isto seja poss´ıvel). Considere agora a MT
M(x) = Mx(x) + 1
Assuma que e´ poss´ıvel implementar M (e´ poss´ıvel mesmo, apesar de M utilizar um ı´ndice x em
Mx(x)). Pergunta-se: M sempre pa´ra? Se sim, enta˜o M esta´ na lista M0,M1,M2, . . ., na˜o? Enta˜o
4
M = Me para algum e. Derive uma contradic¸a˜o com este fato. Dica: fac¸a x = e na definic¸a˜o de
M .
43. (*) Seja H = {< M > unionsqx : M(x) ↓}. Prove que H na˜o e´ recursiva.
44. Prove que S ∼ 2N. Dica: para descobrir a func¸a˜o f ∈ 2N que esta´ associado a uma linguagem
L ∈ S, primeiro fac¸a uma enumerac¸a˜o dos elementos de L. Associe esta enumerac¸a˜o a f(0), f(1),
f(2), etc.
45. (*) Prove que [0, 1] ∼ 2N.
46. Encontre uma func¸a˜o bijetora entre o conjunto de todas as linguagens sobre {0, 1} e o conjunto
[0, 1].
47. Explique porqueˆ TD ∼ T . Dica: ambas sa˜o enumera´veis.
48. (*) Fac¸a um diagrama de Venn mostrando os conjuntos de linguagens R (regular), LLC
(livres de contexto), LSC (sens´ıveis ao contexto), LEF (estrutura de frase), Rec (recursivas) e RE
(recursivamente enumera´veis).
49. Explique o que e´ TIME(f). Deˆ exemplo de linguagens em TIME(n) e TIME(nk), k > 1 de
sua escolha.
50. Explique o que e´ SPACE(f). Deˆ exemplo de linguagens em SPACE(n).
51. (*) Uma MT executa por t passos. Enta˜o no ma´ximo quantas ce´lulas diferentes da fita ela
utilizou? Isto e´, qual, no ma´ximo, o espac¸o utilizado pela MT? Conclua que se L ∈ TIME(n)
enta˜o L ∈ SPACE(n). Mais geralmente, se L ∈ TIME(f), enta˜o L ∈ SPACE(f).
52. Suponha que uma MT M na˜o determin´ıstica sempre tem dois caminhos a escolher em cada
passo (qualquer MT na˜o determin´ıstica pode ser modificada para que isto seja verdade). Enta˜o
depois de t passos, quantas folhas, no pior caso, possui a a´rvore que mostra todas as computac¸o˜es
poss´ıveis da MT? Se M executa em tempo polinomial, nk para algum k, qual o tempo de execuc¸a˜o
de uma MT determin´ıstica que simula a execuc¸a˜o de todos as escolhas poss´ıveis com dada entrada?
53. Deˆ exemplo de duas linguagens pertencentes a` classe P .
54. (*) Deˆ exemplo de duas linguagens da classe NP .
55. (*) Explique porqueˆ, se as MT M e R executam em tempo polinomial, a composic¸a˜o delas
tambe´m executa em tempo polinomial. Isto e´, M ′(x) = M(R(x)) tambe´m executa em tempo |x|k
para algum k. Dicas: assuma que R execute em tempo nk e M em tempo nm no qual n = |x| e´ o
nu´mero de ce´lulas da entrada (que e´ tambe´m o nu´mero de bits da entrada). A sa´ıda de R tem no
ma´ximo quantas ce´lulas? Qual e´ a entrada para M na composic¸a˜o M(R(x)) ?
56. Explique o que e´ a reduc¸a˜o polinomial. Quando uma linguagem L e´ redut´ıvel polinomialmente
a uma linguagem K?
5
57. Suponha que L e´ redut´ıvel polinomialmente a K (L 6P K) e K 6P SAT . Enta˜o temos
L 6P SAT ?
58. Suponha que SAT 6P L. Mostre que qualquer linguagem em NP e´ polinomialmente redut´ıvel
a L.
59. A linguagem L da questa˜o anterior e´ NP-completa? Se na˜o, escreva as condic¸o˜es necessa´rias
para que ela seja.
60. (*) Se L ∈ NP , K ∈ NP e temos SAT 6P L e L 6P K, enta˜o SAT 6P K. Isto quer dizer
que ambas L e K sa˜o NP-completas?
61. (*) Uma linguagem L e´ redut´ıvel a SAT por uma MT R que executa em tempo n3 e que
produz sa´ıdas de tamanho |x|2 sendo |x| a entrada de R. Suponha que foi encontrado uma MT
M que decida SAT em tempo n5. Usando a reduc¸a˜o de L a SAT atrave´s de M e R, qual a
complexidade da MT M(R(x)) que decide L?
6