Computando Funções
com
Máquinas de Turing
1
Uma função
f (w)
Contra-domínio:
Domínio: D
f (w)
w D
tem:
S
f ( w)  S
2
Uma função pode ter vários parâmetros:
Exemplo:
Função de adição
f ( x, y )  x  y
3
Domínio Inteiro
diferentes possíveis representações
Decimal:
5
Binário:
101
Unário:
11111
Vamos preferir a representação unária:
mais fácil de ser manipulada por MTs
4
Definição:
Uma função f é computável se
existe uma Máquina de Turing M tal que:
configuração inicial

w

q0
estado inicial
Para todo
configuração final

f (w) 
qf
estado de aceitação
w D Domínio
5
Em outras palavras other words:
Uma função f é computável se
existe uma máquina de Turing M tal que:

q0 w  q f f ( w)
configuração
inicial
Para todo
configuração
final
w D Domínio
6
Exemplo
A função
f ( x, y )  x  y é computável
x, y
são inteiros
Máquina de Turing:
string de entrada:
x0 y
unário
string de saída:
xy 0
unário
7
x
Início
 1 1

y
1 0 1  1 
q0
estado inicial
O 0 é o delimitador que
separa os dois números
8
y
x
Início
 1 1

1 0 1  1 
q0 estado inicial
x y
Fim
 1 1

1 1 0 
q f estado final
9
símbolo 0 aqui ajuda, quando usamos
o resultado para outras operações
x y
Fim
 1 1

1 1 0 
q f estado final
10
Máquina de Turing para
1 1, R
f ( x, y )  x  y
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
11
Exemplo de execução:
x  11 (=2)
y  11 (=2)
Instante 0
y
x
 1 1 0 1 1 
q0
Resultado Final
x y
 1 1 1 1 0 
q4
12
Instante 0
 1 1 0 1 1 
q0
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
13
Instante 1
 1 1 0 1 1 
q0
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
14
Instante 2
 1 1 0 1 1 
q0
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
15
Instante 3
 1 1 1 1 1 
q1
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
16
Instante 4
 1 1 1 1 1 
q1
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
17
Instante 5
 1 1 1 1 1 
q1
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
18
Instante 6
 1 1 1 1 1 
q2
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
19
Instante 7
 1 1 1 1 0 
q3
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
20
Instante 8
 1 1 1 1 0 
q3
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
21
Instante 9
 1 1 1 1 0 
q3
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
22
Instante 10  1 1 1 1 0 
q3
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
23
Instante 11  1 1 1 1 0 
q3
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
  , R
q4
24
Instante 12  1 1 1 1 0 
q4
1 1, R
1 1, R
1 1, L



,
L
0

1
,
R
1
0
,
L
q
q0
q3
q1
2
pára & aceita
  , R
q4
25
Outro Exemplo
A função
f ( x)  2 x
x
é computável
inteiro
Máquina de Turing :
string de entrada:
string de saída:
xx
x
unário
unário
26
x
Início
 1 1

1 
q0 estado inicial
2x
Fim
 1 1

1 1 1 
q f estado de aceitação
27
Pseudocódigo da Máquina de Turing para
f ( x)  2 x
• Substitua cada 1 por $
• Repita:
• Encontre o $ mais à dir. e substitua por 1
• Vá para a extremidade direita e escreva 1
Até que não reste nenhum $
28
f ( x)  2 x
Máquina de Turing para
1  $, R
1 1, L
1 1, R
q0   , L q1 $  1, R
  , R
q3
q2
  1, L
29
Início
Exemplo
 1 1 
Fim
 1 1 1 1 
q0
q3
1  $, R
1 1, L
1 1, R
q0   , L q1 $  1, R
  , R
q3
q2
  1, L
30
Outro Exemplo
f ( x, y ) 
A função
é computável
Entrada:
Saída:
1
se
x y
0
se
x y
x0 y
1
ou
0
31
Pseudocódigo da Máquina de Turing :
• Repita
Case um 1 de
Até que todo o
x com um 1 de y
x ou todo o y seja marcado
• Se um 1 de x não está marcado
limpe a fita e escreva 1 ( x 
senão
limpe a fita e escreva 0 ( x 
y)
y)
32
Combinando
Máquinas deTuring
33
Diagrama de bloco
entrada
Máquina
de Turing
saída
34
Exemplo:
x  y se x  y
f ( x, y) 
0
x, y
x, y
Comparador
se x  y
Somador
x y
x y
x  y Limpador
0
35