UNIPÊ – Centro Universitário de João Pessoa
Curso de Ciências da Computação
Teoria da Computação
MÁQUINA NORMA
Fabrício Dias
[email protected]
Agenda

Máquina Norma


Definições
Máquina Norma como Máquina Universal
Máquina Norma

A Máquina Universal Norma (Number
TheOretic Register MAchine)

proposta por Richard Bird em 1976
3
Máquina Norma

A Máquina Universal Norma (Number
TheOretic Register MAchine)


possui como memória um conjunto
potencialmente infinito de registradores
naturais;
três instruções podem atuar sobre cada
registrador:
 adição do valor um;
 subtração do valor um;
 teste (se o valor armazenado é zero).
4
Máquina Norma


N∞ denota o conjunto de todas as tuplas
com infinitos (mas contáveis) componentes
sobre o conjunto dos números naturais.
Para evitar subscritos, as componentes das
uplas são denotadas por letras maiúsculas
como A, B, X, Y as quais denotam os
registradores na Máquina Norma.
5
Máquina Norma

Definição: A Máquina Norma é uma 7upla (suponha que K seja um registrador,
K  { A, B, …, X, Y }):
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })
a)
Cada elemento do conjunto de valores de
memória N∞ denota uma configuração de
seus infinitos registradores, os quais são
denotados por: A, B, …, X, Y
6
Máquina Norma

Definição:
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })
b)
A função de entrada:
ent: N → N∞ é tal que carrega no
registrador denotado por X o valor de
entrada, inicializando todos os demais
registradores com zero;
7
Máquina Norma

Definição:
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })
c)
A função de saída:
sai: N∞ → N é tal que retorna o valor
corrente do registrador denotado por Y.
8
Máquina Norma

Definição:
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })
d)
O conjunto de interpretações de
operações é uma família de operações
indexada pelos registradores, na qual,
para cada registrador K { A, B, …, X, Y },
tem-se que:

adK: N∞ → N∞
Adiciona um à componente correspondente
ao registrador K, deixando as demais com
seus valores inalterados.
(K:=K+1)
9
Máquina Norma

Definição:
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })

subK: N∞ → N∞
Subtrai um da componente correspondente
ao registrador K, se o seu valor for maior que
zero (caso contrário, mantém o valor zero),
deixando as demais com seus valores
inalterados.
(K:=K-1)
10
Máquina Norma

Definição:
Norma = (N∞, X, Y, ent, sai, { adK,subK }, { zeroK })
e)
O conjunto de interpretações de testes é
uma família de testes indexada pelos
registradores na qual, para cada
registrador K, tem-se que:

zeroK: N∞ → { verdadeiro, falso } resulta em
verdadeiro, se a componente correspondente
ao registrador K for zero e em falso, caso
contrário.
(K=0)
11
Máquina Norma como
Máquina Universal
12
Máquina Norma

Características:

Operações e Testes. Definição de operações
e testes mais complexos como adição,
subtração, multiplicação e divisão de dois
valores e tratamento de valores diversos
como os números primos;
13
Máquina Norma

Características:

Valores Numéricos. Armazenamento de
tratamento de valores numéricos de diversos
tipos como inteiros (negativos e nãonegativos) e racionais;
14
Máquina Norma

Características:

Dados Estruturados. Armazenamento de
tratamento de dados estruturados como em
arranjos (vetores uni e multidimensionais),
pilhas, filas, etc.
15
Máquina Norma

Características:

Endereçamento Indireto e Recursão. Desvio
para uma instrução determinada pelo
conteúdo de um registrador;
16
Máquina Norma

Características:

Cadeia de Caracteres. Definição e
manipulação de cadeias de caracteres.


Tipo não-predefinido numa Máquina Norma;
Tratamento da definição e da manipulação de
cadeias de caracteres será realizado através de
outra Máquina Universal

Máquina de Turing
17
Concluindo

Máquina Norma é uma máquina que:

Possui uma memória potencialmente infinita,
compostas por 3 instruções;

É uma 7- upla do tipo: Norma = (N∞, X, Y,
ent, sai, { adK,subK }, { zeroK });
Possui operações e testes complexos, como
adição, subtração, multiplicação e divisão de
dois valores e tratamento de valores diversos
como os números primos.





Valores numéricos, negativos e não-negativos;
Dados estruturados (pilha, fila..);
Endereçamento indireto e recursão (desvio para
uma instrução);
Cadeia de caracteres (pré-definidas).

Dúvidas?????