CompNum-v0.9

Prévia do material em texto

Teoria da Computação 
Computação Númerica 
Versão dos slides: 0.9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing 
2 
Linguagens 
Máquinas de 
Turing 
reconhece 
“Modelo computacional 
universalmente aceito como 
possuindo poder de expressão 
equivalente aos computadores 
modernos” 
“Máquinas de Turing capturam 
e representam precisamente a 
noção abstrata a respeito do 
que é um algoritmo e quais são 
seus limites” 
? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing 
 Até o momento, existem três possíveis 
resultados para computação: configuração de 
aceitação, configuração de rejeição, ou loop 
 O resultado de uma MT pode também ser 
definido em termos dos símbolos escritos na 
fita quando a computação termina 
• Agora podemos ter um número infinito de 
possíveis resultados! 
 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções 
 A função 𝑓: 𝑋 → 𝑌 pode ser interpretada 
como um mapeamento que atribui um (e 
apenas um) elemento do contra-domínio 𝑌 a 
um elemento do domínio 𝑋 
 Atribuição para todos elementos de 𝑋: função 
total; caso contrário, função parcial 
 𝑓 𝑢 ↑: não existe valor em 𝑌 atribuído a 𝑢 
 
 
4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação de Funções 
 Projeto de MTs para computar o valor de 
funções 
• Elemento do contra-domínio 𝑌 atribuído pela 
função a um elemento do domínio 𝑋; os 
elementos de 𝑋 representam a “entrada” da 
função 
 Elementos de 𝑋 e 𝑌 são representados por 
palavras sobre o alfabeto de entrada 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Simplificações e Convenções 
6 
qu qa 
˽→R,L 
1→x, R 
qa 
1→x, R 
Configuração de aceitação: 
MT encontra-se no estado 
de aceitação e lê um 
símbolo branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Simplificações e Convenções (2) 
7 
q0 
˽→˽,R 
qu 
 A computação inicia-se com um símbolo 
branco. A função do estado inicial é posicionar 
a cabeça e/l no ínicio da palavra de entrada 
 
˽ a b c ... 
q0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 Não existe uma configuração que retorne a 
MT ao estado inicial 
8 
Simplificações e Convenções (3) 
q0 
˽→˽ , R 
X 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Simplificações e Convenções (4) 
 A configuração de aceitação é caracterizada 
pela configuração qa ˽ v ˽, onde v representa 
o resultado obtido 
 
9 
˽ a b c ˽ 
qa 
Resultado 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Visão de Alto Nível 
10 
q0 MT qa 
˽→R ˽→ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação de Funções: 
Definição Formal 
 Uma MT determinística M = (Q, ∑, Γ, , q0, 
qa) computa a função unária 𝑓: 
∗
→ 
∗
 se 
i. Existe apenas uma transição do estado q0 e ela 
tem a forma (q0, ˽) (qi, ˽, R) 
ii. Não existem transições do tipo (qi, x) (q0, y, 
d) para qualquer 𝑞𝑖 ∈ 𝑄, 𝑥, 𝑦 ∈ Σ, 𝑑 ∈ *𝐿, 𝑅+ 
iii. Não existem transições do tipo (qa, ˽) 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação de Funções: 
Definição Formal 
iv. A computação com entrada u para na 
configuração qa ˽ v ˽ sempre que f(u)= v 
v. A computação continua de maneira indefinida 
sempre que 𝑓 𝑢 ↑ 
 No restante, iremos nos referir a esta nova 
definição como Máquina de Turing 
Númerica (MTN) 
 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação de Funções 
 Uma função é Turing computável se existe uma 
MTN que a computa 
 Uma MTN que computa uma função tem dois 
estados: q0 e o estado de parada qa 
 A computação começa com uma transição a 
partir de q0 que posiciona a cabeça le no ínicio da 
palavra de entrada 
 Todas computações terminam no estado qa 
 Após o término, o valor da função é escrito na fita 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação de Funções Parciais 
 Uma MTN N que computa uma função 𝑓 pode 
não terminar para uma determinada entra 𝑢 
 Neste caso, dizemos que 𝑓 é indefinida para 𝑢 
• A função 𝑓 é parcial 
 Note que não é necessário que exista um 
Decididor para que uma função seja dita 
computável 
 MTNs podem computar tanto funções totais 
como funções parciais 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Projete uma MTN para computar função 
𝑓: *𝑎, 𝑏+∗→ *𝑎, 𝑏+∗ definida da seguinte forma: 
𝑓 𝑢 = 
𝜀 𝑠𝑒 𝑐𝑜𝑛𝑡é𝑚 𝑝𝑒𝑙𝑜 𝑚𝑒𝑛𝑜𝑠 𝑢𝑚 𝑎
↑ 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜 
 
 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (2) 
16 
q0 q1 qa q2 
˽→R ˽→L a→R 
b→R 
˽→R 
a→R 
b→R 
a→˽,L 
b→˽,L 
/*loop se não 
contém a*/ 
/*“rebobina“ a fita, não 
precisa escrever nada 
para esta função*/ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computando Funções n-árias 
17 
˽ a b c 
q0 
˽ a c c ˽ b b b ˽ 
𝑓 𝑥, 𝑦, 𝑧 , 𝑥, 𝑦, 𝑧 ∈ 𝑎, 𝑏, 𝑐
∗ 
Saída: qa ˽ f(abc,acc,bbb) ˽ 
𝑓 𝑎𝑎, 𝜀, 𝑏𝑐 
˽ a a ˽ 
q0 
˽ b c ˽ 
... 
... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação Numérica 
 Uma função numérica é uma função da forma 
𝑓: 𝑁 × 𝑁 × ⋯× 𝑁 → 𝑁 
• Domínio consiste em números naturais ou n-tuplas 
de números naturais 
 Exemplos: 
• 𝑠𝑞:𝑁 → 𝑁, função unária definida por 𝑠𝑞 𝑛 = 𝑛2 
• 𝑎𝑑𝑑:𝑁 × 𝑁 → 𝑁, função binária definida por 
𝑎𝑑𝑑 𝑥, 𝑦 = 𝑥 + 𝑦 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Simbólico → Numérico 
 Números são representados por strings de 
simbolos: 234, 23435, 2.343, 3x10-2, etc 
 Portanto, precisamos apenas definir o alfabeto 
de entrada da MTN para uma determinada 
representação de números naturais 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Notação Unária 
 Aqui, usaremos a chamada representação unária, 
onde números naturais são representados por 
sequências de 1s 
• 0 → 1 
• 1 → 11 
• 2 → 111 
• ... 
 A representação unária de um número 𝑛 é 
denotada por 𝑛 
 ∑ = {1}+ 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Notação Unária: Exemplo 
21 
˽ 1 1 1 
q0 
˽ 1 ˽ 1 1 1 1 ˽ 
sum 𝑥, 𝑦, 𝑧 = x + y + z 
sum(2,0,3) 
... 
˽ 1 1 1 
q0 
1 1 1 ˽ ... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções e Relações 
 Podemos usar uma função característica para 
definir relações 
 𝑟: 𝑁 × 𝑁 × ⋯× 𝑁 → *0,1+ define uma k-ária 
relação R sobre o domínio da função. A 
relação é definida por: 
𝑛1, 𝑛2, … , 𝑛𝑘 ∈ 𝑅 𝑠𝑒 𝑟 𝑛1, 𝑛2, … , 𝑛𝑘 = 1 
𝑛1, 𝑛2, … , 𝑛𝑘 ∉ 𝑅 𝑠𝑒 𝑟 𝑛1, 𝑛2, … , 𝑛𝑘 = 0 
22 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções e Relações (2) 
 Podemos dizer uma função característica é 
um predicado (função cujo codomínio é 
{TRUE, FALSE} aplicado sobre relações 
 Uma relação é Turing computável se sua 
função característica é Turing computável 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNs Básicas: Building Blocks 
 Função sucessora: 𝑠 𝑛 = n + 1 
24 
q0 q1 qa 
˽→R ˽→1,L 
1→R 
1→L 
S: 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNs Básicas: Building Blocks 
 A função zero: 𝑧 𝑛 = 0 
25 
q0 q1 q3 q2 
˽→R ˽→R ˽→L 
1→R 1→˽L 
qa 
˽→1L 
Z: 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNs Básicas: Building Blocks 
 A função vazia: 𝜀 𝑛 =↑ 
26 
q1 q2 
˽→R 
˽→R 
1→R 
qa 
E: 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNs Básicas: Building Blocks 
 Função adição: A(x,y):x+y 
 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNs Básicas: Building Blocks 
 Função adição: A(m,n):m+n 
28 
q0 q1 q3 q2 
˽→R ˽→L ˽→1R 
1→R 1→R 
q4 
1→˽L 
qa 
1→˽L 
1→L 
 Representação unária de m e n é 1m+1 e 1n+1, 
respectivamente; m + n é 1m + n +1 
 A MTN A substitui o símbolo branco entre os 
argumentos por 1 e depois “apaga” os dois mais a 
direita 
A: 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções vs. Algoritmos 
 Considere as duas MTNs acima. Z já 
conhecemos. E Z1 ? Qual função Z1 computa? 
29 
q0 q1 q3 q2 
˽→R ˽→R ˽→L 
1→R 1→˽L 
qa 
˽→1L 
Z: 
q0 q1 q3 q2 
˽→R ˽→L 1→R qa 
1→L 
1→˽R Z1: 
˽→L 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções vs. Algoritmos 
 Z e Z1 computam amesma função, a função zero 
30 
Mapeia elementos do 
domínio para elementos do 
codomínio 
Dada uma entrada, 
mecanicamente computa o 
valor da função sempre a 
função é definida para esta 
entrada 
Função 
MTN 
Definição Computação 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação Sequencial de MTNs 
 MTNs projetadas para realizar uma única 
tarefa podem ser combinadas para construir 
máquinas que realizam computações mais 
complexas (Princípio “Lego”) 
 Intuição: Execute um conjunto de MTNs 
sequencialmente, a saída de uma MTN é a 
entrada de outra 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Visão de Alto Nível: 
Interface e Implementação 
32 
q0 MT qa 
˽→˽, R ˽→R,L 
˽ a b c ... 
q0 
˽ a b c ˽ 
qa 
Resultado 
Implementação 
Interface 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Projetar uma MTN C para computar a função 
constante c(n) = 1 
 Vamos representar a execução sequencial de 
duas MTNs por “+” 
 C ⟺ 𝑍 + 𝑆 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (2) 
34 
q0 q1 qa 
˽→R ˽→1,L 
1→R 
1→L 
S: 
q0 q1 q3 q2 
˽→R ˽→R ˽→L 
1→R 1→˽L 
qa 
˽→1L 
Z: 
+ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (3) 
35 
qz,0 qz,1 qz,3 qz,2 
˽→R ˽→R ˽→L 
qza=qs,0 
˽→1L 
1→R 1→˽L 
qs,1 qs,a 
˽→R 
˽→1,L 
1→R 1→L 
C: Z + S 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Visão de Alto Nível 
36 
* 
Z * 
S * 
C Estados iniciais e 
finais podem ser 
inferidos das 
próprias MTNs 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Visão de Alto Nível: Macros 
37 
* M * 
Macro: Máquina que 
computa tarefas simples e 
frequentemente executadas 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macros 
 Requer pequenas adaptações na definição de 
MTNs 
 Pode existir mais de um estado de aceitação 
 A computação pode começar do meio da fita 
 Existem apenas duas transições do estado q0 
 (q0, ˽) (qi, ˽, R) 
 (q0, ˽) (qi, ˽, L) 
 Todas as outras definições permanecem válidas 
 
 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macros (2) 
 Uma família de macros é normalmente 
descritas por um esquema 
 Exemplo: A macro MDi move a cabeça le para 
a direita através de i números naturais 
consecutivos 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macros (3) 
 Temos MD1 
 
40 
q0 qa 
˽→R 
1→R 
 Temos MDk é construída através da adição de 
estados para mover a cabeça le através de uma 
sequência de k números naturais 
 
q0 q1 
˽→R 
1→R 
˽→R … qk-1 qa 
˽→R 
1→R 1→R 
˽→R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macros (4) 
 Assim como nas MTNs, a execução de macros 
requer que a entrada tenha uma forma específica 
(“contrato da interface”) 
• Por exemplo, MDi, requer que existam pelo menos i 
números naturais à direita da cabeça le 
 É de responsabilidade do projetista de uma 
máquina composta por macros assegurar que a 
configuração de entrada apropriada é recebida 
por cada macro 
 A computação de uma macro permanece dentro 
do segmento de fita indicado pelo símbolo 
branco inicial e final; nenhuma porção da fita 
fora destes limites é alterada 
 41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macro MEk – Mover para Esquerda 
 Move a cabeça de leitura para esquerda através 
de uma sequência de k números naturais. Macro 
MDk (mover para direita) é análoga 
42 
˽ 𝑛1 ... ˽ 𝑛2 ˽ ˽ 𝑛𝑘 ˽ 
˽ 𝑛1 ... ˽ 𝑛2 ˽ ˽ 𝑛𝑘 ˽ 
Posição da cabeça le 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Macro ED (encontre à direita) 
 Move a cabeça le para a posição de processar 
o próximo número natural à direita. Macro EE 
(encontre à esquerda) é análoga 
43 
˽ ... ˽ ˽ ˽ 𝑛 ˽ 
Posição da cabeça le 
˽ ... ˽ ˽ ˽ 𝑛 ˽ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Ek (Exclui uma sequência 
de k números naturais) 
 Apaga uma sequência de k números naturais e 
termina com a fita em sua posição original 
44 
˽ 𝑛1 ... ˽ 𝑛2 ˽ ˽ 𝑛𝑘 ˽ 
Posição da cabeça le 
˽ ˽ ... ˽ ˽ ˽ ˽ ˽ ˽ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
CPk (cópia) 
 Copia k números naturais para as posições à 
direita do último número a ser copiado e 
termina com a fita em sua posição original 
 
45 
˽ 𝑛1 ... ˽ ˽ 𝑛𝑘 ˽ 
Posição da cabeça le 
˽ ˽ ... ˽ ˽ ˽ 
˽ 𝑛1 ... ˽ ˽ 𝑛𝑘 ˽ ˽ 𝑛1 ... ˽ ˽ 𝑛𝑘 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
CPk,i (cópia após i números) 
 Copia k números naturais para as posições 
que iniciam-se i posições a partir do último 
número a ser copiado e termina com a fita em 
sua posição original 
 
46 
Posição da cabeça le 
˽ 𝑛1 ... ˽ ˽ 𝑛𝑘 ˽ 𝑛𝑘+1 ... ˽ ˽ 𝑛𝑘+𝑖 ˽ 
˽ 𝑛1 ... ˽ 𝑛𝑘 ˽ 𝑛𝑘+1 ... ˽ ˽ 𝑛𝑘+𝑖 ˽ ˽ ... ˽ ˽ ˽ ˽ ˽ 
˽ 𝑛1 ... ˽ ˽ 𝑛𝑘 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
T (Translado) 
 Muda a localização do primeiro número 
natural para a direita da cabeça le 
47 
˽ ... ˽ ˽ ˽ 𝑛 ˽ 
˽ ... ˽ ˽ ˽ 𝑛 ˽ 
Posição da cabeça le 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
BRN (Branch on zero) 
 Recebe como entrada um único número 
 O valor da entrada é usada para determinar o estado 
de parada 
 Não altera a fita e não muda a posição da cabeça le 
48 
* 
BRN n=0 
n>0 
* 
* 
˽ 𝑛 ˽ 
Executa em qq 
configuração do tipo: 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Composição de Macros 
 O que esta macro faz? 
49 
* CP1,1 * 
 E1 * T * 
MD1 * T * 
ME1 * 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Composição de Macros 
 INV (Inverte): inverte a ordem entre dois 
números 
50 
* CP1,1 * 
 E1 * T * 
MD1 * T * 
ME1 * 
˽ 𝑛1 ˽ 𝑛2 ˽ ... ˽ 
˽ 𝑛2 ˽ 𝑛1 ˽ ... ˽ 
Posição da cabeça le 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Projete uma máquina para computar a função 
de projeção 𝑝 𝑘 𝑖 
• k representa o número de argumentos (números 
naturais) 
• i define o índice do resultado da projeção: o 
número na posição i é mantido, todos outros são 
apagados 
 Cinto de utilidades: T, MD1, ED, Ei, EE 
 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
53 
* Ei-1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
54 
* Ei-1 * 
T 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
55 
* Ei-1 * 
MD1 T * 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
56 
* Ei-1 * 
MD1 * T 
ED * 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
57 
* Ei-1 * * 
MD1 * T 
ED * 
Ek-i 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Intuição: apague os 𝑖 − 1 argumentos iniciais, 
translade o argumento para a primeira posição 
da fita, apague os argumentos 𝑖 + 1 até k 
58 
* Ei-1 * * 
MD1 * T * EE * 
ED * 
Ek-i 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
 Máquina para computar a função 𝑓 𝑛 = 3𝑛 
 Novo item no cinto de utilidades: 
• A: Adiciona os dois números naturais à direita da 
cabeça le 
 
59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
 Máquina para computar a função 𝑓 𝑛 = 3𝑛 
 
60 
* CP1 * 
MD1 * A * * A 
CP1 * * 
ME1 
 Quais é a sequência de estados da fita 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 
 Máquina para computar a função 𝑓 𝑛 = 0 
 Use a macro BRN e D (retorna o predecessor) 
61 
Prof. Dr.-Ing. LeonardoAndrade Ribeiro 
Exemplo 3 
 Máquina para computar a função 𝑓 𝑛 = 0 
 Use a macro BRN e D (retorna o predecessor) 
62 
* 
BRN n=0 
n>0 
* 
D 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Combinando MTNs e Macros 
 As condições do estado inicial, permitem que 
a macro seja executada após a leitura de um 
símbolo branco em qualquer estado 
63 
qi M * 
˽→ 
Computando 
𝑀𝑢𝑙𝑡(𝑚, 𝑛): 𝑚 × 𝑛 
64 
q0 q1 
˽→R 
q2 
1→R 
 E1 
˽→ 
* ME1 * 
 A * ME1 * 
q3 
* 
 MD1 
* 
 CP1,1 q7 q7 
˽→ 1→X,R 
1→R 
q6 
q5 
X→R 
1→L 
1→L 
˽→L 
 T 
 E1 
* 
 T 
q4 
* 
˽→ 
1→˽,L 
X→˽,L 
X→˽,L 
 CP1 
˽→ 
1→X,R 
1→R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Construção de Programas em 
Computadores Modernos 
65 
Programa 
Executável 
compilador 
executa 
Linguagem de 
Progração de 
Alto-Nível 
codifica 
Computador moderno 
Processo simplificado 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Construção de Programas em 
Máquinas de Turing 
66 
Programa 
Executável 
compilador 
executa 
Linguagem de 
Progração de 
Alto-Nível 
codifica 
Máquinas de Turing 
Processo simplificado 
˽ a b c ... 
q0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagem de Montagem 
para MTs 
 Princípio básico: 
• Um computador muda bits de posição em alguma 
localização da memória 
• MTs escreve símbolos na fita 
 Vamos projetar uma linguagem de montagem 
(assembly) para MTs 
• Descrição sequencial das ações e redirecionamentos 
do fluxo do programa 
• Simplificação do gerenciamento de memória 
• Vamos chamar esta linguagem de LMT 
 
 
 
67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico 
 Valores da entrada da MT são atribuídos para as 
variáveis 𝑣1, … , 𝑣𝑘 
 𝑣𝑘+1, … , 𝑣𝑛 são as variáveis locais usadas pelo 
programa: recebem o valor 0 quando a MT é 
inicializada 
68 
˽ 𝑣1 ... ˽ ˽ 𝑣𝑘 ˽ 𝑣𝑘+1 ... ˽ ˽ 𝑣𝑛 ˽ ˽ ˽ ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico (2) 
 Após a incialização, a cabeça de le é posicionada 
no primeiro símbolo branco após as variáveis de 
entrada e locais: posição HOME 
 A cabeça le retorna para posição HOME entre a 
execução de instruções 
 69 
˽ 𝑣1 ... ˽ ˽ 𝑣𝑘 ˽ 𝑣𝑘+1 ... ˽ ˽ 𝑣𝑛 ˽ ˽ ˽ ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico (3) 
 
 
70 
˽ 𝑣1 ... ˽ ˽ 𝑣𝑘 ˽ 𝑣𝑘+1 ... ˽ ˽ 𝑣𝑛 ˽ ˽ ˽ ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
 À direita da posição HOME estão a versão da MT dos 
registradores 
• A primeiro valor (delimitador por símbolos brancos) está no 
registrador 1, o segundo no registro 2 e assim por diante 
 Restrição: Registrador 𝑖 pode ser lido ou escrito apenas se 
os registradores 1,… , 𝑖 − 1 contém valores 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conjunto de Instruções 
71 
Instrução Descrição 
INIT 𝑣𝑖 Inicializa a variável local 𝑣𝑖 para 0 
HOME 𝑡 Move a cabeça le para HOME quando t variáveis estão alocadas 
LOAD 𝑣𝑖 , t Carrega o valor da variável 𝑣𝑖 no registrador 𝑡 
STORE 𝑣𝑖 , t Armaze o valor do registrador 𝑡 na variável 𝑣𝑖 
RETURN 𝑣𝑖 Apaga as variáveis e deixa o valor de 𝑣𝑖 na posição de saída 
CLEAR 𝑡 Apaga o valor no registrador 𝑡 
BRN L, 𝑡 Redireciona para a instrução L se o valor no registrador t é 0 
GOTO L Execute a instrução L 
NOP Nenhuma operação (executada conjuntamente com GOTO) 
INC 𝑡 Incrementa o valor do registrador 𝑡 
DEC 𝑡 Decrementa o valor do registradro t 
ZERO 𝑡 Substitui o valor no registrador 𝑡 por 0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Inicialização da Fita 
 Inicialização é realizada pelas instruções INT e 
HOME 
72 
Instrução Implementação via Macros 
MDi-1 ZR MEi-1 INIT 𝑣𝑖 
 
HOME 𝑡 
 
 MDt 
* A macro ZR escreve 0 na posição imediatamente à 
direita da cabeça le 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Inicialização da Fita: Exemplo 
 Considere a inicialização de um programa com 
uma variável de entrada 𝑖 e duas variáveis 
locais (abaixo, 𝑞 é um estado qualquer) 
73 
Instrução Configuração 
INIT 2 
 
𝒒˽𝑖 ˽ 
𝒒˽𝑖 ˽ 0 ˽ 
𝒒˽𝑖 ˽ 0 ˽0 ˽ INIT 3 
 HOME 3 
 
˽𝑖 ˽ 0 ˽0 𝒒 ˽ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução STORE 
 Move o valor do registrador 𝑡 para uma variável 
especificada 
 Restrição: STORE 𝑣𝑖 , t pode ser usado apenas 
quando 𝑡 é o último registrador com uma variável 
atribuída 
 Espaçamento entre variáveis é mantido 
 Usa a macro INV para mover o valor do 
registrador para a posição correta 
 O valor do registrador 𝑡 é apagado no final da 
operação 
 74 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução STORE𝑣𝑖,1: Implementação 
 N é o número total de variáveis de entrada e locais; os 
expoentes indicam a repetição da sequência de macros 
75 
Instrução Implementação via Macros 
ME1 INV 
STORE 𝑣𝑖, 1 
 
𝑛 − 𝑖 + 1 
MD1 INV 
𝑛 − 𝑖 
MD1 
E1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Execução STORE𝑣2,1: Exemplo 
76 
Instrução Configuração 
ME1 
 
˽𝑣1˽ 𝑣2˽ 𝑣3𝒒˽ 𝑟 ˽ 
INV 
 
˽𝑣1˽ 𝑣2𝒒˽ 𝑣3˽ 𝑟 ˽ 
˽𝑣1˽ 𝑣2𝒒˽ 𝑟 ˽ 𝑣3˽ 
ME1 
 INV 
 
˽𝑣1𝒒˽ 𝑣2˽ 𝑟 ˽ 𝑣3˽ 
˽𝑣1𝒒˽ 𝑟 ˽ 𝑣2˽ 𝑣3˽ 
˽𝑣1˽ 𝑟 𝒒˽ 𝑣2˽ 𝑣3˽ MD1 
 INV 
 
˽𝑣1˽ 𝑟 𝒒˽ 𝑣3˽ 𝑣2˽ 
MD1 
 
˽𝑣1˽ 𝑟 ˽ 𝑣3𝒒˽𝑣2˽ 
˽𝑣1˽ 𝑟 ˽ 𝑣3𝒒˽ ˽ ˽ E1 
 
Instrução STORE 𝑣𝑖,𝑡: Implementação 
77 
Instrução Implementação via Macros 
ME1 INV 
STORE 𝑣𝑖, 𝑡 
 
𝑡 + 𝑛 − 𝑖 − 1 
MD1 INV 
𝑡 + 𝑛 − 𝑖 − 1 
MD1 
E1 
MEt-1 
INV 
MDt-2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução LOAD 
 Copia o valor da variável 𝑣𝑖 no registrador 𝑡 
 Restrição: os registradores 1, … , 𝑡 − 1 devem 
conter valores 
78 
Instrução Implementação via Macros 
ME𝑛 − 𝑖 + 1 
LOAD 𝑣𝑖, 𝑡 
 
CP1, 𝑛 − 𝑖 + 1 + 𝑡 
 
MD𝑛 − 𝑖 + 1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução CLEAR 
 Apaga o valor do registrador especificado 
79 
Instrução Implementação via Macros 
MD𝑡 − 1 
CLEAR 𝑡 
 
E1 
 
MEt − 1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução RETURN 
 Apaga todas as variáveis da fita, exceto a variável 
especificada 
 Restrição: nenhum registrador deve estar 
alocado 
 Juntamente com CLEAR, é usada para 
reconfigurar a fita para retornar o valor de uma 
determinada computação 
 Resultado final é a configuração básica de saída: 
• q ˽ 𝑣𝑖 ˽ 
80 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução RETURN 𝑣𝑖: Implementação 
81 
Instrução Implementação via Macros 
 T 
RETURN 𝑣𝑖 
 
MD1 
ED 
E𝑛 − 𝑖 + 1 
EE 
E𝑖 − 1 
MEn 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instruções Aritméticas 
 As instruções INC, DEC, e ZERO são 
implementadas pelas macros que computam 
as funções sucessora, predecessora, e zero 
 Instruções aritméticas adicionais, de mais 
alto-nível, poderiam também ser definidas 
• Ex.: Função ADD 
82 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instruções BRN e GOTO 
 Realizam o redirecionamento do fluxo de 
execução 
 GOTO L indica que a próxima instrução a ser 
executada é L 
 BRN 𝐿, 𝑡 testa o valor do registrador L e realiza 
uma das seguintes ações: 
• Se o valor for diferente de zero, a instrução 
seguinte à instrução BRN é executada 
• Se o valor for zero, a instrução L é executada 
83 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução BRN: Implementação 
84 
* 
BRN 
n > 0 
n=0 
Máquina para 
instrução 1 
Máquina para 
instrução 2 
E1 * * 
* 
E1 * 
BRN L,1 
“instrução 1” 
... 
L:“instrução 2” 
Código 
Após a execução de BRN, o 
conteúdode t é apagado 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
 Escreva um programa na linguagem LMT que 
use uma variável de entrada, uma variável 
locais, e um registrador para computar a 
função 𝑓 𝑛 = 2𝑛 + 1 
• A variável de entrada é 𝑣1 e a computação usa 𝑣2 
como variável local 
85 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício: Solução 
86 
INIT 𝑣2 
HOME 2 
LOAD 𝑣1, 1 
STORE 𝑣2, 1 
LOAD 𝑣2, 1 
BRN L2, 1 
LOAD 𝑣1, 1 
INC 1 
STORE 𝑣1, 1 
LOAD 𝑣2, 1 
DEC 1 
STORE 𝑣2, 1 
GOTO L1 
L1 
LOAD 𝑣1, 1 
INC 1 
STORE 𝑣1, 1 
RETURN 𝑣1 
L2 
; A variável 𝑣2 é usada como um contador 
que é decrementado cada vez que L1 é 
executado. Complementarmente, a cada 
execução de L1, 𝑣1 é incrementado. L1 é 
executado n vezes. 
; Após sair do loop L1, o 
valor de 𝑣1 é 
incrementado mais uma 
vez antes de ser 
retornado como 
resultado 
𝑓 𝑛 = 2𝑛 + 1