Máquinas de Turing não determińısticas

Prévia do material em texto

PUC GOIÁS
ESCOLA DE CIÊNCIAS EXATAS E DA
COMPUTAÇÃO
CMP1067 Projeto e Análise de Algoritmos II
Marco A. F. Menezes
AULA 3
Referências: esta aula está baseada nos seguintes livros,
1. John E. Hopcroft, Jeffrey D. Ullman e Rajeev Motwani. Introdução à
Teoria de Autômatos, Linguagens e Computação. Tradução: Vanden-
berg D. de Souza. Rio de Janeiro: Elsevier, 2002.
2. Ruy E. Campello e Nelson Maculan. Algoritmos e heuŕısticas: desen-
volvimento e avaliação de performance. Niterói/RJ: EDUFF, 1994.
3. Michael Sipser. Introdução à Teoria da Computação. Tradução: Ruy
José Guerra Barretto de Queiroz. São Paulo: Thomson Learning, 2007.
Aula anterior
1.2 Variantes de máquinas de Turing
Definição 1.4 Uma máquina de Turing não determińıstica é uma 7-upla,
(Q,Σ,Γ, δ, q0, qaceita, qrejeita),
em que Q,Σ,Γ são todos conjuntos finitos e
1. Q é o conjunto de estados,
1
2. Σ é o alfabeto de entrada sem o śımbolo em branco ⊔,
3. Γ é o alfabeto de fita, em que ⊔ ∈ Γ e Σ ⊆ Γ,
4. δ : Q × Γ → P(Q × Γ × {E,D}) é a função de transição, com o
contradomı́nio como o conjunto das partes.
5. q0 ∈ Q é o estado inicial,
6. qaceita ∈ Q é o estado de aceitação,
7. qrejeita ∈ Q é o estado de rejeição, onde qrejeita 6= qaceita.
Exemplo Considere uma máquina de Turing não determińıstica definida
por
M = (Q,Σ,Γ, δ, q0, qaceita, qrejeita),
em que
Q = {q0, q1, qaceita, qrejeita}, Σ = {0, 1}, Γ = {0, 1,⊔},
δ(q0, 0) = {(q0, 1, D)}, δ(q0, 1) = {(q1, 0, D)}, δ(q0,⊔) = {(qrejeita, 1, D)},
δ(q1, 0) = {(q1, 0, D), (q0, 0, E)}, δ(q1, 1) = {(q1, 1, D), (q0, 1, E)},
δ(q1,⊔) = {(qaceita,⊔, D)}.
Apresente o diagrama de estados.
Resolução
Teorema 1.1 Toda máquina de Turing não determińıstica tem uma
máquina de Turing (determińıstica) que lhe é equivalente.
A tese de Church-Turing Um problema (de decisão) pode ser resolvido
por um algoritmo se, e somente se, puder ser computado por uma máquina
de Turing que atinge um estado de parada para toda instância do problema.
Exerćıcios para casa Fazer a Lista 1.
Próxima aula Unidade 1 - Revisão: a tese de Church-Turing - resolução
de exerćıcios para casa.
2