O Computador Universal
Bibliografia Base
• Artigo “Turing Machine” por James Moor em
Encyclopedia of Computer Science (4a Edição).
Bib. FCT/UNL: QA 76.15 ENC
• Páginas 147-166 do capítulo 7 do livro de Martin
Davis "The universal computer". W.W.Norton
2000. Bib. FCT/UNL: QA 76.17 DAV.
Referências
• Outras:
– Visual Turing:
http://www.cheran-software.com/vturing/
– Pagina Alan Turing:
http://www.turing.org.uk/turing/
A Noção de Computação
• Em 1930 um computador era uma pessoa cujo
trabalho era efectuar computações:
– Efectuava marcas em folhas de papel.
– Mudava constantemente a atenção de folha para folha.
• O matemático Inglês Alan Turing tentou modelar
o essencial deste processo de computação por um
modelo matemático!
• Criou o modelo que descreve o funcionamento
básico de QUALQUER computador!
Um Exemplo
• Queremos converter a sequência de números:
1010010002101021010
• Em:
0101101112101020101
• i.e. ou 1 passa a 0, ou vice-versa, ou mantêm-se
Como o fazer?
• Máquina de Turing:
– Uma unidade de controlo, que pode estar em um de
vários (número finito) estados possíveis.
– Uma fita, organizada em quadrados discretos, cada
quadrado pode armazenar um único símbolo de um
conjunto de símbolos.
– Uma cabeça de escrita/leitura, que se move na fita e que
transmite informação de e para a fita de controlo.
• Artigos: Turing Machine
No exemplo, temos 2 estados...
ou 0 passa a 1 e 1 passa a 0:
1010010002101021010
0101101112101020101
0:1 ->
1:0 ->
ou os 0 e 1 mantêm-se:
1010010002101021010
0101101112101020101
0:1 ->
1:0 ->
0:0 ->
1:1 ->
E o 2 altera este comportamento...
1010010002101021010
0101101112101020101
0:1 ->
1:0 ->
2:2 ->
2:2 ->
0:0 ->
1:1 ->
Funcionamento
• Para um dado estado R,
– Se a máquina lê um símbolo a.
– Então:
• Escreve o símbolo b (Blank).
• Opcionalmente move a cabeça uma posição (para a
direita ou para a esquerda).
• Muda para o estado S.
Vantagens
• São modelos matemáticos:
– Não têm qualquer limitação física
(comprimento de fita tão grande quanto o
necessário).
• São simples:
– Mas qualquer computador pode ser descrito por
uma máquina de Turing!
– Qualquer computador pode simular uma
máquina de Turing, desde que tenha memória
suficiente.
Podemos Formalizar a Máquina de
Turing utilizando tabelas de quíntuplos:
• Mudar do estado R para S, lendo a e escrevendo b,
com movimento para a direita:
R a : b -> S
Quintupulos: Formalização
• Mudar do estado R para S, lendo a e
escrevendo b, com movimento para a
direita:
a/b denotam qualquer
símbolo válido. Não
está a/a pois podem não
ser o mesmo símbolo!
R a : b -> S
Quintupulos: Formalização
• Mudar do estado R para S, lendo a e
escrevendo b, com movimento para a
esquerda:
R a : b <- S
Quintupulos: Formalização
• Mudar do estado R para S, lendo a e
escrevendo b, sem movimento.
Ra:b*S
Church/Turing Thesis
• Alan Turing demonstrou que:
– A Máquina de Turing captura a noção de
COMPUTAÇÃO.
– Exs: Máquinas para efectuar a representação
binária de e e ...
• Criou uma máquina de Turing Universal:
Número de Código duma máquina M
Input de M
A Máquina de Turing Universal
• Um número COD codifica uma máquina de
Turing específica.
• Uma máquina de Turing Universal recebe
esse número e o input DAT.
• Com base no número COD, a máquina de
Turing Universal aplica as computações
descritas em COD a DAT.
Número de Código duma máquina M
Input de M
A Máquina de Turing Universal para
compreender os Computadores
• Na máquina de Turing Universal:
– COD é o programa
– DAT são os dados tratados
– A máquina de Turing é o Hardware
• Lições para entender um computador:
– Um computador está SEMPRE num dado estado!
– Nesse estado altera SEMPRE da mesma forma os dados
que recebe!
– APENAS quando muda de estado altera os dados de outra
forma (a do novo estado)!
– O computador ESCOLHE quais os dados a processar a
seguir com base nos dados actuais e estado em que está o
seu processamento!
Máquina Par ou Impar (Davis pp. 152-154)
Q
0
:
=>
E
Q
2
:
=>
E
Q
0
:
=>
E
Q
4
:
=>
E
Q
1
:
=>
O
Q
3
:
=>
O
Q
1
:
=>
O
Q
5
:
=>
O
E
0
:
=>
E
E
2
:
=>
E
E
0
:
=>
E
E
4
:
=>
E
E
1
:
=>
O
E
3
:
=>
O
E
1
:
=>
O
E
5
:
=>
O
O
0
:
=>
E
O
2
:
=>
E
O
0
:
=>
E
O
4
:
=>
E
O
1
:
=>
O
O
3
:
=>
O
O
1
:
=>
O
O
5
:
=>
O
*
F
E
*
F
E
*
F
E
:
0
:
1
Q
6
:
=>
E
Q
8
:
=>
E
Q
7
:
=>
O
Q
9
:
=>
O
E
6
:
=>
E
E
8
:
=>
E
E
7
:
=>
O
E
9
:
=>
O
O
6
:
=>
E
O
8
:
=>
E
O
7
:
=>
O
O
9
:
=>
O
:
0
Exercícios (1/2)
• Para a máquina de Turing Par/Impar (Davis,
pp. 152-154), qual o próximo estado de?
a)
Q
\|/
__ __ __ 1 2
b)
3 4 5 __ __
Q
\|/
__ __ __ __ __ __ __ __ 5 __ __
Exercícios (2/2)
• Considere a seguinte máquina de Turing:
Q 0 : 1 -> Q
Q_:_*F
Q 1 : 0 -> Q
a) Qual o resultado de aplicar esta máquina à
fita:
__ __ __ 1 0
0 1 1 __ __