Máquina de acesso aleatório - Random-access machine

Na ciência da computação , a máquina de acesso aleatório ( RAM ) é uma máquina abstrata na classe geral de máquinas de registro . A RAM é muito semelhante à máquina do contador, mas com a capacidade adicional de 'endereçamento indireto' de seus registros. Como a máquina de contador, a RAM tem suas instruções na parte de estado finito da máquina (a chamada arquitetura Harvard ).

O equivalente da RAM da máquina de Turing universal  - com seu programa nos registradores e também com seus dados - é chamado de máquina de programa armazenado de acesso aleatório ou RASP. É um exemplo da chamada arquitetura de von Neumann e está mais próximo da noção comum de computador .

Junto com os modelos de máquina de Turing e contra-máquina , os modelos RAM e RASP são usados ​​para análise de complexidade computacional . Van Emde Boas (1990) chama esses três modelos mais a máquina de ponteiro de "modelos de máquina sequencial", para distingui-los dos modelos de " máquina de acesso aleatório paralela ".

Introdução ao modelo

O conceito de máquina de acesso aleatório (RAM) começa com o modelo mais simples de todos, o chamado modelo de máquina de contador . Duas adições o afastam da máquina de balcão, no entanto. O primeiro aprimora a máquina com a conveniência do endereçamento indireto; o segundo move o modelo em direção ao computador baseado em acumulador mais convencional com a adição de um ou mais registros auxiliares (dedicados), o mais comum dos quais é chamado de "o acumulador".

Definição formal

Uma máquina de acesso aleatório (RAM) é um modelo abstrato de máquina computacional idêntico a uma máquina de contagem de registros múltiplos com a adição de endereçamento indireto. A critério de uma instrução da TABELA de sua máquina de estados finitos , a máquina deriva o endereço de um registrador "alvo" (i) diretamente da própria instrução, ou (ii) indiretamente do conteúdo (por exemplo, número, rótulo) do registrador "ponteiro" especificado na instrução.

Por definição: Um registro é um local com um endereço (uma designação / localizador único e distinguível equivalente a um número natural) e um conteúdo  - um único número natural. Para precisão, usaremos o simbolismo quase formal de Boolos-Burgess-Jeffrey (2002) para especificar um registro, seu conteúdo e uma operação em um registro:

  • [r] significa "o conteúdo do registro com o endereço r". O rótulo "r" aqui é uma "variável" que pode ser preenchida com um número natural ou uma letra (por exemplo, "A") ou um nome.
  • → significa "copiar / depositar em" ou "substituir", mas sem destruição da fonte
Exemplo: [3] +1 → 3; significa "O conteúdo do registro de origem com endereço" 3 ", mais 1, é colocado no registro de destino com endereço" 3 "(aqui origem e destino são o mesmo lugar). Se [3] = 37, isto é, o conteúdo de o registro 3 é o número "37", então 37 + 1 = 38 será colocado no registro 3.
Exemplo: [3] → 5; significa "O conteúdo do registro de origem com endereço" 3 "é colocado no registro de destino com endereço" 5 ". Se [3] = 38, isto é, o conteúdo do registro 3 é o número 38, então este número será colocado em registrador 5. O conteúdo do registrador 3 não é perturbado por esta operação, então [3] continua a ser 38, agora o mesmo que [5].

Definição: Uma instrução direta é aquela que especifica na própria instrução o endereço do registrador de origem ou destino, cujo conteúdo será o objeto da instrução. Definição: Uma instrução indireta é aquela que especifica um "registrador de ponteiro", cujo conteúdo é o endereço de um registrador de "destino". O registro de destino pode ser uma origem ou um destino (as várias instruções COPY fornecem exemplos disso). Um registro pode se dirigir a si mesmo indiretamente.

Por falta de um padrão / convenção, este artigo especificará "direto / indireto", abreviado como "d / i", como um parâmetro (ou parâmetros) na instrução:
Exemplo: COPY ( d , A, i , N) significa diretamente d obter o endereço do registrador de origem (registrador "A") da própria instrução, mas indiretamente eu obtenho o endereço de destino do registrador de ponteiro N. Suponha [N] = 3, então o registrador 3 é o destino e a instrução fará o seguinte: [A] → 3.

Definição: o conteúdo do registrador de origem é usado pela instrução. O endereço do registrador fonte pode ser especificado (i) diretamente pela instrução, ou (ii) indiretamente pelo registrador ponteiro especificado pela instrução.

Definição: O conteúdo do registrador ponteiro é o endereço do registrador "alvo".

Definição: O conteúdo do registrador de ponteiro aponta para o registrador de destino  - o "destino" pode ser um registrador de origem ou de destino.

Definição: o registrador de destino é onde a instrução deposita seu resultado. O endereço do registrador fonte pode ser especificado (i) diretamente pela instrução, ou (ii) indiretamente pelo registrador ponteiro especificado pela instrução. Os registros de origem e destino podem ser um.

Refresher: O modelo da contra-máquina

Melzak (1961) fornece uma fácil visualização de uma contra-máquina: seus "registros" são buracos no solo, e esses buracos retêm seixos. Por uma instrução, dentro e fora desses buracos "o computador" (pessoa ou máquina) adiciona (INCrementa) ou remove (DECrementa) uma única pedra. Conforme necessário, seixos adicionais vêm e os seixos em excesso voltam para um suprimento infinito; se o buraco for muito pequeno para acomodar as pedras, o "computador" escava um buraco maior.
Minsky (1961) e Hopcroft-Ullman 1979 (p. 171) oferecem a visualização de uma máquina de Turing multi-fitas com tantas fitas à esquerda quanto "registros". O comprimento de cada fita é ilimitado à direita e todos os quadrados ficam em branco, exceto a extremidade esquerda, que é marcada. A distância da "cabeça" de uma fita de sua extremidade esquerda, medida em números de quadrados de fita, representa o número natural no "registro". Para diminuir a contagem de quadrados, o cabeçote da fita se move para a esquerda; Aumente ele se move para a direita. Não há necessidade de imprimir ou apagar marcas na fita; as únicas instruções condicionais são para verificar se a cabeça está na extremidade esquerda, testando uma marca da extremidade esquerda com uma "instrução pule se marcada".
As seguintes instruções "mnemônicas", por exemplo, "CLR (r)" são arbitrárias; nenhum padrão existe.

A máquina de registro tem, para uma memória externa à sua máquina de estado finito - uma coleção ilimitada (cf: nota de rodapé | contável e ilimitada) de locais discretos e exclusivamente rotulados com capacidade ilimitada , chamados "registros". Esses registros contêm apenas números naturais (zero e os inteiros positivos). Por uma lista de instruções sequenciais na TABELA da máquina de estados finitos, alguns (por exemplo, 2) tipos de operações primitivas operam no conteúdo desses "registradores". Finalmente, uma expressão condicional na forma de um IF-THEN-ELSE está disponível para testar o conteúdo de um ou dois registradores e "ramificar / pular" a máquina de estado finito para fora da sequência de instruções padrão.

Modelo base 1 : O modelo mais próximo da visualização de Minsky (1961) e de Lambek (1961):

  • {Aumenta o conteúdo do registrador r, DECrime o conteúdo do registrador r, IF o conteúdo do registrador r é Zero ENTÃO pula para a instrução I z ELSE continua para a próxima instrução}:
Instrução Mnemônico Ação no (s) registro (s) "r" Ação no registro de instruções da máquina de estado finito, IR
Incremento INC (r) [r] + 1 → r [IR] + 1 → IR
DECremento DEC (r) [r] - 1 → r [IR] + 1 → IR
Jump if Zero JZ (r, z) Nenhum SE [r] = 0 ENTÃO z → IR ELSE [IR] + 1 → IR
Halt H Nenhum [IR] → IR

Modelo básico 2 : O modelo "sucessor" (nomeado após a função sucessora dos axiomas de Peano ):

  • {Aumentar o conteúdo do registrador r, CLeaR o conteúdo do registrador r, IF conteúdo do registrador r j Igual ao conteúdo do registrador r k ENTÃO Saltar para a instrução I z ELSE ir para a próxima instrução}
Instrução Mnemônico Ação no (s) registro (s) "r" Ação no registro de instruções da máquina de estado finito, IR
Claro CLR (r) 0 → r [IR] + 1 → IR
Incremento INC (r) [r] + 1 → r [IR] + 1 → IR
Saltar se for igual JE (r1, r2, z) Nenhum SE [r1] = [r2] ENTÃO z → IR ELSE [IR] + 1 → IR
Halt H Nenhum [IR] → IR

Modelo básico 3 : usado por Elgot-Robinson (1964) em sua investigação de RASPs limitados e ilimitados - o modelo "sucessor" com COPY no lugar de CLEAR:

  • {Aumente o conteúdo do registrador r, COPIE o conteúdo do registrador r j para o registrador r k , IF conteúdo do registrador r j é igual ao conteúdo do registrador r k e então pule para a instrução I z ELSE vá para a próxima instrução}
Instrução Mnemônico Ação no (s) registro (s) "r" Ação no registro de instruções da máquina de estado finito, IR
CÓPIA DE CÓPIA (r1, r2) [r1] → r2 [IR] + 1 → IR
Incremento INC (r) [r] + 1 → r [IR] + 1 → IR
Saltar se for igual JE (r1, r2, z) Nenhum SE [r1] = [r2] ENTÃO z → IR ELSE [IR] + 1 → IR
Halt H Nenhum [IR] → IR

Criação de "instruções de conveniência" a partir dos conjuntos básicos

Os três conjuntos de base 1, 2 ou 3 acima são equivalentes no sentido de que se pode criar as instruções de um conjunto usando as instruções de outro conjunto (um exercício interessante: uma dica de Minsky (1967) - declarar um registro reservado, por exemplo, chamada é "0" (ou Z para "zero" ou E para "apagar") para conter o número 0). A escolha do modelo dependerá de qual o autor achar mais fácil de usar em uma demonstração, ou uma prova, etc.

Além disso, a partir dos conjuntos de base 1, 2 ou 3, podemos criar qualquer uma das funções recursivas primitivas (cf Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Como ampliar a rede para capturar as funções recursivas mu totais e parciais será discutido no contexto do endereçamento indireto). No entanto, construir as funções recursivas primitivas é difícil porque os conjuntos de instruções são tão ... primitivos (minúsculos). Uma solução é expandir um determinado conjunto com "instruções de conveniência" de outro conjunto:

Estas não serão sub-rotinas no sentido convencional, mas sim blocos de instruções criadas a partir do conjunto base e dado um mnemônico. Em um sentido formal, para usar esses blocos, precisamos (i) "expandi-los" em seus equivalentes de instrução base - eles exigirão o uso de registradores temporários ou "auxiliares", de modo que o modelo deve levar isso em consideração, ou ( ii) projetar nossas máquinas / modelos com as instruções 'integradas'.
Exemplo: Conjunto de bases 1. Para criar CLR (r), use o bloco de instruções para fazer a contagem regressiva do registrador r até zero. Observe o uso da dica mencionada acima:
  • CLR (r) = equiv
  • loop : JZ (r, sair )
  • DEC (r)
  • JZ (0, loop )
  • saída : etc.

Novamente, tudo isso é apenas por conveniência; nada disso aumenta o poder intrínseco do modelo.

Por exemplo: o conjunto mais expandido incluiria cada instrução única dos três conjuntos, mais o salto incondicional J (z), ou seja:

  • {CLR (r), DEC (r), INC (r), CPY (r s , r d ), JZ (r, z), JE (r j , r k , z), J (z)}

A maioria dos autores escolhe um ou outro dos saltos condicionais, por exemplo, Shepherdson-Sturgis (1963) usa o conjunto acima menos JE (para ser perfeitamente preciso, eles usam JNZ - Jump if Not Zero no lugar de JZ; outra instrução de conveniência possível).

A operação "indireta"

Exemplo de endereçamento indireto

Em nosso dia a dia, a noção de uma "operação indireta" não é incomum.

Exemplo: uma caça ao tesouro.
No local "Tom _ & _ Becky's_cave_in_pirate_chest" estará onde podemos encontrar um mapa que nos direciona para "o tesouro":
(1) Vamos para o local "Tom _ & _ Becky's_cave ..." e cavamos até encontrar uma caixa de madeira
(2) Dentro da caixa está um mapa para a localização do tesouro: "under_Thatcher's_front_porch"
(3) Vamos para o local "under_Thatcher's_front_porch", retire o concreto com uma britadeira e descobrimos "o tesouro": um saco de maçanetas enferrujadas.

A indireção especifica um local identificado como o baú do pirata em "Tom _ & _ Becky's_cave ..." que atua como um ponteiro para qualquer outro local (incluindo ele mesmo): seu conteúdo (o mapa do tesouro) fornece o "endereço" do local de destino "sob_Thatcher 's_front_porch "onde a ação real está ocorrendo.

Por que a necessidade de uma operação indireta: dois grandes problemas com o modelo contra-máquina

A seguir, deve-se lembrar que esses modelos são modelos abstratos com duas diferenças fundamentais de qualquer coisa fisicamente real: números ilimitados de registros, cada um com capacidades ilimitadas. O problema aparece de forma mais dramática quando se tenta usar um modelo de contra-máquina para construir um RASP equivalente a Turing e, assim, calcular qualquer função recursiva mu parcial :

  • Melzak (1961) adicionou indireção ao seu modelo "buraco e seixo" para que seu modelo pudesse se modificar com um "goto calculado" e fornece dois exemplos de seu uso ("Representação decimal na escala de d" e "Classificando por magnitude ", se eles são usados ​​em sua prova de que o modelo é equivalente a Turing não está claro, pois" o programa em si é deixado para o leitor como um exercício "(p. 292)). Minsky (1961,1967) foi capaz de demonstrar que, com a codificação de número de Gödel adequada (mas difícil de usar) , o modelo de registro não precisava de direção indireta para ser equivalente a Turing; mas precisava de pelo menos um registro ilimitado. Conforme observado abaixo, Minsky (1967) sugere o problema de um RASP, mas não oferece uma solução. Elgot e Robinson (1964) provaram que seu modelo RASP P 0  - não tem capacidade indireta - não pode computar todas as "funções sequenciais recursivas" (aquelas que têm parâmetros de comprimento arbitrário) se não tiver a capacidade de modificar suas próprias instruções, mas pode via números de Gödel, se isso acontecer (p. 395-397; em particular a figura 2 e nota de rodapé p. 395). Por outro lado, seu modelo RASP P ' 0 equipado com um "registrador de índice" (endereçamento indireto) pode computar todas as "funções sequenciais recursivas parciais" (as funções recursivas mu) (p. 397-398).
Cook e Reckhow (1973) dizem de forma mais sucinta:
As instruções indiretas são necessárias para que um programa fixo acesse um número ilimitado de registros conforme as entradas variam. ”(P. 73)
  • Capacidades ilimitadas de registradores versus capacidades limitadas de instruções de máquina de estado : A chamada parte de estado finito da máquina deve ser - pela definição normal de algoritmo - muito finita tanto no número de "estados" (instruções) quanto no tamanhos das instruções (sua capacidade de conter símbolos / sinais). Então, como uma máquina de estado move uma constante arbitrariamente grande diretamente para um registrador, por exemplo, MOVE (k, r) (Move a constante k para o registrador r)? Se constantes grandes são necessárias, elas devem começar nos próprios registradores ou ser criadas pela máquina de estado usando um número finito de instruções, por exemplo, multiplique e adicione sub-rotinas usando INC e DEC (mas não um número quase infinito destes!).
Às vezes, a constante k será criada pelo uso de CLR (r) seguido por INC (r) repetido k vezes - por exemplo, para colocar a constante k = 3 no registrador r, ou seja, 3 → r, então no final da instrução [r ] = 3: CLR (r), INC (r), INC (r), INC (r). Esse truque é mencionado por Kleene (1952) p. 223. O problema surge quando o número a ser criado esgota o número de instruções disponíveis para a máquina de estados finitos ; há sempre uma constante maior do que o número de instruções disponíveis para a máquina de estados finitos .
  • Números ilimitados de registros versus instruções de máquina de estado limitada : Isso é mais grave do que o primeiro problema. Em particular, esse problema surge quando tentamos construir um chamado RASP, uma "máquina universal" (veja mais em Máquina de Turing Universal ) que usa sua máquina de estado finito para interpretar um "programa de instruções" localizado em seus registradores - ou seja, estamos construindo o que hoje é chamado de computador com a arquitetura de von Neumann .
Observe que a máquina de estado finito da máquina de contagem deve chamar um registro explicitamente (diretamente) por seu nome / número: INC (65.356) chama o número de registro "65.365" explicitamente . Se o número de registros exceder a capacidade da máquina de estado finito de endereçá-los, os registros fora dos limites ficarão inacessíveis. Por exemplo, se a máquina de estados finitos só pode atingir 65.536 = 2 16 registradores, como ela pode atingir 65.537?

Então, como é que nos dirigimos a um registo para além dos limites da máquina de estado finito? Uma abordagem seria modificar as instruções do programa (aquelas armazenadas nos registradores) para que contivessem mais de um comando. Mas isso também pode ser exaurido, a menos que uma instrução seja de tamanho (potencialmente) ilimitado. Então por que não usar apenas uma "über-instrução" - um número realmente muito grande - que contém todas as instruções do programa codificadas nele! É assim que Minsky resolve o problema, mas a numeração de Gödel que ele usa representa um grande inconveniente para o modelo, e o resultado não é nada parecido com a nossa noção intuitiva de um "computador com programa armazenado".

Elgot e Robinson (1964) chegaram a uma conclusão semelhante com respeito a um RASP que é "finitamente determinado". Na verdade, ele pode acessar um número ilimitado de registros (por exemplo, para buscar instruções deles), mas apenas se o RASP permitir a "auto-modificação" de suas instruções de programa e tiver codificado seus "dados" em um número de Gödel (Fig. 2 p. 396 )

No contexto de um modelo mais semelhante ao de um computador, usando sua instrução RPT (repetir), Minsky (1967) nos atormenta com uma solução para o problema (cf p. 214, p. 259), mas não oferece uma resolução firme. Ele afirma:

"Em geral, uma operação RPT não poderia ser uma instrução na parte de estado finito da máquina ... isso pode esgotar qualquer quantidade particular de armazenamento permitida na parte finita do computador [sic, seu nome para seus modelos de RAM]. As operações RPT requerem registros próprios infinitos. " (p. 214).

Ele nos oferece um RPT limitado que junto com CLR (r) e INC (r) pode computar qualquer função recursiva primitiva , e ele oferece o RPT ilimitado citado acima que desempenha o papel de operador µ; ele junto com CLR (r) e INC (r) pode computar as funções recursivas mu. Mas ele não discute "indireção" ou o modelo de RAM em si.

A partir das referências em Hartmanis (1971), parece que Cook (em suas notas de aula enquanto estava na UC Berkeley, 1970) consolidou a noção de endereçamento indireto. Isso fica mais claro no artigo de Cook e Reckhow (1973) - Cook é o orientador da tese de mestrado de Reckhow. O modelo de Hartmanis - bastante semelhante ao modelo de Melzak (1961) - usa adições e subtrações de dois e três registros e duas cópias de parâmetros; O modelo de Cook e Reckhow reduz o número de parâmetros (registros chamados nas instruções do programa) a um chamado pelo uso de um acumulador "AC".

A solução em poucas palavras: Projete nossa máquina / modelo com indireção ilimitada  - forneça um registro de "endereço" ilimitado que pode nomear (chamar) qualquer registro, não importa quantos sejam. Para que isso funcione, em geral, o registrador ilimitado requer uma capacidade para ser limpo e então incrementado (e, possivelmente, decrementado) por um loop potencialmente infinito. Nesse sentido, a solução representa o operador μ ilimitado que pode, se necessário, caçar ad infinitim ao longo da string ilimitada de registradores até encontrar o que está procurando. O registrador de ponteiro é exatamente como qualquer outro registrador com uma exceção: sob as circunstâncias chamadas "endereçamento indireto" ele fornece seu conteúdo, ao invés do operando de endereço na TABELA da máquina de estado, para ser o endereço do registrador de destino (incluindo possivelmente ele mesmo !).

Indireção limitada e as funções recursivas primitivas

Se evitarmos a abordagem de Minsky de um número de monstro em um registrador, e especificarmos que nosso modelo de máquina será "como um computador", teremos que enfrentar este problema de indireção se quisermos calcular as funções recursivas (também chamadas de μ-recursivas funções ) - variedades totais e parciais.

Nosso modelo de contra-máquina mais simples pode fazer uma forma "limitada" de indireção - e assim calcular a subclasse de funções recursivas primitivas  - usando um "operador" recursivo primitivo chamado "definição por casos" (definido em Kleene (1952) p 229 e Boolos-Burgess-Jeffrey p. 74). Essa "via indireta limitada" é um assunto trabalhoso e tedioso. "Definição por casos" requer que a máquina determine / distinga o conteúdo do registrador de ponteiro tentando, vez após vez até o sucesso, comparar este conteúdo com um número / nome que o operador de caso declara explicitamente . Assim, a definição por casos começa, por exemplo, do endereço de limite inferior e continua ad nauseam em direção ao endereço de limite superior tentando fazer uma correspondência:

O número no registro N é igual a 0? Se não, é igual a 1? 2? 3? ... 65364? Se não, estamos no último número 65365 e é melhor que seja este, senão temos um problema!

A indireção "limitada" não nos permite calcular as funções recursivas parciais - para aqueles que precisamos de indireção ilimitada, também conhecido como o operador µ .

Suponha que pudéssemos continuar até o número 65.367 e, de fato, esse registro tinha o que estávamos procurando. Então poderíamos ter concluído nosso cálculo com sucesso! Mas suponha que 65367 não tivesse o que precisávamos. Até onde devemos continuar a ir?

Para ser equivalente a Turing, a máquina de contagem precisa usar o infeliz método de número de Minsky Gödel de registro único ou ser aumentada com a capacidade de explorar as extremidades de sua string de registro, ad infinitum, se necessário. (Uma falha em encontrar algo "lá fora" define o que significa para um algoritmo falhar em terminar; cf Kleene (1952) pp. 316ff Capítulo XII Funções Recursivas Parciais , em particular p. 323-325.) Veja mais sobre isso em o exemplo abaixo.

Indireção ilimitada e as funções recursivas parciais

Para indireção ilimitada , exigimos uma mudança de "hardware" em nosso modelo de máquina. Assim que fizermos essa mudança, o modelo não será mais uma máquina de balcão, mas sim uma máquina de acesso aleatório.

Agora, quando por exemplo INC é especificado, a instrução da máquina de estado finito terá que especificar de onde virá o endereço do registro de interesse. Este , onde pode ser (i) as instruções do máquina de estado que fornece um rótulo explícito , ou (ii) o ponteiro-registo cujo conteúdo é o endereço de interesse. Sempre que uma instrução especifica um endereço de registro, agora também precisará especificar um parâmetro adicional "i / d" - "indireto / direto". Em certo sentido, este novo parâmetro "i / d" é uma "chave" que vira uma maneira de obter o endereço direto conforme especificado na instrução ou a outra forma de obter o endereço indireto do registrador de ponteiro (qual registrador de ponteiro - em alguns modela cada registrador pode ser um registrador de ponteiro - é especificado pela instrução). Esta "escolha mutuamente exclusiva, mas exaustiva" é mais um exemplo de "definição por casos", e o equivalente aritmético mostrado no exemplo abaixo é derivado da definição em Kleene (1952) p. 229.

Exemplo: CPY ( fonte indireta , fonte r , destino direto , destino r )
Atribua um código para especificar o endereçamento direto como d = "0" e o endereçamento indireto como i = "1". Então, nossa máquina pode determinar o endereço de origem da seguinte maneira:
i * [r s ] + (1-i) * r s
Por exemplo, suponha que o conteúdo do registro 3 seja "5" (ou seja, [3] = 5) e o conteúdo do registro 4 seja "2" (ou seja, [4] = 2):
Exemplo: CPY (1, 3, 0, 4) = CPY (indireto, registro 3, direto, registro 4)
1 * [3] + 0 * 3 = [3] = endereço de registro de origem 5
0 * [4] + 1 * 4 = 4 = endereço de registro de destino 4
Exemplo: CPY (0, 3, 0, 4)
0 * [3] + 1 * 3 = 3 = endereço de registro de origem 3
0 * [4] + 1 * 4 = 4 = endereço de registro de destino 4
Exemplo: CPY (0, 3, 1, 4)
0 * [3] + 1 * 3 = 3 = endereço de registro de origem 3
1 * [4] + 0 * 4 = [4] = endereço de registro de destino 2

A instrução indireta COPY

Provavelmente, a mais útil das instruções adicionadas é COPY. De fato, Elgot-Robinson (1964) fornece seus modelos P 0 e P ' 0 com as instruções COPY, e Cook-Reckhow (1973) fornece seu modelo baseado em acumulador com apenas duas instruções indiretas - COPY para o acumulador indiretamente, COPY do acumulador indiretamente .

Uma infinidade de instruções : Como qualquer instrução agindo em um único registrador pode ser aumentada com seu "dual" indireto (incluindo saltos condicionais e incondicionais, cf o modelo Elgot-Robinson), a inclusão de instruções indiretas dobrará o número de parâmetro único / instruções de registro (por exemplo, INC (d, r), INC (i, r)). Pior, cada instrução de dois parâmetros / registros terá 4 variedades possíveis, por exemplo:

CPY (d, r s , d, r d ) = COPIAR diretamente do registrador de origem para o registrador de destino
CPY (i, r sp , d, r d ) = COPIAR para o registrador de destino indiretamente usando o endereço de origem a ser encontrado no registrador de ponteiro de fonte r sp .
CPY (d, r s , i, r dp ) = COPIAR o conteúdo do registrador de origem indiretamente no registrador usando o endereço de destino a ser encontrado no registrador de ponteiro de destino r dp .
CPY (i, r sp , i, r dp ) = COPY indiretamente o conteúdo do registrador de origem com endereço a ser encontrado no registrador de ponteiro de origem r sp , no registrador de destino com endereço a ser encontrado no registrador de ponteiro de destino r dp )

De maneira semelhante, cada instrução de três registradores que envolve dois registradores de origem r s1 r s2 e um registrador de destino r d resultará em 8 variedades, por exemplo, a adição:

[r s1 ] + [r s2 ] → r d

vai render:

  • ADICIONE (d, r s1 , d, r s2 , d, r d )
  • ADICIONE (i, r sp1 , d, r s2 , d, r d )
  • ADICIONE (d, r s1 , i, r sp2 , d, r d )
  • ADICIONE (i, r sp1 , i, r sp2 , d, r d )
  • ADICIONE (d, r s1 , d, r s2 , i, r dp )
  • ADICIONE (i, r sp1 , d, r s2 , i, r dp )
  • ADICIONE (d, r s1 , i, r sp2 , i, r dp )
  • ADICIONE (i, r sp1 , i, r sp2 , i, r dp )

Se designarmos um registro para ser o "acumulador" (veja abaixo) e colocarmos fortes restrições nas várias instruções permitidas, poderemos reduzir bastante a abundância de operações diretas e indiretas. No entanto, deve-se ter certeza de que o conjunto de instruções reduzido resultante é suficiente e devemos estar cientes de que a redução virá à custa de mais instruções por operação "significativa".

A noção de "acumulador A"

A convenção histórica dedica um registro ao acumulador, um "órgão aritmético" que literalmente acumula seu número durante uma sequência de operações aritméticas:

“A primeira parte do nosso órgão aritmético ... deve ser um órgão de armazenamento paralelo que pode receber um número e adicioná-lo ao que já está nele, que também é capaz de limpar seu conteúdo e pode armazenar o que ele contém. chame esse órgão de Acumulador . É bastante convencional em princípio nas máquinas de computação do passado e do presente dos mais variados tipos, por exemplo, multiplicadores de mesa, contadores IBM padrão, máquinas de relé mais modernas, o ENIAC "(negrito no original: Goldstine e von Neumann , 1946; p. 98 em Bell e Newell 1971).

No entanto, o acumulador vem às custas de mais instruções por "operação" aritmética, em particular no que diz respeito ao que é chamado de instruções 'ler-modificar-gravar', como "Aumentar indiretamente o conteúdo do registro apontado pelo registrador r2". "A" designa o registro "acumulador" A:

Rótulo Instrução UMA r2 r378.426 Descrição
. . . 378.426 17
INCi (r2): CPY (i, r2, d, A) 17 378.426 17 O conteúdo de r2 aponta para r378.426 com conteúdo "17": copie para A
INC (A) 18 378.426 17 Conteúdo de incimento de A
CPY (d, A, i, r2) 18 378.426 18 Conteúdo de r2 aponta para r378.426: copie o conteúdo de A para r378.426

Se ficarmos com um nome específico para o acumulador, por exemplo, "A", podemos implicar o acumulador nas instruções, por exemplo,

INC (A) = INCA

No entanto, quando escrevemos as instruções CPY sem o acumulador chamado, as instruções são ambíguas ou devem ter parâmetros vazios:

CPY (d, r2, d, A) = CPY (d, r2,,)
CPY (d, A, d, r2) = CPY (,, d, r2)

Historicamente, o que aconteceu é que essas duas instruções CPY receberam nomes distintos; no entanto, nenhuma convenção existe. A tradição (por exemplo, o computador MIX imaginário de Knuth (1973) ) usa dois nomes chamados LOAD e STORE. Aqui estamos adicionando o parâmetro "i / d":

LDA (d / i, r s ) = def CPY (d / i, r s , d, A)
STA (d / i, r d ) = def CPY (d, A, d / i, r d )

O modelo baseado em acumulador típico terá todas as suas operações aritméticas e constantes de duas variáveis ​​(por exemplo, ADD (A, r), SUB (A, r)) usar (i) o conteúdo do acumulador, juntamente com (ii) o conteúdo de um registro especificado . As operações de uma variável (por exemplo, INC (A), DEC (A) e CLR (A)) requerem apenas o acumulador. Ambos os tipos de instrução depositam o resultado (por exemplo, soma, diferença, produto, quociente ou resto) no acumulador.

Exemplo: INCA = [A] +1 → A
Exemplo: ADDA (r s ) = [A] + [r s ] → A
Exemplo: MULA (r s ) = [A] * [r s ] → A

Se assim escolhermos, podemos abreviar os mnemônicos porque pelo menos um registrador de origem e o registrador de destino é sempre o acumulador A. Assim, temos:

{LDA (i / d, r s ), STA (i / d, r d ), CLRA, INCA, DECA, ADDA (r s ), SUBA (r s ), MULA (r s ), DIVA (r s ) , etc.)

A noção de registro de endereço indireto "N"

Se nosso modelo tiver um acumulador ilimitado, podemos ligar todos os outros registradores? Não até que forneçamos pelo menos um registro ilimitado do qual derivamos nossos endereços indiretos.

A abordagem minimalista é usar a si mesmo (Schönhage faz isso).

Outra abordagem (Schönhage faz isso também) é declarar um registro específico como o "registro de endereço indireto" e limitar a indireção em relação a esse registro (o modelo RAM0 de Schonhage usa registros A e N para instruções indiretas e diretas). Novamente, nosso novo registro não tem um nome convencional - talvez "N" de "iNdex", ou "iNdirect" ou "Número do endereço".

Para máxima flexibilidade, como fizemos para o acumulador A - consideraremos N apenas outro registro sujeito a incremento, decremento, limpeza, teste, cópia direta, etc. Novamente, podemos reduzir a instrução para um único parâmetro que fornece direção e indireção, por exemplo.

LDAN (i / d) = CPY (i / d, N, d, A); Acumulador LoaD via registro iNdirection
STAN (i / d) = CPY (d, A, i / d, N). Acumulador de armazenamento via registro iNdirection

Por que essa abordagem é tão interessante? Pelo menos dois motivos:

(1) Um conjunto de instruções sem parâmetros:

Schönhage faz isso para produzir seu conjunto de instruções RAM0. Consulte a seção abaixo.

(2) Reduzir uma RAM para uma máquina de Post-Turing:

Posando como minimalistas, reduzimos todos os registros, exceto o acumulador A e o registro de indireção N, por exemplo, r = {r0, r1, r2, ...} a uma sequência ilimitada de pombos de capacidade (muito) limitada. Eles não farão nada além de conter números (muito) limitados, por exemplo, um bit solitário com valor {0, 1}. Da mesma forma, reduzimos o acumulador a um único bit. Restringimos qualquer aritmética aos registradores {A, N}, usamos operações indiretas para puxar o conteúdo dos registradores para o acumulador e escrevemos 0 ou 1 do acumulador para um registrador:

{LDA (i, N), STA (i, N), CLR (A / N), INC (A / N), DEC (N), JZ (A / N, I z ), JZ (I z ), H}

Impulsionamos mais e eliminamos A completamente pelo uso de dois registradores "constantes" chamados "ERASE" e "PRINT": [ERASE] = 0, [PRINT] = 1.

{CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I z ), JZ ( I z ), H}

Renomeie as instruções COPY e chame INC (N) = RIGHT, DEC (N) = LEFT e temos as mesmas instruções da máquina de Post-Turing, mais um CLRN extra:

{APAGAR, IMPRIMIR, CLRN, DIREITA, ESQUERDA, JZ (i, N, I z ), JZ (I z ), H}

Equivalência de Turing da RAM com indireção

Na seção acima, mostramos informalmente que uma RAM com capacidade de indireção ilimitada produz uma máquina de Post-Turing . A máquina de Post-Turing é equivalente a Turing, então mostramos que a RAM indireta é equivalente a Turing.

Damos aqui uma demonstração um pouco mais formal. Comece projetando nosso modelo com três registros reservados "E", "P" e "N", mais um conjunto ilimitado de registros 1, 2, ..., n à direita. Os registros 1, 2, ..., n serão considerados "os quadrados da fita". Registre "N" pontos para "o quadrado escaneado" que "a cabeça" está observando no momento. A "cabeça" pode ser considerada como estando no salto condicional - observe que ela usa endereçamento indireto (cf Elgot-Robinson p. 398). À medida que diminuímos ou incrementamos "N", a cabeça (aparente) "se moverá para a esquerda" ou "direita" ao longo dos quadrados. Iremos mover o conteúdo de "E" = 0 ou "P" = 1 para o "quadrado digitalizado" como apontado por N, usando o CPY indireto.

O fato de nossa fita ter a extremidade esquerda apresenta-nos um pequeno problema: sempre que LEFT ocorrer, nossas instruções terão que testar para determinar se o conteúdo de "N" é zero ou não; em caso afirmativo, devemos deixar sua contagem em "0" (esta é nossa escolha como projetistas - por exemplo, podemos ter a máquina / modelo "disparar um evento" de nossa escolha).

Conjunto de instruções 1 (aumentado): {INC (N), DEC (N), CLR (N), CPY (d, r s , i, N), JZ (i, r, z), HALT}

A tabela a seguir define as instruções Post-Turing em termos de suas instruções equivalentes de RAM e dá um exemplo de seu funcionamento. A localização (aparente) da cabeça ao longo da fita dos registros r0-r5. . . é mostrado sombreado:

Mnemônico rótulo: E P N r0 r1 r2 r3 r4 r5 etc. Ação nos registros Ação em máquina de estado finito Registro de Instrução IR
começar: 0 1 3 1 0
R direito: INC (N) 0 1 4 1 0 [N] +1 → N [IR] +1 → IR
P imprimir: CPY (d, P, i, N) 0 1 4 1 1 [P] = 1 → [N] = r4 [IR] +1 → IR
E apagar: CPY (d, E, i, N) 0 1 4 1 0 [E] = 0 → [N] = r4 [IR] +1 → IR
eu deixou: JZ (i, N, final) 0 1 4 1 0 Nenhum SE N = r4] = 0 ENTÃO "fim" → IR else [IR] +1 → IR
DEC (N) 0 1 3 1 0 [N] -1 → N
J0 (parada) jump_if_blank: JZ (i, N, final) 0 1 3 1 0 Nenhum SE N = r3] = 0 ENTÃO "fim" → IR else [IR] +1 → IR
J1 (parada) jump_if_mark: JZ (i, N, parada) 0 1 3 1 0 N = r3] → A SE N = r3] = 0 ENTÃO "fim" → IR else [IR] +1 → IR
fim . . . etc. 0 1 3 1 0
parar: H 0 1 3 1 0 Nenhum [IR] +1 → IR

Exemplo: indireção limitada produz uma máquina que não é equivalente a Turing

Ao longo desta demonstração, devemos ter em mente que as instruções na TABELA da máquina de estados finitos são limitadas , ou seja, finitas :

"Além de ser meramente um conjunto finito de regras que fornece uma sequência de operações para resolver um tipo específico de problema, um algoritmo tem cinco características importantes [Finiteness, Definiteness, Input, Output, Effectiveness]" (itálico adicionado, Knuth p. 4 -7).
A dificuldade surge porque os registradores têm "nomes" (números) explícitos e nossa máquina deve chamá-los pelo nome para "acessá-los".

Vamos construir o CPY indireto (i, q, d, φ) com o operador CASE. O endereço do registro de destino será especificado pelo conteúdo do registro "q"; uma vez que o operador CASE tenha determinado qual é este número, o CPY irá depositar diretamente o conteúdo do registro com aquele número no registro "φ". Precisaremos de um registrador adicional que chamaremos de "y" - ele serve como um contador ascendente.

Portanto, o que se segue é na verdade uma demonstração construtiva ou prova de que podemos simular o CPY indireto (i, q, d, φ) sem uma mudança de design de "hardware" em nossa máquina / modelo de contador. No entanto, observe que, como este CPY indireto é "limitado" pelo tamanho / extensão da máquina de estado finito, um RASP usando este CPY indireto pode calcular apenas as funções recursivas primitivas , não o conjunto completo de funções recursivas mu .

O "operador" CASE é descrito em Kleene (1952) (p. 229) e em Boolos-Burgess-Jeffrey (2002) (p. 74); os últimos autores enfatizam sua utilidade. A definição a seguir é por Kleene, mas modificada para refletir a construção familiar "IF-THEN-ELSE".

O operador CASE "retorna" um número natural em φ dependendo de qual "caso" é satisfeito, começando com "case_0" e passando sucessivamente por "case_last"; se nenhum caso for satisfeito, então o número chamado "default" (também conhecido como "woops") é retornado em φ (aqui x designa alguma seleção de parâmetros, por exemplo, registrador qe a string r0, ... rlast)):

Definição por casos φ ( x , y):

  • case_0: SE Q 0 ( x , y) é verdadeiro ENTÃO φ 0 ( x , y) ELSE
  • case_1: SE Q 1 ( x , y) for verdadeiro ENTÃO φ 1 ( x , y) ELSE
  • cases_2 a case_next_to_last: etc. . . . . . . . OUTRO
  • case_last: SE Q último ( x , y) for verdadeiro ENTÃO φ último ( x , y) ELSE
  • padrão: faça φ padrão ( x , y)

Kleene exige que os "predicados" Q n que fazem o teste sejam todos mutuamente exclusivos - "predicados" são funções que produzem apenas {verdadeiro, falso} para a saída; Boolos-Burgess-Jeffrey acrescenta a exigência de que os casos sejam "exaustivos".

Começamos com um número no registro q que representa o endereço do registro de destino. Mas qual é esse número? Os "predicados" irão testá-lo para descobrir, uma tentativa após a outra: JE (q, y, z) seguido por INC (y). Uma vez que o número é identificado explicitamente, o operador CASE copia direta / explicitamente o conteúdo deste registro para φ:

Definição por casos CPY (i, q, d, φ) = def φ (q, r0, ..., rlast, y) =
  • case_0: IF CLR (y), [q] - [y] = 0 THEN CPY (r0, φ), J (sair) ELSE
  • case_1: IF INC (y), [q] = [y] = 1 THEN CPY (r1, φ), J (sair) ELSE
  • case_2 até o caso n: IF. . . ENTÃO . . . OUTRO
  • case_n: IF INC (y), [q] = [y] = n THEN CPY (rn, φ), J (sair) ELSE
  • case_n + 1 a case_last: IF. . . ENTÃO . . . OUTRO
  • case_last: IF INC (y), [q] = [y] = "último" THEN CPY (rlast, φ), J (sair) ELSE
  • padrão: woops

Case_0 (a etapa base da recursão em y) tem a seguinte aparência:

  • case_0 :
  • CLR (y); definir o registro y = 0
  • JE (q, y, _φ0 )
  • J ( case_1 )
  • _φ0: CPY (r0, φ)
  • J ( sair )
  • case_1: etc.

Case_n (a etapa de indução) se parece com isso; lembre-se, cada instância de "n", "n + 1", ..., "último" deve ser um número natural explícito:

  • case_n :
  • INC (y)
  • JE (q, y, _φn )
  • J ( case_n + 1 )
  • _φn: CPY (rn, φ)
  • J ( sair )
  • case__n + 1: etc.

Case_last interrompe a indução e limita o operador CASE (e, portanto, limita o operador de "cópia indireta"):

  • case_last :
  • INC (y)
  • JE (q, y, _φúltimo )
  • J ( woops )
  • _φúltimo : CPY (rúltimo, φ)
  • J ( sair )
  • woops: como lidamos com uma tentativa fora dos limites?
  • saída: etc.

Se o CASE pudesse continuar ad infinitum, seria o operador mu . Mas não pode - o "registro de estado" de sua máquina de estado finito atingiu sua contagem máxima (por exemplo, 65365 = 11111111,11111111 2 ) ou sua tabela ficou sem instruções; afinal, é uma máquina finita .

Exemplos de modelos

Modelo de registro para registro ("leitura-modificação-gravação") de Cook e Reckhow (1973)

O modelo Cook e Rechkow comumente encontrado é um pouco como o modelo Malzek de registrador ternário (escrito com mnemônicos Knuth - as instruções originais não tinham mnemônicos, exceto TRA, Read, Print).

  • LOAD ( C, rd ) ; C → rd, C é qualquer número inteiro
Exemplo: LOAD ( 0, 5 )apagará o registro 5.
  • ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, os registros podem ser iguais ou diferentes;
Exemplo: ADD ( A, A, A )dobrará o conteúdo do registro A.
  • SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, os registros podem ser iguais ou diferentes:
Exemplo: SUB ( 3, 3, 3 )apagará o registro 3.
  • COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Copia indiretamente o conteúdo do registrador de origem apontado pelo registrador de ponteiro r p no registrador de destino.
  • COPY ( d, rs, i, rp ) ; [rs] → [rp]. Copie o conteúdo do registrador de origem r s para o registrador de destino apontado pelo registrador de ponteiro r p .
  • JNZ ( r, Iz ) ;Salto condicional se [r] for positivo; ou seja, IF [r]> 0 THEN pule para a instrução z senão continue em sequência (Cook e Reckhow chamam isso: "Transferir o controle para a linha m se Xj> 0")
  • READ ( rd ) ;copie "a entrada" no registro de destino r d
  • PRINT ( rs ) ;copie o conteúdo do registrador de origem r s para "a saída".

RAM0 e RAM1 de Schönhage (1980)

Schönhage (1980) descreve um modelo atomizado muito primitivo escolhido para sua prova da equivalência de seu modelo de máquina ponteiro SMM :

"Para evitar qualquer endereçamento explícito, o RAM0 tem o acumulador com conteúdo z e um registro de endereço adicional com conteúdo atual n (inicialmente 0)" (p. 494)

Modelo RAM1 : Schönhage demonstra como sua construção pode ser usada para formar a forma mais comum e utilizável de RAM semelhante a um "sucessor" (usando os mnemônicos deste artigo):

  • LDA k ; k --> A , k é uma constante, um número explícito como "47"
  • LDA ( d, r ) ; [r] → A ; carregar diretamente A
  • LDA ( i, r ) ; [[r]] → A ; carregar indiretamente A
  • STA ( d, r ) ; [A] → r ; armazenar diretamente A
  • STA ( i, r ) ; [A] → [r] ; indiretamente armazenar A
  • JEA ( r, z ) ; IF [A] = [r] then Iz else continue
  • INCA ; [A] + 1 --> A

Modelo RAM0 : a máquina RAM0 de Schönhage tem 6 instruções indicadas por uma única letra (o 6º "C xxx" parece envolver 'pular o próximo parâmetro'. Schönhage designou o acumulador com "z", "N" com "n", etc. Em vez dos mnemônicos de Schönhage, usaremos os mnemônicos desenvolvidos acima.

  • (Z), CLRA: 0 → A
  • (A), INCA: [A] +1 → A
  • (N), CPYAN: [A] → N
  • (A), LDAA: [[A]] → A ; o conteúdo dos pontos A para registrar o endereço; colocar o conteúdo do registro em A
  • (S), STAN: [A] → [N] ; conteúdo de N pontos para registrar o endereço; colocar o conteúdo de A no registro apontado por N
  • (C), JAZ ( z ): [A] = 0 then go to Iz ; ambíguo em seu tratamento

A indireção vem (i) de CPYAN (copiar / transferir conteúdo A para N) trabalhando com store_A_via_N STAN, e de (ii) a instrução indireta peculiar LDAA ( [[A]] → [A] ).

Notas de rodapé

Finito vs ilimitado

O fato de definição de que qualquer tipo de máquina de contador sem um registro ilimitado - registro de "endereço" deve especificar um registro "r" pelo nome indica que o modelo requer que "r" seja finito , embora seja "ilimitado" no sentido de que o modelo não implica limite superior para o número de registros necessários para fazer seu (s) trabalho (s). Por exemplo, não exigimos r <83.617.563.821.029.283.746 nem r <2 ^ 1.000.001, etc.

Assim, nosso modelo pode "expandir" o número de registradores, se necessário para realizar um determinado cálculo. No entanto, este não significam que qualquer número que o modelo se expande para deve ser finito  - deve ser indexável com um número natural: ω não é uma opção .

Podemos escapar dessa restrição fornecendo um registro ilimitado para fornecer o endereço do registro que especifica um endereço indireto.

Veja também

links externos

Referências

Com algumas exceções, essas referências são as mesmas da máquina de registro .

    • Goldstine, Herman H. e von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study , Princeton. Reimpresso nas páginas 92–119 em Bell, C. Gordon e Newell, Allen (1971), Computer Structures: Readings and Examples , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 }.
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidade e Lógica: Quarta Edição , Cambridge University Press, Cambridge, Inglaterra. O texto original de Boolos-Jeffrey foi extensivamente revisado por Burgess: mais avançado do que um livro introdutório. O modelo da "máquina Abacus" é amplamente desenvolvido no Capítulo 5 Computabilidade do Abacus ; é um dos três modelos extensivamente tratados e comparados - a máquina de Turing (ainda na forma original de 4 tuplas de Boolos) e a recursão dos outros dois.
  • Arthur Burks , Herman Goldstine , John von Neumann (1946), Discussão preliminar do design lógico de um instrumento de computação eletrônico , reimpresso pp. 92ff em Gordon Bell e Allen Newell (1971), Estruturas de computador: leituras e exemplos , livro mcGraw-Hill Company, New York. ISBN  0-07-004357-4 .
  • Stephen A. Cook e Robert A. Reckhow (1973), Time-bounded random access machines , Journal of Computer Systems Science 7 (4): 354-375.
  • Martin Davis (1958), Computability & Unsolvability , McGraw-Hill Book Company, Inc. New York.
  • Calvin Elgot e Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Journal of the Association for Computing Machinery, Vol. 11, No. 4 (outubro, 1964), pp. 365-399.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232-245.
  • John Hopcroft , Jeffrey Ullman (1979). Introdução à Teoria dos Autômatos, Linguagens e Computação , 1ª ed., Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . Um livro difícil centrado em torno das questões de interpretação mecânica de "linguagens", NP-Completude, etc.
  • Stephen Kleene (1952), Introdução à Metamatemática , North-Holland Publishing Company, Amsterdã, Holanda. ISBN  0-7204-2103-9 .
  • Donald Knuth (1968), The Art of Computer Programming , Segunda Edição 1973, Addison-Wesley, Reading, Massachusetts. Cf páginas 462-463 onde ele define "um novo tipo de máquina abstrata ou 'autômato' que lida com estruturas interligadas."
  • Joachim Lambek (1961, recebido em 15 de junho de 1961), How to Program an Infinite Abacus , Mathematical Bulletin, vol. 4, não. 3. Setembro de 1961, páginas 295-302. Em seu Apêndice II, Lambek propõe uma "definição formal de 'programa'. Ele faz referência a Melzak (1961) e Kleene (1952), Introdução à Metamatemática .
  • ZA Melzak (1961, recebido em 15 de maio de 1961), An informal Arithmetical Approach to Computability and Computation , Canadian Mathematical Bulletin , vol. 4, não. 3. Setembro de 1961, páginas 279-293. Melzak não oferece referências, mas reconhece "o benefício das conversas com os Drs. R. Hamming, D. McIlroy e V. Vyssots da Bell telephone Laborators e com o Dr. H. Wang da Universidade de Oxford."
  • Marvin Minsky (1961). "Insolucionabilidade recursiva do problema de 'tag' de Post e outros tópicos da teoria das máquinas de Turing". Annals of Mathematics . The Annals of Mathematics, vol. 74, No. 3. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR  1970290 .
  • Marvin Minsky (1967). Computation: Finite and Infinite Machines (1ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc.Em particular, consulte o capítulo 11: Modelos semelhantes aos computadores digitais e o capítulo 14: Bases muito simples para computabilidade . No capítulo anterior, ele define "Máquinas de programa" e no capítulo posterior discute "Máquinas de programa universal com dois registros" e "... com um registro", etc.
  • John C. Shepherdson e HE Sturgis (1961) receberam em dezembro de 1961 Computability of Recursive Functions , Journal ofthe Association of Computing Machinery (JACM) 10: 217-255, 1963. Um artigo de referência extremamente valioso. Em seu Apêndice A, os autores citam 4 outros com referência a "Minimalidade de Instruções Usadas em 4.1: Comparação com Sistemas Similares".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, algoritmos do operador AP On , (Russo) Dok. Akad. Nauk 122 (1958), 967-970. Tradução para o inglês, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (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, agosto de 1980. Onde Schōnhage mostra a equivalência de seu SMM com o "sucessor RAM" (Random Access Machine), etc. resp. Storage Modification Machines , em Theoretical Computer Science (1979), pp. 36-37
  • Peter van Emde Boas , "Machine Models and Simulations", pp. 3-66, em: Jan van Leeuwen , ed. Manual de Ciência da Computação Teórica. Volume A: Algorithms and Complexity , The MIT PRESS / Elsevier, 1990. ISBN  0-444-88071-2 (volume A). QA 76.H279 1990. O tratamento de van Emde Boas dos SMMs aparece nas páginas 32-35. Este tratamento esclarece Schonhage 1980 - segue de perto, mas expande ligeiramente o tratamento de Schonhage. Ambas as referências podem ser necessárias para um entendimento eficaz.
  • Hao Wang (1957), A Variant to Turing's Theory of Computing Machines , JACM (Journal of the Association for Computing Machinery) 4; 63-92. Apresentado na reunião da Associação de 23 a 25 de junho de 1954.