Mostrar código-fonte de Máquina de registradores

{{sem notas|data=fevereiro de 2015}}
Na [[lógica matemática]] e na [[ciência da computação teórica]] uma ''máquina de registradores ''é uma classe genérica de [[Máquina abstrata|máquinas abstratas]] usadas de uma maneira similar a  [[máquina de Turing]]. Todos os modelos são [[Turing completude|Turing equivalentes]].

==Visão geral==
A máquina registradores tem seu nome pelo uso de um ou mais [[registrador|”registradores”]]. Em contraste com a fita e a cabeça da máquina de Turing, o modelo usa “múltiplos, registradores unicamente endereçados”, cada um que controlam um único [[número inteiro]] positivo.

Há ao menos 4 subclasses encontradas na literatura, aqui listamos da mais primitiva a mais parecida com um [[computador]]:
*Máquina de contador – o mais primitivo e reduzido modelo teórico de um ''[[hardware]]''. Falta endereçamento indireto. Instruções são na máquina de estados finitos na [[Arquitetura Harvard]].
*[[Máquina de Ponteiros]]  – Uma mistura de máquina de contador e modelos RAM. Menos comum e mais abstrata do que ambos modelos. Instruções são na máquina de estados finitos na arquitetura Harvard.
*Máquina de acesso aleatório ([[RAM]]) – uma máquina de contador com endereçamento indireto e, geralmente, um conjunto de instruções melhorado. Instruções são na máquina de estados finitos na arquitetura Harvard.
*Máquina de programa armazenado de acesso aleatório, modelo (RASP)
Uma máquina de acesso aleatório com instruções em seus registradores análogo a [[Máquina de Turing universal]]; sendo assim, um exemplo da [[arquitetura de von Neumann]]. Mas diferente de um computador, o modelo é “idealizado” com efetivamente infinitos registradores(e se usados, efetivamente infinitos registradores especiais, como um acumulador). Diferente de em um computador ou mesmo [[RISC]], o conjunto de instruções é de um número muito mais reduzido.

Qualquer modelo de máquina de registradores é [[Turing completude|Turing equivalente]].
Velocidade computacional é bastante dependente das especificações de cada modelo.

Na ciência da computação prática, um conceito simular é conhecido como [[máquina virtual]] é usado ocasionalmente para minimizar as dependências em arquitetura de máquina subjacentes. Como máquinas também são usadas para ensinar. O termo “máquina de registradores” é usado as vezes para referir a máquina virtual em livros didáticos.
<ref>[[Harold Abelson]] e [[Gerald Jay Sussman]] com Julie Sussman, [[Structure and Interpretation of Computer Programs]], [[MIT Press]], [[Cambridge, Massachusetts]], 2nd Ed, 1996</ref>

== Definição formal ==
:''Nenhuma terminologia padrão existe; cada autor é responsável por definir os seus mnemônicos ou símbolos. Muitos autores usam um símbolismo “registrar-transferir” para explicar as ações dos seus modelos, mas novamente eles são responsáveis por definir suas sintaxe.''

Uma máquina de registradores consiste de:

#'''Um não vinculado número de rotulados, discretos, registradores não vinculados por extensão(capacidade)''': um finito(ou infinito, em alguns modelos) conjunto de registradores  <math>r_0 \ldots r_n</math> cada um considerado como de extensão infinita e cada um suportando um numeral não negativo (0,1,2,...).<ref>". . . uma sequência contável de registradores numerados 1,2,3, ..., cada um podendo armazenar números naturais 0,1,2,... Cada programa particular, no entanto, envolve apenas um número finito desses registradores, os outros permanecendo vazios(i.e. contendo 0) durante a computação." Shepherdson e Sturgis 1961:219. Lambek 1961:295 propuseram "um contável conjunto infinito de  ''localidades'' (buracos, fios, etc).</ref> Os registradores podem fazer a sua própria aritmética, ou pode ser que haja um ou mais registrador especial que faz a aritmética. Por exemplo, um "acumulador" e/ou um "registrador de endereços".
#'''Contadores ou marcadores''':<ref>Por exemplo, Lambek 1961:295 propôs o uso de pedras, grânulos, etc.</ref> discretos, indistiguíveis objetos ou marcadores de um ou mais números adequados ao modelo. No mais reduzido modelo de máquina de contador, para cada operação aritmética apenas um objeto/marcador é ou adicionado ou removido de sua localidade/fita. Em alguns modelos de máquina de contador(ex: Melzak (1961), Minsky (1961)) e maior parte dos modelos RAM e RAPS podem adicionar ou remover mais de um objeto/marca com a operação de "adição" e geração "[[subtração]]"; ocasionalmente com "multiplicação" e/ou "divisão". Alguns modelos tem operações de controle como "copiar" (variavelmente: "mover", "ler", "armazenar") que move grupos de objetos/marcas de registrador a registrador em uma ação.
#'''Um limitado conjunto de instruções''':  as instruções tendem a ser divididas em duas classes: artimética e controle. As instruções são tiradas de duas classes para formar conjuntos de instruções, tal qual um conjunto de instruções deve permitir o modelo de ser [[Turing completude|Turing equivalente]] (deve ser capaz de computar qualquer [[função computável|função recursiva parcial]]).
##'''Aritmética''': instruções aritméticas devem operar sobre todos os registradores ou somente sobre um registrador especial(ex: acumulador). Eles são "geralmente" escolhidos pelos seguintes conjuntos(mas exceções se aplicam):
##*Máquina de contador: { Incrementar (r), Decrementar (r), Clear-to-zero (r) }
##*Reduced RAM, RASP: { Incrementar (r), Decrementar (r), Clear-to-zero (r), Ler constante imediata k, Adicionar (r<sub>1</sub>,r<sub>2</sub>), subtração-própria (r<sub>1</sub>,r<sub>2</sub>), Incrementar acumulador, Decrementar acumulador, Limpar acumulador, Adicionar para acumulador conteúdo do registrador r, subtração-própria do conteúdo do acumulador registrado r, }
##*Augmented RAM, RASP: Todas funções reduzidas e mais: { Multiplicar, Dividar, várias funções booleanas de bit(left-shift, teste de bit, etc.)}
##'''Controle''':
##*Modelos de máquina de controle: opcional { Copiar tal (r<sub>1</sub>,r<sub>2</sub>) }
##*Modelos RAM e RASP: deve haver { Copiar (r<sub>1</sub>,r<sub>2</sub>) }, ou { Ler acumulador de r, Guardar acumulador em r, Ler acumulador com uma constante imediata }
##*Todos modelos: ao menos um  "salto" ''condicional'' (branch, goto) seguindo teste de um registrador ex: { Jump-if-zero, Jump-if-not-zero (i.e. Jump-if-positive), Jump-if-equal, Jump-if-not equal  }
##*Todos modelos opcionais: { "salto" de programa incondicional (goto) }
##'''Método de endereçamento de registrador''':
##*Máquina de contador: sem endereçamento indireto, operações imediatas em modelos altamente atomizados
##*RAM and RASP: endereçamento indireto viável, operações imediatas típicas
##'''Input-output''': opcional em todos os modelos.
#'''Registrador de estados''': Um registrador de instruções especiais "IR", finito e separado dos outros registradores acima, armazenando a instrução atual para ser executa e endereça na TABELA de instruções; este registrador e a TABELA é localizada na máquina de estados finitos.
#*O IR é limitante para todos os modelos. No caso do RAM e RASP, por propósito de determinar o "endereço" de um registrador, o modelo pode selecionar tanto (i) no caso de endereçamento direto é especificado pela TABELA e temporariamente localizados no IR ou (ii) no caso de endereçamento indireto - o conteúdo do registrador é especificado pela instruções de  IR.
#*O IR "não" é o "contador de programação"(PC) do RASP(ou [[computador]] convencional). O PC é só outro registrador similar ao acumulador, mas dedicado a armazenar números da atual instrução de registro do RASP. Assim, o RASP tem ''duas'' "instruções/programações" registradores—(i) o IR (Registrador de instrução da máquina de estado finito), e (ii) um PC (contador de programação) para o programa localizado nos registos. (Bem como um registro dedicado à "PC", um RASP podem dedicar outro registro para o "Registro de instruções do programa" (indo por qualquer número de nomes como "PIR" IR "," PR ", etc.)
#'''Lista de instruções rotulados, geralmente em ordem sequencial''': Uma lista de instruções finitas <math>I_1 \ldots I_m</math>. No caso da máquina de contador, máquina de acesso aleatório e máquina de ponteiro, as instruções estão na  "TABELA" de estados finitos da máquina; assim esses modelos são exemplos de arquitetura de Harvard. No caso da programação RASP, as instruções estão nos registradores;
Assim é um exemplo da [[arquitetura de von Neumann]]. Geralmente, como [[programa de computador|programas de computador]], as instruções são listadas em ordem sequencial; a não ser que um salto seja sucedido na sequência padrão e continue na ordem número. Uma exceção disso é o abaco (Lambek (1961), Minsky (1961)) modelos de máquinas de contadores—toda instrução tem ao menos um  "próximo" identificador de instrução "z", e o branch condicional tem dois.
*Observe que o modelo ábaco combina duas instruções, JZ then DEC: e.g. { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub> ) }.<br>Veja ''McCarthy Formalism'' para mais sobre ''expressões condicionais '' "IF r=0 THEN z<sub>true</sub> ELSE  z<sub>false</sub>" (cf McCarthy (1960)).

== Desevolvimento histórico do modelo da máquina de registradores  ==

Duas tendências apareceram no começo dos [[anos 1950]] - a primeira para caracterizar o [[computador]] como uma [[máquina de Turing]]; e a segunda para definir modelos de computador com instruções sequenciais e saltos condicionais-com o poder de uma máquina de Turing, i.e. uma chamada [[Turing completude|Turing equivalência]]. Necessidades  para este trabalho foram realizados no âmbito de dois problemas "difíceis": o problema da palavra indicesivel mostrado por [[Emil Post]]-seu problema da "parada"-e os "dificílimos" [[problemas de Hilbert]]-a 10 questão sobre [[equação diofantina|equações diofantinas]]. Pesquisadores estavam procurando por modelos Turing-equivalentes que fossem menos "lógicos" em natureza e mais "aritmético".  (cf Melzak (1961) p.&nbsp;281, Shepherdson-Sturgis (1963) p.&nbsp;218).

A primeira tendência-em direção a caracterização de computadores-parece ter originado<ref>Veja a "Nota" em Shepherdson e Sturgis 1963:219. No seu apêndice A o autor segue com uma listagem e discussão sobre o conjunto de instruções de Kaphengst, Ershov and Péter(cf p. 245ff).</ref> com [[Hans Hermes]] (1954), [[Rózsa Péter]] (1958), e [[Heinz Kaphengst]] (1959), a segunda tendência com [[Hao Wang (academic)|Hao Wang]] (1954, 1957) e, como notado acima, expandida por [[Zdzislaw Alexander Melzak]] (1961), [[Joachim Lambek]] (1961), [[Marvin Minsky]] (1961, 1967), e [[John Shepherdson]] e [[Howard E. Sturgis]] (1963).

Os últimos cinco nomes são listados explicitamente em ordem por [[Yuri Matiyasevich]]. Ele continua com:
:"Máquina de registradores [alguns autores usam "máquina de registradores" sinonimamente com "máquina de contador"] são particularmente adequadas para construírem equações diofantinas. Como máquinas de Turing, elas tem instruções primitivas e, em adição, elas lidam com números" (Yuri Matiyasevich (1993), ''Hilbert's Tenth Problem'', comentário do capítulo 5 do livro, no http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm. )

Aparentemente Lambek, Melzak, Minsky e Shepherdson e Sturgis anteciparam independentemente a mesma idéia ao mesmo tempo.

A história começa com o modelo de Wang.

=== (1954, 1957) Modelo de Wang: Máquina de Post-Turing ===
O trabalho de Wang segui com os papeis de [[Emil Post]] (1936), o que direcionaram para a definição de sua[[Wang B-machine]]—um modelo computável de [[Máquina de Post-Turing]] com apenas quatro instruções atômicas:
:{ LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }

Para esses quatro, tanto Wang (1954, 1957) e também C.Y. Lee (1961) adicionou outra instrução para o conjunto de Post { ERASE },  e então o salto incondicional de Post { JUMP_to_ instruction_z } (ou, para fazer as coisas mais fáceis, o salto condicional JUMP_IF_blank_to_instruction_z, ou ambos. Lee nomeou este um modelo "W-machine":
:{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }

Wangs expressou esperanças de que seu modelo fosse uma  "aproximação" (p.&nbsp;63) entre as máquinas teóricas deTuring e o computador do mundo prático.

O trabalho de Wang foi altamente influente. Nós o vemos ser referenciado por Minsky (1961) e (1967), Melzak (1961), Shepherdson e Sturgis (1963). De fato, Shepherdson e Sturgis (1963) observaram que:
:"... nós temos dar um passo a frente da 'aproximação' entre os aspectos teóricos e práticos da computação sugeridos por Wang" (p. 218)

[[Martin Davis]] eventualmente evoluiu esse modelo na Máquina de Post-Turing de 2 símbolos.

'''Dificuldades com o modelo de Wang/modelo de Post-Turing''':

Exceto de que havia um problema: o modelo de Wang(as seis instruções no modelo de 7 na máquina de Post-Turing) ainda era como uma máquina de Turing de de fita única, não importando o quanto o seu ''programa de instruções sequenciais'' era bom. Tanto Melzak (1961) e Shepherdson e Sturgis (1963) observaram isso (no contexto de certas provas e investigações):

:"... uma máquina de Turing tem uma certa opacidade... uma máquina de Turing é lenta(hipoteticamente) e operações e, geralmente, complicada. Isso a faz consideravelmente difícil de definir, e ainda mais difícil de investigar esses problemas como otimização de tempo o estoque ou uma comparação de eficiência de dois algarismos. (Melzak (1961) p. 281)

:"...ainda que não difíceis ... provas são complicadas e tediosas de seguir por duas razões: (1) Uma máquina de Turing só tem apenas uma cabeça, o que obriga a computação ser divida em pequenos passos de operações de dígito único.(2)
Ela tem somente uma fita, então existe certa dificuldade de se encontrar o número em que se deseja trabalhar e mantê-lo separado dos outros números" (Shepherdson and Sturgis (1963) p.&nbsp;218).<!-- Example: Multiply '''a''' x '''b''' = '''c''', for example: 3 x 4 = 12.

The scanned square is indicated by brackets around the mark i.e. ['''1''']. An extra mark serves to indicate the symbol "0".

At the start of a computation, just as Shepherdson-Sturgis and Melzak complain, we see the variables expressed in unary—i.e. the tally marks for '''a'''= '''| | | |''' and '''b''' = '''| | | | |''' – "in a line" (concatenated on what Melzak calls a "linear tape"). Space must be available for '''c''' at the end of the computation, extending without bounds to the right:
{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
| width="14.4" Height="11.4" |
| width="13.8" |
| width="13.8" |
| width="13.8" | top
| width="13.8" | a
| width="13.8" | a
| width="13.8" | a
| width="13.8" |
| width="13.8" | top
| width="13.8" | b
| width="13.8" | b
| width="13.8" | b
| width="15.6" | b
| width="13.8" |
| width="13.8" | btm
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" |
| width="13.8" |
| width="13.8" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="11.4" |
 |
 |
|style="background-color:#FFFF99" | [1]
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
 |
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|}

At the end of the computation the multiplier '''b''' is 5 marks "in a line" (i.e. concatenated) to left of the 13 marks of product '''c'''.
{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
| width="14.4" Height="11.4" |
| width="13.8" |
| width="13.8" |
| width="13.8" | top
| width="13.8" | a
| width="13.8" | a
| width="13.8" | a
| width="13.8" |
| width="13.8" | top
| width="13.8" | b
| width="13.8" | b
| width="13.8" | b
| width="15.6" | b
| width="13.8" |
| width="16.8" | btm
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
|- style="font-size:9pt" align="center" valign="bottom"
| Height="11.4" |
 |
 |
 |
 |
 |
 |
 |
|style="background-color:#CCFFCC" | [1]
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
 |
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
 |
 |
 |
|}-->
===Modelos de "corte de fita" de Minsky, Melzak-Lambek e Shepherdson-Sturgisx===
Entao por que não cortar a fita para que cada uma seja infinitamente longa(para acomodar numerais de qualquer número), mas com finais a esquerda, e chamar esse modelo de "Post-Turing de três fitas"? As cabeças individuais irão mover para esquerda(para decrementar) e para direita(para incrementar). Em um sentido as cabeças indicam "o topo da pilha" dos pontos concatenados. Ou em Minsky (1961) e Hopcroft e Ullman (1979, p.&nbsp;171ff) a fita está sempre vazia exceto pela marca a esquerda - em nenhum momento uma cabeça imprime ou apaga. Nós apenas temos que tomar cuidado para escrever nossas instruções para que um teste por zero e saltos ocorram antes de decrementar, senão nossa máquina irá "cair para fim"-nós temos uma instância de [[função parcial]]. Antes de uma diminuição, nossa máquina deve sempre perguntar: "A fita está vazia? Se sim, então eu não posso decrementar. Se não, então eu posso."

Minsky (1961) e Shepherdson-Sturgis (1963) provaram que apenas algumas fitas-quase nenhumas-ainda permitiam que a máquina fosse Turing equivalente SE o dado na fita fosse representado como um número de Gödel(ou outro número unicamente decodificável); este número vai evoluir conforme a computação procede. Na versão versão de uma fita com o número de Gödel , a máquina de contador deve ser capaz de (i) multiplicar o número de Gödel por uma constante(números "2" ou "3"), e (ii) dividir por uma constante, e saltar se o restante for zero. Minsky (1967) mostra que é necessário para que esse conjunto de instruções bizarro possa ser simplificado para &nbsp;{ INC (r), JZDEC (r, z) } e as instruções &nbsp;{ CLR (r), J (r) } se as duas fitas estiverem disponíveis. No entanto, uma simples Gödelização ainda é necessária. Um resultado similar aparece em Elgot-Robinson (1964) com respeito ao modelo RASP.
<!-- To do a multiplication algorithm we don't need the extra mark to indicate "0", but we will need an extra "temporary" tape '''t'''.  And we will need an extra "blank/zero" register (e.g. register #0) for an unconditional jump:

{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
|style="font-weight:bold" width="83.4" Height="12" | At  the start:
| width="16.8" |
| width="15" |
| width="16.2" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | register 0:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | a = register 1:
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99;font-weight:bold" | []
|style="font-weight:bold" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | b = register 2:
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | c = register 3:
|style="background-color:#CCFFFF;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | t = register 4:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="3" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt"
|style="font-weight:bold" Height="12" align="center" valign="bottom" | At the end:
|  valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | register 0:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | a = register 1:
|style="background-color:#FFFF99;font-weight:bold" | []
 |
 |
 |
|style="font-weight:bold" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | b = register 2:
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | c = register 3:
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF;font-weight:bold" | []
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | t = register 4:
 | 1
 | 1
 | 1
 | 1
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|}

We can write simple Post-Turing "subroutines" to atomize "increment" and "decrement" into Post-Turing instructions. Note that the head stays always just one square to the right of the top-most printed mark, i.e. at the "top of the stack". "r" is a parameter in the instructions that symbolizes the tape-as-register to be moved and printed or erased, and tested:
:
: "Increment r" = PRINT_SCANNED_SQUARE_of_TAPE_r, MOVE_TAPE_r_LEFT; i.e. (or: move tape r's head right)
::'''X+''' r is equivalent to '''P''' r; '''L''' r
: "Decrement r" = JUMP_IF_TAPE_r_BLANK(ZERO) TO XXX, ELSE MOVE_TAPE_r_RIGHT, ERASE_SCANNED_SQUARE_of_TAPE_rN; (or: move tape r's head left)
::'''X-''' r is equivalent to '''J0''' r, xxx; '''R''' r; '''E''' r

Indeed this is similar to the approach that Minsky (1961) took. He started with 4 left-ended tape-machine that:
: "used the basic arithmetic device of the present paper. Then, two of the tapes were eliminated by the prime-factor method" (p. 438).

He then observed that:
: "we may formulate these results so that the operations act essentially only on the ''length'' of the strings" (his italics, p. 449).

His first model, "1961" (it had changed by 1967) started out with only a single mark at the left end of each tape-as-register. The machine was not allowed to '''P'''rint any marks, just move '''L'''eft or '''R'''ight and test for the mark = "1" in the following example. Thus the conventional Post-Turing-like instruction set went from
: { R; L; P; E; J0 xxx; J1 xxx, H }

to, for each tape-as-register:
: { R; L; J1 xxx, H }

where '''R''' can be renamed '''INC'''rement, '''R''' can be renamed '''DEC'''rement, "J1" can be combined with "DEC" to create a non-atomized instruction, or can be kept separate and renamed '''J'''ump if '''Z'''ero. -->

=== (1961) O modelo de Melzak é diferente: grupos de pedras vão pra dentro e pra fora de aberturas===
O modelo de Melzak (1961) é significativamente diferente. Ele pegou seu próprio modelo, virou as fitas verticalmente, chamou-as de “aberturas no chão” a serem enchidos por “contadores pedras”. Diferente do “incremente” e “decremente” de Minsky, Melzak permitiu subtração, e adição, convencional de qualquer quantidade de pedras.

Ele define endereçamento indireto para seu modelo (p.&nbsp;288) e mostra dois exemplos de seu uso (p.&nbsp;89); sua prova (p.&nbsp;290-292) de que o modelo é [[Turing completo|Turing equivalente]] é tão “nebulozamente” explicada que o leitor não consegue distinguir se ele desejava ou não que endereçamento indireto fosse necessário para a prova.

O legado do modelo de Melzak é a simplificação do modelo de Lambek e a reaparição de suas convenções mnemônicas em Cook e Reckhow (1973).

=== Lambek (1961) reduz o modelo de Melzak no modelo de Minsky (1961): INC e DEC-with-test ===
Lambek (1961) tomou o modelo ternário de Melzak e o reduziu às duas instruções unárias —X+, X- if possible else jump— exatamente as mesmas que Minsky (1961) apresentou.

No entanto, como o modelo de Minsky (1961), o modelo de Lambek executa suas instruções de uma maneira sequencial—tanto X+ quanto X- carregam o identificador da próxima instrução, e X- também carrega a instrução jump-to se o teste condicional ocorrer com sucesso.

=== Elgot-Robinson (1964) e o problema da RASP sem endereçamento indireto===
Uma RASP ou máquina RASP começa como uma máquina de contador com sua “programa de instruções” em seus “registradores”. Analogamente ao, mas independente do, “Registrador de Instruções” de uma máquina de estado finita, pelo menos um de seus registradores (chamado de “contador de programa” (PC)) e um ou mais registradores “temporários” mantém um registro de, e operam no, número da instrução atual. A tabela de instruções de uma máquina de estado finita é responsável por (i) buscar a instrução de programa atual do registrador apropriado, (ii) ler a instrução de programa, (iii) buscar os operados especificados pela instrução de programa, e (iv) executar a instrução de programa.

No entanto há um problema: Se for baseada na “máquina de contadores” esse “computador”, máquina de [[von Neumann]] não será Turing-equivalente. Ela não consegue computar tudo que é computável. Intrinsecamente, o modelo e limitado pelo tamanho de suas instruções de máquina de estado (bastante) “finitas”. O RASP baseado numa máquina de contadores pode computar qualquer [[função recursiva primitiva]] (como multiplicação, por exemplo), mas não todas as funções mu-recursivas, como a [[função de Ackermann]].

Elgot-Robinson investigou a possibilidade de permitir seu modelo RASP a modificar por si só suas próprias instruções de programa. Essa era uma ideia antiga, proposta por Burks-Goldstine-von Neumann (1946-7), e algumas vezes chamada de “o ''goto'' computado”. Melzak (1961) menciona especificamente o “''goto'' computado” por esse nome, mas provê seu modelo com endereçamento indireto em seu lugar.

'''''Goto'' computado:''' Um programa RASP de instruções que modifica o “endereço ''goto''” em uma instrução de pulo (jump) condicional ou incondicional.
Mas isso não resolve o problema (a não ser que se faça uso de [[números de Gödel]]. O que é necessário é um método de buscar o endereço de uma instrução de programa que está (bastante) “depois/acima” do limite superior do registrador e tabela de instruções da máquina de estados finita.

:Exemplo: Uma máquina de contadores equipada com apenas 4 registradores não limitados pode, por exemplo, multiplicar qualquer dois números (m e n), resultando em um número p, e assim ser uma função recursiva primitiva, não importa quão grande sejam os números m e n. Além disso, menos de 20 instruções são necessárias para essa operação! Por exemplo:  { 1: CLR ( p ), 2: JZ ( m, done ), 3 outer_loop: JZ ( n, done ), 4: CPY ( m, temp ), 5: inner_loop: JZ ( m, outer_loop ), 6: DEC ( m ), 7: INC ( p ), 8: J ( inner_loop ), 9: outer_loop: DEC ( n ), 10 J ( outer_loop ), HALT }

:No entanto, com apenas 4 registradores, essa máquina não é nem de perto grande o suficiente para construir uma RASP que consiga executar o algoritmo de multiplicação como um “programa”. Não importa o quão grande nós construamos nossa máquina de estados finita, sempre haverá um “programa” (junto com seus parâmetros) que é maior do que a máquina. Assim, por definição, a máquina de programas limitada que não use truques de codificação não limitados como os números de Gödel não pode ser “universal”.

Minsky (1967) menciona esse problema em sua investigação de uma máquina de contadores. (ele as chama de “modelos de computador de programas”) equipado com as instruções { CLR (r), INC (r), e RPT (repita as instruções de m a n um certo número de vezes) }. Ele não nos diz como consertar o problema, mas ele observa que:
: “... o computador de programas tem de possuir alguma maneira de manter um registro de quantas instruções RPT ainda precisam ser executadas, e isso pode exaustar qualquer quantidade particular de armazenamento permitido na parte finita do computador. Operações RPT requerem registradores infinitos para elas próprias, no geral, e elas tem de ser tratadas diferentemente dos outros tipos de operações que nós já consideramos.” (p. 214)

Mas Elgot e Robinson resolveram o problema: eles aumentaram seus RASP P<sub>0</sub> com um conjunto de instruções indexado - uma forma, de uma certa maneira, mais complicada (mas mais flexível) de endereçamento indireto. Seu modelo  P'<sub>0</sub> endereça os registradores adicionando o conteúdo do registrador “base” (especificado na instrução) ao “index”, especificado explicitamente na instrução (ou vice versa, trocando “base” e “index”). Dessa maneira, a instruções indexadoras P'<sub>0</sub> possuem um parâmetro a mais quando comparado com as instruções não-indexadoras P<sub>0</sub>:
: Exemplo: INC ( r<sub>base</sub>, index ); o endereço efetivo será [r<sub>base</sub>] + index, onde o número natural “index” é derivado da própria instrução.
=== Hartmanis (1971) ===
Em 1971, Hartmanis simplificou a indexação para indireção com o objetivo de usá-lo em seu modelo RASP.

'''Endereçamento Indireto:''' Um registrador-ponteiro provê à máquina de estados finita o endereço do registrador “alvo” requerido pela instrução. Em outras palavras: O “conteúdo” do registrador-ponteiro é o “endereço” do registrador “alvo” a ser usado pela instrução. Se o registrador ponteiro for ilimitado, a RAM, e um RASP adequado anexado no seu chassi, vai ser Turing-equivalente. O registrador “alvo” pode servir tanto como um registrador fonte (source) ou destino (destination), da maneira que estiver especificado na instrução.

Note que a máquina de estado finita não tem que especificar explicitamente o endereço desse registrador alvo. Ele apenas diz para o resto da máquina: Dê-me o conteúdo do registrador apontado pelo meu registrador-ponteiro e depois faça xyz com isso. Esse registrador ponteiro deve ser especificado explicitamente por nome (“N”, ou “72, ou “PC”, por exemplo), através da respectiva instrução, mas não é necessário ter conhecimento do conteúdo desse registrador.

=== Cook e Reckhow (1973) descrevem a RAM ===
Cook e Reckhow (1973) citam Hartmanis (1971) e simplificam seu modelo para o que eles chamam de [[Máquina de acesso randômico]] (em inglês, Random Access Machine, RAM, i.e. uma máquina com indireção e [[arquitetura Harvard]]). De uma certa maneira voltando a ideia presentada por Melzak (1961), mas com um modelo bem mais simples.

== Precedência ==

Minsky estava trabalhando no ''M.I.T. Lincoln Labs'', onde publicou seu trabalho. Seu artigo foi recebido para publicação nos “Anais de Matemática” em 15 de Agosto, 1960, mas nao publicado até Novembro de 1961. Mesmo tendo sido submetido um ano antes dos trabalhos de Melzak e Lambek fosse submetido e publicado (recebidos, respectivamente, em 15 de Maio e 15 de Junho de de 1961 e publicados juntos em setembro de 1961). O fato de (i) ambos serem canadenses e publicados no Boletim de Matemática Canadense, (ii) nenhum dos dois referenciarem o trabalho de Minsky, pois esse ainda não havia sido publicado em um periódico, mas (iii) Melzak referenciar Wang, e Lambek referenciar Melzak, leva a hipótese de que seus trabalhos se desenvolveram simultaneamente e independentemente.

Quase exatamente a mesma coisa aconteceu com Shepherdson e Sturgis. Seus artigos foram recebidos em dezembro de 1961 - alguns meses depois dos artigos de Melzak e Lambek. Novamente, eles tiveram pouca (no máximo um mês) ou nenhuma chance de revisar o trabalho de Minsky. Eles foram cuidados em observar em uma nota de rodapé que artigos de Eschov, Kaphengst e Peter haviam “aparecido recentemente” (p.&nbsp;219). Na verdade, esses foram publicados muito antes, mas em jornais alemães, publicados em alemão, o que dificultou a acessibilidade ao trabalho.

O ultimo artigo de Shepherdson  e Sturgis não apareceram em um periódico até 1963. Além disso, como eles honestamente descrevem no Apendix A, os ‘sistems’ de Kaphengst (1959), Ershov (1958), Peter (1958) são todos tão similares entre si quanto aos resultados obtidos, descritos como um conjunto indistinguível do seguinte:
: produza 0 i. e. 0 --> n
: incremente um número i.e. n+1 --> n
::”i.e. realizando as operações geradoras de números naturais” (p. 246)
: copie um número i.e. n --> m
: para “mudar o curso da computação”, seja comparando dois números ou decrementando até 0.

Realmente, Shepherson e Sturgis concluem:
::”Os  varios sistemas mínimos são muito similares” (p. 246)

Ordenados pela data de publicação, os trabalhos de Kaphengst (1959), Ershov (1958) e Peter (1958) vieram primeiro.

==Veja também==
{{colbegin||25em}}
* [[Máquina de contador]]
** [[Máquina de contador:modelos de referência]]
** [[Modelos de máquinas de contador]]
* [[Máquina de ponteiros]]
* [[Máquina RA (Random Access)|Máquina RA]]
* [[Máquina RASP (Random-Access Stored-Program)|Máquina RASP]]
* [[Máquina de Turing]]
** [[Máquina de Turing universal]]
** [[Galeria das máquinas de Turing]]
** [[Exemplos de Máquinas de Turing]]
* [[Máquina Wang-b]]
* [[Máquina de Post-Turing]]
* [[Algoritmo]]
** [[Caracterização de Algoritmos]]
** [[Exemplos de Algoritmos]]
* [[Problema da parada]]
* [[Algoritmo do Castor]]
* [[Máquina Stack]]
{{colend}}

== Bibliografia==
'''Textos base'''  A seguinte bibliografia de artigos inclui alguns textos a serem usados como base. A matemática que leva ao conjunto de artigos sobre máquinas abstratas nos anos 50 e 60 podem ser encontrados em van Heijenoort (1967) - uma coletânea de artigos originais cobrindo os 50 anos desde Frege (1879) até Gödel (1964) (p.&nbsp;71); os artigos original de [[Alan Turing]] (1936-7) e [[Emil Post]] (1936) estão incluídos em “The Indecidable”. As matemáticas de Church, Rosser e Kleene que aparecem como reimpressões dos artigos original em “The Indecidable” continuaram a ser exploradas em Kleene (1952), um texto indispensável para qualquer pessoa procurando um entendimento mais profundo da matemática por trás das máquinas. Tanto Kleene (1952) quanto Davis (1958) são referenciados por vários artigos.

Para um bom estudo da máquina de registradores veja Minsky (1967), capítulo 11, “Modelos similares a Computadores Digitais” - onde ele chama a máquina de registradores de “computador-programa”. Uma nova visão é encontrada em van Emde Boas (1990). Um estudo recente do modelo de Minsky (1961)/Lambek (1961) pode ser encontrado em Boolos-Burgeess-Jeffrey (2002); eles reencarnaram o “modelo do ábaco” de Lambek para demonstrar equivalência entre máquinas de Turing e funções parcialmente recursivas, e eles disponibilizam uma introdução de nível de mestrado para tanto modelos de máquinas abstratas (contadoras e de Turing) e a matemática da teoria da recursão. Começando com a primeira edição de Boolos-Burgess (1970), esse modelo apareceu com virtualmente o mesmo nível de detalhe.

'''Os artigos''': Os artigos começam com Wang (1957) e sua dramática simplificação da máquina de Turing. Turing (1936), Kleene (1952), Davis (1958)  e em particular Post (1936) são citados em Wang (1957); por sua vez, Wang é referenciado por Melzak (1961), Minsky (1961) e Shepherdson -Sturgis (1961-3) na maneira em como eles independentemente reduzem as fitas da máquina de Turing a “contadores”. Melzak (1961) mostra seu modelo de  máquina de contadores “pebble-in-holes” (pedra-em-buracos, literalmente) com indireção, mas não conduz o estudo a frente. O trabalho de Elgot-Robinson (1964) define a máquina RASP (Random Access Stored Program) e parece ser o primeiro a investigar a falha que máquinas de contadores limitadas tem em calcular funções mu-recursivas. Essa falha - com exceção do uso draconiano do [[Número de Gödel]] a moda de Minsky (1961) - leva a sua definição de instruções “indexadas” (i.e. endereçamento indireto) para seu modelo RASP. Elgot-Robinson (1964) e também Hartmanis (1971) investigam RASPs com programas que modificam a si mesmos. Hartmanis (1971) especifica um conjunto de instruções com indireção, citando notas de aula de Cook (1970). Para uso em investigações de complexidade computacional, Cook e seu estudante de graduação Reckhow (1973) provem a definição de uma RAM (o modelo e a convenção mnemônica são similares as de Melzak, mas não o referenciam no artigo). As máquinas de ponteiros são um trabalho de Knuth (1968, 1973) e, independentemente, de Schönhage (1980).

Em sua maior parte os artigos contem matemática que ultrapassa o nível de um curso de graduação - em particular [[funções recursivas primitivas]] e [[funções mu-recursivas]] apresentadas elegantemente em Kleene (1952) e superficialmente, mas útil de qualquer maneira, em Boolos-Burgess-Jeffrey (2002).

Todos os textos e artigos com exceção dos quatro marcados com asteriscos foram revisados. Esses quatro estão escritos em alemão e aparecem como referencia em Shepherdson-Sturgis (1963) e Elgot-Robinson (1964), Shepherson-Sturgis (1963) oferecem uma breve discussão de seus resultados no apendix A do trabalho de Shepherson-Sturgis. A terminologia de pelo menos um artigo (Kaphengst (1959) parece usar a mesma análise de arquitetura de computadores de Burke-Goldstine-von Neumann(1946-7).

{|class="wikitable" style="text-align:center; font-size:88%"
|-  style="vertical-align:bottom;"
! style="width:114.6;"| Autor
! style="width:43.2;"| Ano
! style="width:46.8;"| Referência
! style="width:41.4;"| Máquina de Turing
! style="width:43.2;"| Máquina de Contadores
! style="width:27.6;"| RAM
! style="width:28.2;"| RASP
! style="width:38.4;"| Máquina de Ponteiros
! style="width:54px;"| Endereçamento Indireto
! style="width:43.8;"| Programas meta-modificadores
|-  style="vertical-align:bottom;"
| style="text-align:left" | Goldstine & von Neumann
| 1947
| X
|
|
|
|
|
|
| X
|-  style="vertical-align:bottom;"
| style="text-align:left" | Kleene
| 1952
| X
|
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | *Hermes
| 1954, 5
|
|
| ?
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Wang
| 1957
| X
| X
| superficialmente
|
|
|
| superficialmente
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | *Peter
| 1958
|
|
| ?
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Davis
| 1958
| X
| X
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | *Ershov
| 1959
|
|
| ?
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | *Kaphengst
| 1959
|
|
| ?
|
| X
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Melzak
| 1961
|
|
| X
|
|
|
| X
| superficialmente
|-  style="vertical-align:bottom;"
| style="text-align:left" | Lambek
| 1961
|
|
| X
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Minsky
| 1961
|
|
| X
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Shepherdson & Sturgis
| 1963
|
|
| X
|
|
|
| superficialmente
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Elgot & Robinson
| 1964
|
|
|
|
| X
|
| X
| X
|-  style="vertical-align:bottom;"
| style="text-align:left" | Davis- Undecidable
| 1965
| X
| X
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | van Heijenoort
| 1967
| X
|
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Minsky
| 1967
|
|
| X
| superficialmente
|
|
| superficialmente
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Knuth
| 1968, 73
| X
|
|
|
|
| X
| X
| X
|-  style="vertical-align:bottom;"
| style="text-align:left" | Hartmanis
| 1971
|
|
|
|
| X
|
|
| X
|-  style="vertical-align:bottom;"
| style="text-align:left" | Cook & Reckhow
| 1973
|
|
|
| X
| X
|
| X
| X
|-  style="vertical-align:bottom;"
| style="text-align:left" | Schonhage
| 1980
|
|
|
| X
|
| X
| X
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | van Emde Boas
| 1990
| X
| X
| X
| X
| X
| X
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Boolos & Burgess; Boolos, Burgess & Jeffrey
| 1970–2002
| X
| X
| X
|
|
|
|
|
|}

==Referências==
'''Notas'''
{{reflist}}
'''Fontes'''
{{refbegin}}
* [[George Boolos]], [[John P. Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 ''Abacus Computability''; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp.&nbsp;92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4  .
* [[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354-375.
* [[Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
* [[Calvin Elgot]] and [[Abraham Robinson]] (1964), ''Random-Access Stored-Program Machines, an Approach to Programming Languages'', Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp.&nbsp;365–399.
* [[Juris Hartmanis|J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp.&nbsp;232–245.
* [[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X.  A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
*[[Donald Knuth]] (1968), ''The Art of Computer Programming'', Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
*[[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.
*[[Zdzislaw Alexander Melzak|Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
*{{citar periódico|autor =Marvin Minsky|autorlink =Marvin Minsky  |título=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines  |periódico=Annals of Math  |outros=1961, received agosto 15, 1960  |volume=74  |páginas=437–455  |doi=10.2307/1970290|número=3|publicado=The Annals of Mathematics, Vol. 74, No. 3|jstor=1970290 }}
*{{citar livro|autor = Marvin Minsky |título= Computation: Finite and Infinite Machines |edição= 1st |publicado= Prentice-Hall, Inc.|local= Englewood Cliffs, N. J. |ano= 1967}} In particular see chapter 11: ''Models Similar to Digital Computers'' and chapter 14: ''Very Simple Bases for Computability''. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
*[[John C. Shepherdson]] and [[H. E. Sturgis]] (1961) received December 1961 ''Computability of Recursive Functions'', Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".
**Kaphengst, Heinz, ''Eine Abstrakte programmgesteuerte Rechenmaschine''', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:''5'' (1959), 366-379.
**[[Andrey Ershov|Ershov, A. P.]] ''On operator algorithms'', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
**[[Rózsa Péter|Péter, Rózsa]] ''Graphschemata und rekursive Funktionen'', Dialectica 12 (1958), 373.
**Hermes, Hans ''Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42-53.
* [[Arnold Schönhage]] (1980), ''Storage Modification Machines'', Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. ''Storage Modification Machines'', in ''Theoretical Computer Science'' (1979), pp.&nbsp;36–37
*[[Peter van Emde Boas]], "Machine Models and Simulations" pp.&nbsp;3–66, in: [[Jan van Leeuwen]], ed. ''Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990. van Emde Boas' treatment of SMMs appears on pp.&nbsp;32–35. This treatment clarifies Schōnhage 1980—it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
*[[Hao Wang (academic)|Hao Wang]] (1957), ''A Variant to Turing's Theory of Computing Machines'', JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23–25, 1954.
{{refend}}

==Ligações externas==
* {{MathWorld|title=Register machine|urlname=RegisterMachine}}
* [http://www.igblan.free-online.co.uk/igblan/ca/minsky.html Igblan - Minsky Register Machines]

{{DEFAULTSORT:Register Machine}}
[[Categoria:Modelos computacionais]]