Máquina de registradores

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áquinas abstratas usadas de uma maneira similar a máquina de Turing. Todos os modelos são Turing equivalentes.

Visão geral

A máquina registradores tem seu nome pelo uso de um ou mais ”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 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.

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:

1. 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 $r_{0}\ldots r_{n}$ cada um considerado como de extensão infinita e cada um suportando um numeral não negativo (0,1,2,...). 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".
2. Contadores ou marcadores: 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.
3. 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 equivalente (deve ser capaz de computar qualquer função recursiva parcial).
   1. 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₁,r₂), subtração-própria (r₁,r₂), 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.)}
   2. Controle:
      • Modelos de máquina de controle: opcional { Copiar tal (r₁,r₂) }
      • Modelos RAM e RASP: deve haver { Copiar (r₁,r₂) }, 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) }
   3. 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
   4. Input-output: opcional em todos os modelos.
4. 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.)
5. Lista de instruções rotulados, geralmente em ordem sequencial: Uma lista de instruções finitas $I_{1}\ldots I_{m}$. 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 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_true, z_false ) }.
  Veja McCarthy Formalism para mais sobre expressões condicionais "IF r=0 THEN z_true ELSE z_false" (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 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ções diofantinas. Pesquisadores estavam procurando por modelos Turing-equivalentes que fossem menos "lógicos" em natureza e mais "aritmético". (cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218).

A primeira tendência-em direção a caracterização de computadores-parece ter originado com Hans Hermes (1954), Rózsa Péter (1958), e Heinz Kaphengst (1959), a segunda tendência com 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 suaWang 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. 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. 218).

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. 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  { INC (r), JZDEC (r, z) } e as instruções  { 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.

(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. 288) e mostra dois exemplos de seu uso (p. 89); sua prova (p. 290-292) de que o modelo é 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₀ 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'₀ 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'₀ possuem um parâmetro a mais quando comparado com as instruções não-indexadoras P₀:

Exemplo: INC ( r_base, index ); o endereço efetivo será [r_base] + 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. 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

• 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
• 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

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. 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).

Autor	Ano	Referência	Máquina de Turing	Máquina de Contadores	RAM	RASP	Máquina de Ponteiros	Endereçamento Indireto	Programas meta-modificadores
Goldstine & von Neumann	1947	X							X
Kleene	1952	X
*Hermes	1954, 5			?
Wang	1957	X	X	superficialmente				superficialmente
*Peter	1958			?
Davis	1958	X	X
*Ershov	1959			?
*Kaphengst	1959			?		X
Melzak	1961			X				X	superficialmente
Lambek	1961			X
Minsky	1961			X
Shepherdson & Sturgis	1963			X				superficialmente
Elgot & Robinson	1964					X		X	X
Davis- Undecidable	1965	X	X
van Heijenoort	1967	X
Minsky	1967			X	superficialmente			superficialmente
Knuth	1968, 73	X					X	X	X
Hartmanis	1971					X			X
Cook & Reckhow	1973				X	X		X	X
Schonhage	1980				X		X	X
van Emde Boas	1990	X	X	X	X	X	X
Boolos & Burgess; Boolos, Burgess & Jeffrey	1970–2002	X	X	X

Referências

Notas

Fontes

Ligações externas

• Weisstein, Eric W. «Register machine» (em inglês). MathWorld 
• Igblan - Minsky Register Machines