Maquina norma

MÁQUINA DE NORMA Number TheOretic Register MAchine
André Rodrigues

Legenda
 Máquina Norma
 Conceito de Máquina

 Definições da Máquina Norma
 Exemplo de Operação e Teste  Conclusão

Conceito de Máquina
 É um algoritmo que tem descrição finita e não ambígua e consiste em passos discretos, executáveis mecanicamente em um tempo finito.

Máquina Norma
 A Máquina Universal Norma ( Number TheOretic Register Machine).  Foi denominada e proposta a Máquina Norma por Richard Bird 1976.  É uma máquina extremamente simples, de tal forma que parece difícil acreditar que o seu poder computacional é, no mínimo, o de qualquer computador moderno.

Máquina Norma
 Possui como memória um conjunto infinito de

registradores naturais e três instruções sobre cada registrador:
 Exemplo:

A:=A+1 (adiciona um) A:=A-1 (subtrai um) A=0 (testa se e zero)

Máquina Norma
 Os registradores podem qualquer de ℕ, isto é V=ℕ∞

conter um elemento

 Os registradores são denotados por A,B,...,X,Y

 A operação A:=A-1 quando A é 0 e não altera seu valor.  Os registradores X e Y são especiais

Máquina Norma
 A maquina Norma é uma 7-upla

(suponha que kє {A,B,X,Y...}):  Norma = (ℕ∞, ℕ, ℕ, ent, sai, {adk,subk},{zerok}).
 Onde:  Cada elemento do conjunto de valores de memória ℕ∞ denota uma configuração de seus infinitos registradores que são denotados por A, B,…,X, Y

Máquina Norma
 A função de entrada ent: ℕ → ℕ∞ carrega no registrador denotado por X o valor de entrada, inicializando todos os demais registradores com zero.  A função de saída sai: ℕ∞ → ℕ retorna o valor atual do registrador Y.

Máquina Norma
 O conjunto de interpretações de operações

é indexada pelos registradores, onde para cada registrador k: adk: ℕ∞ → ℕ∞ e subk: ℕ∞ → ℕ∞
 O conjunto de interpretações de testes é indexada pelos registradores, onde para cada registrador k:

zerok: ℕ∞ → { verdadeiro, falso}

Máquina Norma
 EXEMPLO: Atribuição de um Valor