01 maquinas de turing

Aula de teoria da computação

1. Máquinas de Turing
Yuri Tavares dos Passos

2. Introdução
●As Máquinas de Turing (M.T.) são úteis
para provar que alguns problemas:
–não podem ser resolvidos ou
–são naturalmente difíceis de se resolver

3. Introdução
●Considere o seguinte problema:
–É possível fazer um programa que diga se um
program em C pode imprimir na tela “hello
world\n”?

4. Introdução

6. Introdução
●Envolve o teorema de Fermat
–Resolvido recentemente!
●O problema geral sobre impressão de
“hello world” é possível ser resolvido?

7. Introdução

8. Introdução

9. Introdução

10. Introdução

11. Introdução
●O que acontece com H
2 quando H
2'
imprime “yes”?
●E quando imprime “hello world”?

12. Introdução
●Se H
2 imprimir “hello world”, significa que a
entrada H
2 não imprimiria tal palavra.
●Se H
2 não imprimir “hello world”, significa
que sua entrada H
2 imprimiria tal palavra
●Absurdo!

13. Linguagens e Problemas
●Nesta disciplina trataremos linguagens
como se fossem problemas a serem
resolvidos
–Pertinência de um string w a uma linguagem
L:
–Dado uma cadeia w em ∑
* , definir se w
está ou não em L.

14. Linguagens e Problemas
●Exemplo: O problema de testar se um
número binário é primo.
●Lp é o conjunto das cadeias dos números
binários que representam um número
binário.

15. Linguagens e Problemas
●Na prática, decidir se faz parte ou não de
um conjunto não generaliza a noção de
problema.
–Um analisador sintático além de
responder sim ou não, também gera
uma árvore sintática.

16. Linguagens e Problemas
●Em alguns momentos, estamos usando
linguagens não como problemas de
decisão:
–{0
n1
n|n≥1}
●Consideramos problemas de decisão
quando queremos provar que ele é difícil

17. Linguagens e Problemas
●Exemplo: Reconhecer se um arquivo texto
em ASCII pertence a linguagem dos
programas C.
–Um compilador C converte um arquivo
ASCII para executável.
–Se o problema de reconhecimento fosse
mais fácil que a conversão, então
usaríamos o conversor para reconhecer.

18. Linguagens e Problemas
●Teríamos uma contradição a hipótese: se o
teste de pertinência a C é difícil, o
problema da conversão também é difícil.

19. Universos das
Linguagens

20. Máquina de Turing
●Motivação de seu estudo:
–Provar para o programador que existem
problemas que não podem ser resolvidos
–Provar que alguns problemas podem ser
resolvidos, mas usam um período de tempo
muito grande
●Convencer ao programador que apenas algumas
instâncias do problema bem especificadas podem
ser resolvidas em tempo hábil

21. Máquina de Turing
●Máquina abstrata
–Seria ineficiente construí-la no mundo real
●Utilizar programas em uma linguagem (C,
Java) dificultam as provas, pois:
–Cada estado de um programa é representado pelas
suas variáveis
–Mais difícil de adaptar problemas como “uma
gramática é ambígua?”, “uma fórmula booleana
pode assumir V como resultado?”

22. Máquina de Turing
●Histórico:
–David Hilbert indagou se era possível encontrar
um algoritmo para determinar a falsidade ou
verdade de uma proposição matemática.
–Kurt Gödel demonstrou o teorema da
incompletude.
–Diversas noções de computação vieram à tona.
●Funções recursivas de Alonzo Church e outras.
–Turing propôs a M.T.

23. Máquina de Turing

24. Máquina de Turing
●M = (Q,Σ,Г,δ,q
0,B,F)
●Q é o conjunto de estados
●Σ é o alfabeto de entrada
●Г é o alfabeto de saída, ou símbolos da fita.
–Σ⊂Г
●δ é a funçao de transição
–δ: Q x Г→ Q x Г x {E,D}
–{E,D} = {L,R} = {←,→}

25. Máquina de Turing
●q
0 é o estado inicial.
–q
0∈Q
●B é o simbolo branco.
–B∈Г e B∉Σ
●F é o conjunto de estados finais.
–F⊆Q

26. Descrição instantânea
●Notação para descrever o que faz a M.T.
●Suponhamos que a esquerda e a direita
de uma D.I. (ou ID) é infinitamente branco.
X
1
X
2
...X
i-1
qX
i
X
i+1
...X
n

27. Descrição instantânea
●Usamos ⊢ para refletir um movimento
●Usamos ⊢
* para indicar zero ou mais
movimentos
●Suponha δ(q,X
i) = (p,Y,L)
–X
1X
2...X
i-1qX
iX
i+1...X
n⊢X
1X
2...pX
i-1YX
i+1...X
n
●Suponha δ(q,X
i) = (p,Y,R)
–X
1X
2...X
i-1qX
iX
i+1...X
n⊢X
1X
2...X
i-1YpX
i+1...X
n

28. Descrição instantânea
●Se i=1 e movimento à esquerda:
–qX
1X
2...X
n⊢qBX
1X
2...X
n
●Se i=n, Y=B e movimento à esquerda:
–X
1X
2...X
n-1qX
n⊢X
1X
2...X
n-2pX
n-1

29. Descrição instantânea
●Se i=1, Y=B e movimento à direita:
–qX
1X
2...X
np
⊢
X
2...X
n
●Se i=n e movimento à direita:
–X
1X
2...X
n-1qX
n⊢X
1X
2...X
n-2YpB

30. Exemplo 1
●Uma M.T. Para reconhecer {0
n1
n|n≥1}
●M = ({q
0,q
1,q
2,q
3,q
4},{0,1},{0,1,X,Y,B},δ,q
0,B,
{q
4})

31. Exemplo 1

32. Exemplo 1
●q
0: estado inicial e M entra toda vez que
retorna ao 0 restante mais à esquerda.
●q
1: indica que deve ir a direita enquanto
for 0 ou Y, troca 1 por Y e anda à direita
para encontrar novos Ys.
●q
2: volta a esquerda até encontrar um X,
andando à esquerda enquanto for Y ou 0.

33. Exemplo 1
●q
3: lê Ys até encontrar um B a direita.
●q
4: estado final, indica que foi reconhecida
a palavra. Trava para indicar
reconhecimento!

34. Exemplo 1
q
00011X
⊢
q
1011X0
⊢
q
111X
⊢
q
20Y1⊢q
2X0Y1⊢
Xq
00Y1XX
⊢
q
1Y1XXY
⊢
q
11XX
⊢
q
2YY⊢
Xq
2XYYXX
⊢
q
0YYXXY
⊢
q
3YXXYY
⊢
q
3B⊢
XXYYBq
4B

35. Exemplo 1
q
00010X
⊢
q
1010X0
⊢
q
110X
⊢
q
20Y0⊢q
2X0Y0⊢
Xq
00Y0XX
⊢
q
1Y0XXY
⊢
q
10 XXY0
⊢
q
1B

36. Diagramas de transição

37. Exemplo 2
●Ao invés de reconhecer uma linguagem,
uma M.T. para calcular.
–m∸n = max(m-n,0)
●M = ({q
0, … ,q
6},{0,1},{0,1,B},δ,q
0,B,{})
●Entrada é da forma: 0
m10
n
–0000100 = 4∸2
●Saída é da forma: 0
m∸n

38. Exemplo 2

39. Exemplo 2

40. Exemplo 2
●q
0: estado inicial. Inicia o ciclo de substituição
de 0 por B. Vai para q
5 se encontrar 1.
●q
1: Pesquisa à direita, passando por 0s até
achar 1. Em seguida vai para q
2.
●q
2: Salta 1s até encontrar 0. Vai para q
4 se
encontrar B e vai para q
3 se encontrar 0,
substituindo-o por 1

41. Exemplo 2
●q
3: M se move à esquerda até encontrar B.
Ao encontrar muda para q
0.
●q
4: Subtração está completa, mas um 0
sem correspondência foi encontrado.Troca
o 1 por B.
●q
5: Troca os símbolos restantes por B ao
final do cálculo.

42. Exemplo 2
●q
6:Pára a máquina quando termina o
cálculo.

43. Exemplo 2
●0000100

44. Linguagens aceitas pela
M.T.
●Seja M = (Q,Σ,Г,δ,q
0,B,F)
●L(M) é o conjunto de strings w tais que q
0w ⊢
* αpβ para
algum p∈F e quaisquer strings α e β.
●O conjunto das linguagens aceitas por M.T. são chamadas
de linguagens recursivamente enumeráveis.
–Recursiva vem de formalismos computacionais anteriores
à M.T.
–Enumeráveis vem da noção que tais strings podem ser
enumeradas (colocadas em ordem) assim como os
conjuntos enumeráveis (ℕ,ℤ,ℚ)

45. Máquina de Turing e sua
parada
●A noção de aceitação está relacionada
comumente a parada da M.T.
–Reconhecimento de {0
n1
n|n≥1}
●Dizemos que a M.T. pára quando entra em
um estado q tal que δ(q,X) é indefinido
–A M.T. para calcular “monus” pára para
qualquer entrada.

46. Máquina de Turing e sua
parada
●Suponhamos que sempre pára quando se
aceita uma string.
●As linguagens das M.T. que sempre param
mesmo quando se rejeita uma string são
consideradas recursivas.

47. Exercícios
●Mostre as D.I.s do Exemplo 1 para: 00,
000111 e 00111
●Projete uma M.T. que reconheça as
seguintes linguagens:
–O conjunto de strings com o número igual de 0s
e 1s.
–{a
nb
nc
n|n≥1}
–{ww
R| w∈{0,1}
*
}

48. Exercícios
●Considere a seguinte Máquina de Turing:
M = ({q
0,q
1,q
2,q
f},{0,1},{0,1,B},δ,q
0,B,{q
f})
Descreva o que faz M se δ for definida com
a) δ(q
0,0)=(q
1,1,R); δ(q
1,1)=(q
1,1,R); δ(q
1,B)=(q
f,B,R)
b) δ(q
0,0)=(q
0,B,R); δ(q
0,1)=(q
1,B,R);
δ(q
1,1)=(q
1,B,R); δ(q
1,B)=(q
f,B,R)
c) δ(q
0,0)=(q
1,1,R); δ(q
1,1)=(q
2,0,L); δ(q
2,1)=(q
0,1,R);
δ(q
1,B)=(q
f,B,R)

49. Referência
●[1] HOPCROFT, John E.; ULLMAN, Jeffrey
D.; MOTWANI, Rajeev. Introdução à teoria
de autômatos, linguagens e computação.
[Rio de Janeiro]: Campus, c2003. p. 328-
352
●Imagens da versão em inglês