HotelMobile

Trabalho Completo Máquina Norma
Máquina Norma

Imprimir Trabalho!
Cadastre-se - Buscar 155 000+ Trabalhos e Monografias

Categoria: Tecnologia
Enviado por: gustavoslima 29 setembro 2013
Palavras: 1692 | Páginas: 7
Máquina Norma

Number TheOretic Register MAchine

Débora Pandolfi Alves

Ricardo Nabinger Sanchez

2

Máquina Norma

Number TheOretic Register MAchine

● Máquina de registradores proposta por

Richard Bird

● Possui um conjunto infinito de registradores

naturais como memória e três intruções:

● A:=A+1 (adiciona um)

● A:=A-1 (subtrai um)

● A=0 (testa se é zero)

3

Máquina Norma

● Os registradores podem conter um

elemento qualquer de ℕ, isto é V=ℕ∞

● Os registradores são denotados por

A,B,...,X,Y

● A operação A:=A-1 quando A é 0 não

altera seu valor

● Os registradores X e Y são especiais

4

Máquina Norma Definição

A máquina 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, ...

5

Máquina Norma Definição

– A função de entrada ent: ℕℕ∞ carrega

no registrador X o valor de entrada e 0

nos demais

– A função de saída sai: ℕ∞ℕ retorna o

valor atual do registrador Y

6

Máquina Norma Definição

– 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: ℕ∞ ®