Tese de Church-Turing
1
Tese de Church-Turing (1930):
Qualquer computação que possa ser
realizada de maneira mecânica
pode ser feita por uma Máquina de Turing
2
Algoritmo:
Um algoritmo para um problema é uma
Máquina de Turing que resolve este problema
O algoritmo descreve os passos do
procedimento mecânico
Isso pode ser traduzido na forma de
instruções de uma Máquina de Turing
Prof. Busch - LSU
3
Algoritmos são Máquinas deTuring
Quando dizemos:
Existe um algoritmo
Queremos dizer:
Existe uma Máquina de Turing
4
Variantes
de
Máquinas de Turing
5
O Modelo Padrão
Fita Infinita
 aababb cac a
Cabeça de Leitura-Escrita
(Esq. ou Dir.)
Unidade de Controle
Determinista
6
Variantes do Modelo Padão
Máquinas de Turing com: • Opção de não mover
• Fita semi-infinita
• Off-Line
• Múltiplas fitas
• Multidimensional
• Não determinista
7
As variantes formam diferentes
Classes de Máquinas de Turing
Queremos provar:
Cada Classe tem o mesmo
poder de computação do Modelo Padrão
8
Mesmo poder de computação de duas classes:
Ambas as classes de máquinas de Turing
aceitam as mesmas linguagens
9
Mesmo poder de computação de duas classes
Para qualquer máquina
M1
da primeira classe
existe uma máquina
M2
da segunda classe
tal que:
L( M1)  L( M 2 )
e vice-versa
10
Simulação: técnica para provar mesmo poder
Simular a máquina de uma classe
por uma máquina de outra classe
Primeira Classe
Máquina Original
M1
Segunda Classe
Máquina de Simulação
M2
M1
11
Configurações na Máquina Original
correspondem a configurações
na Máquina de Simulação
Máquina Original:
Máquina Simulação:
d0  d1    d n



d 0  d1    d n
12
Configuração Final
Máquina Original:
df
Máquina de Simulação:
d f
A Máquina de Simulação
e a Máquina Original
aceitam a mesma linguagem
13
Máquinas de Turing com Opção Não Move
A cabeça pode permanecer na mesma posição
 aababb cac a
Esquerda, Direita, Não move
movimentos: L,R,S
14
Exemplo:
Instante 1
 aababb cac a
q1
Instante 2
 b ab ab b c ac a
q2
q1
a  b, S
q2
15
Teorema:
Máquinas com opção não move
têm o mesmo poder de computação
que Máquinas de Turing padrão
16
Prova:
Parte 1: Máquinas com opção não move
são pelo menos tão poderosas
quanto máquinas padrão
Prova: uma máquina padrão é também
uma máquina com opção não move
(que nunca usa a opção S)
17
Prova:
Parte 2: Máquinas padrão
são pelo menos tão poderosas quanto
máquinas com opção não move
Prova:
uma máquina padrão pode simular
uma máquina com opção não move
18
Máquina com opção não move
q1
a  b, L
q2
Simulação na Máquina Padrão
q1
a  b, L
q2
Similar para movimentos para a direita
19
Máquina com opção não move
q1
a  b, S
q2
Simulação na Máquina Padrão
q1
a  b, L
qnew
x  x, R
q2
Para todo símbolo
x
20
Exemplo
Máquina com opção não move:
q1 a  b, S q2
1
aaba 
q1
2
baba 
q2
Simulação na Máquina Padrão:
1
aaba 
q1
2
baba 
qnew
3
baba 
q2
21
Máquina Padrão X
Fita com Múltiplas Trilhas
  a b a b 
  b a c d 
trilha 1
trilha 2
um símbolo
22
trilha 1
  a b a b 
  b a c d 
trilha 2
q1
trilha 1
  a c a b 
  b d c d 
trilha 2
q2
q1
(b, a)  (c, d ), L
q2
23
Fita Semi-Infinita
# a b a c  
.........
24
Máquinas de Turing padrão simulam
máquinas com fita semi-infinita:
Trivial
25
Máquinas com fita semi-infinita simulam
máquinas de Turing padrão:
.........
Máquina padrão
.........
Máquina com fita semi-infinita
.........
26
.........
Máquina padrão
.........
 a b c d e  
ponto de referência
Máquina com fita semi-infinita e duas trilhas
parte dir.
# d e  
parte esq. # c b a 


.........
27
Máquina padrão
q1
q2
Máquina com fita semi-infinita
parte esq.
parte dir.
L
q2
R
q2
L
q1
R
q1
28
Máquina padrão
q1
a  g, R
q2
Máquina com fita semi-infinita
parte dir.
R
q1
parte esq.
L
q1
(a, x)  ( g , x), R
( x, a)  ( x, g ), L
para todos os símbolos
R
q2
L
q2
x
29
Instante 1
.........
Máquina padrão
 a b c d e  
.........
q1
Máquina com fita semi-infinita
parte dir.
# d e  
parte esq. # c b a 
L
q1


.........
30
Instante 2
.........
Máquina padrão
 g b c d e  
.........
q2
Máquina com fita semi-infinita
parte dir.
# d e  
parte esq. # c b g 
L
q2


.........
31
Na borda da fita:
Máquina com fita semi-infinita
parte dir.
R
q1
parte esq.
L
q1
(# , # )  (# , # ), R
(# , # )  (# , # ), R
L
q1
R
q1
32
Máquina com fita semi-infinita
Instante 1
parte dir.
# d e  
parte esq. # c b g 


.........
L
q1
Instante 2
parte dir.
# d e  
parte esq. # c b g 
R
q1


.........
33
Teorema:
Máquinas com fita semi-infinita
têm o mesmo poder computacional que
Máquinas de Turing padrão
34
Máquina Off-Line
Arquivo de entrada
a b c
apenas leitura
Unidade de
Controle
fita
leitura / escrita
  g d e  
35
Máquinas off-line simulam
Máquinas de Turing padrão:
Máquina off-line:
1. Copia o arquivo de entrada para a fita
2. Continua a computação como na
Máquina de Turing padrão
36
Máquina padrão

b c  
Máquina off-line
Arquivo de entrada
a
Fita
  a b c 
1. Copia o arquivo de entrada para a fita
37
Máquina padrão
 a b c  
q1
Máquina off-line
Arquivo de entrada
a b c
Fita
  a b c 
q1
2. Faz computações como na máq. de Turing
38
Máquinas de Turing padrão simulam
máquinas off-line:
Use uma máquina padrão com quatro trilhas
para manter informação sobre
arquivo de entrada e o conteúdo da fita
da máquina off-line
39
Máquina off-line
Arquivo de entrada
a b c d
Fita
  e f g 
Fita de 4 trilhas – Máquina padrão
# a b c d
# 0 0 1 0
e f g
0 1 0
Arquivo de entrada
Posição da cabeça
Fita
Posição da cabeça
40
Ponto de referência
# a b
# 0 0
e f
0 1
c d
1 0
g
0
Arquivo de entrada
Posição da cabeça
Fita
Posição da cabeça
Repita para cada transição de estado:
• Retorne ao ponto de referência
• Encontre o símbolo corrente no arquivo
• Encontre o símbolo corrente na fita
• Faça a transição
41
Teorema:
Máquinas off-line
têm o mesmo poder computacional que
máquinas padrão
42
Máquinas de Turing com múltiplas fitas
unidade
de controle
Fita 1
 a b c 
Fita 2
g
f
e


Entrada
43
Fita 1
Instante 1
Fita 2
 a b c 
g
f
e


q1
q1
Instante 2
 a g c 
g
e
d


q2
q2
q1
(b, f )  ( g , d ), L, R
q2
44
Máquinas com múltiplas fitas simulam
máquinas padrão:
Use apenas uma fita
45
Máquinas padrão simulam
máquinas com múltiplas fitas:
Máquina padrão:
• Use uma fita com múltiplas trilhas
• Uma fita da máquina de múltiplas fitas
corresponde a um par de trilhas
46
Máquina de múltiplas fitas
Fita 1
Fita 2
 a b c 
g
f
e
h 

Máquina padrão com fita de 4 trilhas
a
0
e
0
b
1
f
0
c
0
g h
1 0
Fita 1
Posição da cabeça
Fita 2
Posição da cabeça
47
Ponto de referência
#
#
#
#
a
0
e
0
b
1
f
0
c
0
g h
1 0
Fita 1
Posição da cabeça
Fita 2
Posição da cabeça
Repita para cada transição de estado:
•Retorne ao ponto de referência
•Encontre o símbolo corrente na fita 1
•Encontre o símbolo corrente na fita 2
48
•Faça a transição
Teorema:
Máquinas com múltiplas fitas
têm o mesmo poder de computação que
Máquinas de Turing padrão
49
Mesmo poder não significa mesma velocidade:
Linguagem
L  {a b }
n n
Tempo de aceitação
Máquina padrão
n
Máquina com 2 fitas
n
2
50
L  {a b }
n n
Máquina padrão:
2
vai para frente e volta n vezes
Máquina de duas fitas:
n
Copia b
na fita 2
Deixa
a
n
na fita 1
Compara a fita 1 e a fita 2
( n passos)
( n passos)
( n passos)
51
Máquina de Turing MultiDimensional
Fita de 2 dimensões
y

 c a

b

MOVE: L,R,U,D
U: cima
D: baixo
CABEÇA
Posição: +2, -1
x
52
Máquinas multidimensionais simulam
máquinas padrão:
Use uma dimensão
53
Máquinas padrão simulam
máquinas multidimensionais:
Máquina padrão:
• Use uma fita com 2 trilhas
• Armazene os símbolos na fita 1
• Armazene as coordenadas na fita 2
54
Máquina bi-dimensional
y

 c a

b

Máquina padrão
c
a
b
1 # 1 # 2 #  1 #  1
q1
x
q1
símbolos
coordenadas
55
Máquina padrão:
Repita para cada transição
• Atualize o símbolo corrente
• Compute as coordenadas da próxima posição
• Vá para a próxima posição
56
Teorema:
Máquinas multidimensionais
têm o mesmo poder de computação
que máquinas padrão
57
Máquinas de Turing Não Deterministas
a  b, L
q2
q1
a  c, R
q3
Escolha Não Determinista
58
a  b, L
q2
q1
Instante 0
 a b c 
a  c, R
Opção 1
 b b c 
q2
q1
q3
Instante 1
Opção 2
 c b c 
q3
59
string de entrada w é aceito se
esta é uma computação possível

q0 w  x q f y
configuração inicial
configuração final
estado final
60
Máquinas Não Deterministas simulam
Máquinas padrão (deterministas) :
Toda máquina determinista
é também uma máquina não determinista
61
Máquinas deterministas simulam
máquinas não deterministas:
Máquina Determinista:
Mantém informação sobre todas
as possíveis computações
62
Escolhas Não Deterministas
q1
q3
q2
q4
q5
Computação 1
q6
q7
63
Escolhas Não Deterministas
q1
q3
q2
q4
q5
q6
Computação 2
q7
64
Simulação
Máquina Determinista:
• Mantém informação sobre
todas as possíveis computações
• Armazena essas computações em uma
fita bidimensional
65
Máquina Não Determinista
a  b, L
Instante 0
q2
 a b c 
q1
q1
a  c, R
q3
Máquina Determinista
#
#
#
#
# # #
a b c
q1
# # #
# #
#
#
#
Computação 1
66
Máquina Não Determinista
Instante 1
a  b, L
q2
q1
a  c, R
 b b c 
q2
 c b c 
q3
Opção 1
Opção 2
q3
Máquina Determinista
# # # #
#
b b c
# q2
#
c b c
q3
#
# #
#
#
#
#
Computação 1
Computação 2
67
Repita
• Execute um passo em cada computação:
• Se existem duas ou mais opções
na computação corrente:
1. Copie a configuração
2. Modifique o estado na cópia
68
Teorema: Máquinas não deterministas
têm o mesmo poder de computação
máquinas deterministas
69
Observação:
A simulação na máquina determinista
leva no máximo tempo exponencial
em comparação com o tempo gasto
pela máquina não determinista
70