Maquina norma

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2302 palavras )
  • Download(s) : 0
  • Publicado : 3 de novembro de 2012
Ler documento completo
Amostra do texto
Máquina NORMA
O modelo de máquinas de registradores, do qual faz parte a Máquina NORMA,
apresenta diferenças importantes em relação aos outros modelos apresentados neste
trabalho. Esse modelo surgiu mais recentemente em comparação aos demais modelos,
visto ter sido desenvolvido para ser uma representação aproximada dos computadores
modernos. A estrutura de memória de uma máquina deregistradores é
composta por um número infinito de registradores que, diferentemente dos demais
modelos, podem ser modificados independentemente. Esse modelo segue o padrão
da memória de acesso direto dos computadores eletrônicos modernos [2; 15].
Ainda, nas máquinas de registradores a noção de programa e máquina apresentase
de forma dissociada. Mais precisamente, a função programa definida para realizar
umacomputação forma um conjunto de instruções rotuladas, que operam sobre a
estrutura de registradores. A estrutura de controle executa instruções nos registradores
que podem armazenar um número inteiro arbitrariamente grande. Além
dos registradores, o modelo é composto por quatro operações básicas: incremento,
decremento, salto condicional e parada. Essas operações podem ser utilizadas de
29
modo acompor as demais operações necessárias para computações mais complexas.
A máquina de registradores abordada neste trabalho é a NORMA, cujo nome
significa Number theOretic Register MAchine.

-------------------------------------------------

Definição Formal
A definição de uma Máquina NORMA, conforme já mencionado, diferencia-se das
outras máquinas universais aqui apresentadas, uma vez que a noçãode programa
e máquina são isoladas. Formalmente, uma Máquina NORMA pode ser definida
conforme a Definição 2.5, a partir da qual define-se um programa para uma Máquina
NORMA na Definição 2.6.
Definição 1 (Máquina Norma) Uma Máquina Norma é uma tupla MN =
({Rk}∞k=0, {{ek}, {sk}, {zk}, {{adk}, {subk}}∞k=0), onde:
1. {Rk}∞k=0 ∈ N∞ é um conjunto infinitamente contável de registradores indexados
pork.
2. {{ek}, {sk}, {zk}, {{adk}, {subk}}∞k=0 é o conjunto de famílias de funções indexadas
de uma máquina de Norma onde:
(a) ek : N∪{"} → N∞k=0 representa uma família de funções de entrada tal que,
o resultado da aplicação da função ek(X), no conjunto de registradores
{Ri}∞ i=0, é o armazenamento do valor X no registrador Rk e zero nos
demais registradores. Ou seja, após a aplicação de ek(X), Rk = Xe
Ri = 0 para todo i 6= k, se X ∈ N. Se X = " então ek não modifica o
conteúdo dos registradores e o programa termina.
(b) sk : N → N∞k=0 é a família de funções de saída tal que, o resultado da aplicação
da função sY , no conjunto de registradores {Ri}∞ i=1, é a recuperação
do valor contido no registrador RY .
(c) {zk} : N∞ → {v, f} é a família de funções de testes onde o resultado da
aplicaçãode zk, no conjunto de registradores {Ri}∞ i=1, é um valor verdade.
Ou seja, se {Rk} = 0, o resultado será v, verdadeiro, caso contrário será
f, falso.
(d) {adk} : N∞ → N∞ é a família de funções de testes onde o resultado da
aplicação de adk no conjunto de registradores {Ri}∞ i=1 é incrementar o
valor do registrador Rk. Dessa forma, se Rk = 4 e adk então Rk = 5.
(e) {subk} : N∞ → N∞ é a família defunções de testes onde o resultado da
aplicação de {subk} no conjunto de registradores {Ri}∞ i=1 é decrementar
o valor do registrador Rk. Assim, se Rk = 4 e subk então Rk = 3.

Definição 2

Dada uma Máquina
NORMA MN = ({Rk}∞k=0, {{ek}, {sk}, {zk}, {{adk}, {subk}}∞k=0), um programa para
a máquina MN é uma tupla P = (X, Y, I,C, i0), onde
1. X ∈ {Rk}∞k=0 é o registrador onde será armazenada aentrada.
2. Y ∈ {Rk}∞k=0 é o registrador onde será armazenada a saída.
3. I é um conjunto finito de rótulos que identificam as instruções do programa.
30
4. C ⊆ I × (Q × (I ∪ (I × I)) ∪ {"}) é o conjunto de instruções que formam
o programa, tal que o primeiro elemento da tupla é o rótulo da instrução,
o segundo elemento é uma função pertencente ao conjunto Q ⊆
{{ek}, {sk}, {zk}, {{adk}, {subk}}∞k=0 e o...
tracking img