Máquina de contador - Counter machine

Uma máquina contrária é uma máquina abstrata usada em uma lógica formal e na ciência da computação teórica para modelar a computação . É o mais primitivo dos quatro tipos de máquinas de registro . Uma máquina de contagem compreende um conjunto de um ou mais registros ilimitados , cada um dos quais pode conter um único inteiro não negativo e uma lista de (geralmente sequencial) aritmética e instruções de controle para a máquina seguir. A máquina de contagem é normalmente usada no processo de projeto de algoritmos paralelos em relação ao princípio de exclusão mútua. Quando usada dessa maneira, a máquina de contagem é usada para modelar os passos de tempo discretos de um sistema computacional em relação aos acessos à memória. Modelando cálculos em relação aos acessos à memória para cada respectiva etapa computacional, algoritmos paralelos podem ser projetados em tal matéria para evitar o intertravamento, a operação de gravação simultânea por dois (ou mais) threads no mesmo endereço de memória.

Recursos básicos

Para um determinado modelo de máquina de contador, o conjunto de instruções é minúsculo - de apenas uma a seis ou sete instruções. A maioria dos modelos contém algumas operações aritméticas e pelo menos uma operação condicional (se a condição for verdadeira, pule). Três modelos básicos , cada um usando três instruções, são extraídos da coleção a seguir. (As abreviações são arbitrárias.)

  • CLR (r): registro CLeaR r . (Defina r como zero.)
  • INC (r): Aumente o conteúdo do registro r .
  • DEC (r): Decrementa o conteúdo do registrador r .
  • CPY (r j , r k ): Copie o conteúdo do registrador r j para o registrador r k, deixando o conteúdo de r j intacto.
  • JZ (r, z): IF registrador r contém Zero THEN Salta para a instrução z ELSE continua em seqüência.
  • JE (r j , r k , z): SE o conteúdo do registrador r j é igual ao conteúdo do registrador r k THEN Salta para a instrução z ELSE continua em sequência.

Além disso, uma máquina geralmente tem uma instrução HALT, que para a máquina (normalmente depois que o resultado foi calculado).

Usando as instruções mencionadas acima, vários autores discutiram certas máquinas de contador:

  • conjunto 1: {INC (r), DEC (r), JZ (r, z)}, (Minsky (1961, 1967), Lambek (1961))
  • conjunto 2: {CLR (r), INC (r), JE (r j , r k , z)}, (Ershov (1958), Peter (1958) conforme interpretado por Shepherdson-Sturgis (1964); Minsky (1967) ; Schönhage (1980))
  • conjunto 3: {INC (r), CPY (r j , r k ), JE (r j , r k , z)}, (Elgot-Robinson (1964), Minsky (1967))

Os três modelos básicos da máquina de contagem têm o mesmo poder computacional, uma vez que as instruções de um modelo podem ser derivadas das de outro. Todos são equivalentes ao poder computacional das máquinas de Turing . Devido ao seu estilo de processamento unário, as máquinas de contagem são tipicamente exponencialmente mais lentas do que as máquinas de Turing comparáveis.

Nomes alternativos, modelos alternativos

Artigo principal: Modelo de contra-máquina

Os modelos de máquina de contagem têm vários nomes diferentes que podem ajudar a distingui-los por suas peculiaridades. A seguir, a instrução "JZDEC (r)" é uma instrução composta que testa se um registrador r está vazio; em caso afirmativo, pule para a instrução I z , senão, se não, DECremente o conteúdo de r:

  • Máquina de Shepherdson-Sturgis , porque esses autores declararam formalmente seu modelo em uma exposição facilmente acessível (1963). Usa o conjunto de instruções (1) aumentado com instruções de conveniência adicionais (JNZ é "Jump if Not Zero, usado no lugar de JZ):
    {INC (r), DEC (r), CLR (r), CPY (r j , r k ), JNZ (r, z), J (z)}
  • Máquina Minsky , porque Marvin Minsky (1961) formalizou o modelo. Normalmente usa o conjunto de instruções (1), mas a execução da instrução não é sequencial padrão, então o parâmetro adicional 'z' aparece para especificar a próxima instrução após INC e como alternativa em JZDEC:
    {INC (r, z), JZDEC (r, z verdadeiro , z falso )}
  • Máquina de programa , computador de programa , os nomes que Minsky (1967) deu ao modelo porque, como um computador, suas instruções procedem sequencialmente, a menos que um salto condicional seja bem-sucedido. Usa (geralmente) o conjunto de instruções (1), mas pode ser aumentado de forma semelhante ao modelo de Shepherson-Sturgis. JZDEC é frequentemente dividido:
    {INC (r), DEC (r), JZ (r, z verdadeiro )}
  • Máquina Abacus , o nome Lambek (1961) deu à sua simplificação do modelo Melzak (1961), e como Boolos-Burgess-Jeffrey (2002) o chama. Usa o conjunto de instruções (1), mas com um parâmetro adicional z para especificar a próxima instrução na maneira do modelo Minsky (1961);
    {INC (r, z), JZDEC (r, z verdadeiro , z falso )}
  • Máquina de Lambek , um nome alternativo que Boolos-Burgess-Jeffrey (2002) deu à máquina de ábaco. Usa o conjunto de instruções (1 reduzido) com um parâmetro adicional para especificar a próxima instrução:
    {INC (r, z), JZDEC (r, z verdadeiro , z falso )}
  • Máquina sucessora , porque usa a "operação sucessora" dos axiomas de Peano e se assemelha muito. Usado como base para o modelo de RAM sucessor . Usa o conjunto de instruções (2) por exemplo Schönhage como base para seus modelos RAM0 e RAM1 que levam ao seu modelo SMM de máquina de ponteiro , também discutido brevemente em van Emde Boas (1990):
    {CLR (r), INC (r), JE (r j , r k , z)}
  • Modelo Elgot-Robinson , usado para definir seu modelo RASP (1964). Este modelo requer um registro vazio no início (por exemplo, [r0] = 0). (Eles aumentaram o mesmo modelo com endereçamento indireto pelo uso de um registro adicional a ser usado como um registro de "índice".)
    {INC (r), CPY (r s , r d ), JE (r j , r k , z)}
  • Outras máquinas de contador : Minsky (1967) demonstra como construir os três modelos básicos (programa / Minsky / Lambek-ábaco, sucessor e Elgot-Robinson) a partir do superconjunto de instruções disponíveis descritas no parágrafo principal deste artigo. O modelo de Melzak (1961) é bastante diferente do anterior porque inclui 'adicionar' e 'subtrair' em vez de 'incremento' e 'decremento'. As provas de Minsky (1961,1967) de que um único registro será suficiente para a equivalência de Turing requerem as duas instruções {MULtiply k e DIV k} para codificar e decodificar o número de Gödel no registro que representa o cálculo. Minsky mostra que se dois ou mais registros estão disponíveis, então o INC, DEC etc. mais simples são adequados (mas o número de Gödel ainda é necessário para demonstrar a equivalência de Turing ; também demonstrado em Elgot-Robinson 1964).

Definição formal

Uma máquina de contador consiste em:

  1. Registros de valores inteiros ilimitados rotulados : um conjunto finito (ou infinito em alguns modelos) de registros r 0  ...  r n, cada um dos quais pode conter qualquer número inteiro não negativo (0, 1, 2, ... - ou seja, ilimitado ) Os registradores fazem sua própria aritmética; pode ou não haver um ou mais registradores especiais, por exemplo, "acumulador" (consulte Máquina de acesso aleatório para mais informações).
  2. Um registro de estado que armazena / identifica a instrução atual a ser executada. Este registro é finito e separado dos registros acima; assim, o modelo de máquina de contador é um exemplo da arquitetura Harvard
  3. Lista de instruções sequenciais rotuladas : Uma lista finita de instruções I 0  ...  I m . O armazenamento do programa (instruções da máquina de estado finito ) não está no mesmo "espaço" físico que os registradores. Normalmente, mas nem sempre, como os programas de computador, as instruções são listadas em ordem sequencial; a menos que um salto seja bem-sucedido, a seqüência padrão continua em ordem numérica. Cada uma das instruções na lista é de um conjunto (muito) pequeno, mas este conjunto não inclui indireção. Historicamente, a maioria dos modelos extraiu suas instruções deste conjunto:
{Incremento (r), Decremento (r), Limpar (r); Copiar (r j , r k ), salto condicional se o conteúdo de r = 0, salto condicional se r j = r k , salto incondicional, HALT}
Alguns modelos atomizaram ainda mais alguns dos itens acima em instruções sem parâmetro ou os combinaram em uma única instrução, como "Decremento" precedido por salto condicional se zero "JZ (r, z)". A atomização de instruções ou a inclusão de instruções de conveniência não causa nenhuma mudança no poder conceitual, pois qualquer programa em uma variante pode ser traduzido diretamente para a outra.
Conjuntos de instruções alternativos são discutidos no suplemento Modelos de máquina de registro .

Exemplo: COPIAR a contagem do registro # 2 ao # 3

Este exemplo mostra como criar três instruções mais úteis: limpar , pular incondicional e copiar .

Posteriormente, r s conterá sua contagem original (ao contrário de MOVE, que esvazia o registrador de origem, ou seja, zera).

O conjunto básico (1) é usado conforme definido aqui:

Instrução Efeito no registro "j" Efeito sobre o registro do contador de instruções ICR Resumo
INC (j) [j] +1 → j [IC] +1 → IC Aumentar o conteúdo do registro j; próxima instrução
DEC (j) [j] -1 → j [IC] +1 → IC Diminuir o conteúdo do registro j; próxima instrução
JZ (j, z) SE [j] = 0 ENTÃO I z → IC ELSE [IC] +1 → IC Se o conteúdo do registrador j = 0, então a instrução z, então a próxima instrução
HALT

Condições iniciais

Inicialmente, o registro # 2 contém "2". Os registros # 0, # 1 e # 3 estão vazios (contêm "0"). O registro # 0 permanece inalterado durante os cálculos porque é usado para o salto incondicional. O registro # 1 é um bloco de rascunho. O programa começa com a instrução 1.

Condições finais

O programa HALTs com o conteúdo do registro # 2 em sua contagem original e o conteúdo do registro # 3 igual ao conteúdo original do registro # 2, ou seja,

[2] = [3].

Descrição de alto nível do programa

O programa COPY (# 2, # 3) tem duas partes. Na primeira parte, o programa move o conteúdo do registro de origem # 2 para o bloco de rascunho # 1 e para o registro de destino # 3; assim, # 1 e # 3 serão cópias um do outro e da contagem original em # 2, mas # 2 é apagado no processo de diminuição para zero. Os saltos incondicionais J (z) são feitos por testes do registro # 0, que sempre contém o número 0:

[# 2] → # 3; [# 2] → # 1; 0 → # 2

Na segunda parte, o programa move (retorna, restaura) o conteúdo do bloco de notas nº 1 de volta para o nº 2, limpando o bloco de notas nº 1 no processo:

[# 1] → # 2; 0 → # 1

Programa

O programa, destacado em amarelo, é mostrado escrito da esquerda para a direita no canto superior direito.

Uma "execução" do programa é mostrada abaixo. O tempo corre pela página. As instruções estão em amarelo, os registros em azul. O programa é invertido 90 graus, com os números de instrução (endereços) na parte superior, os mnemônicos de instrução sob os endereços e os parâmetros de instrução sob os mnemônicos (um por célula):

1 2 3 4 5 6 7 8 9 10 ← Número da instrução (endereço)
JZ DEZ INC INC JZ JZ DEZ INC JZ H ← Instrução
2 2 3 1 0 1 1 2 0 ← Número de registro
6 1 10 6 ← Número da instrução de salto
Passo IC Inst # reg # J-addr reg0 reg1 reg2 reg3 reg4 IC
começar 0 0 2 0 0 1 mover [# 2] para # 1 e # 3:
1 1 JZ 2 6 0 0 2 0 0 1 → 2 JZ O salto falha: o registro # 2 contém 2
2 2 DEZ 2 0 0 0 2 → 1 0 0 2 → 3 DEZ Reduza o registro # 2 de 2 para 1
3 3 INC 3 0 0 0 1 0 → 1 0 3 → 4 INC Incrementar o registro # 3 de 0 para 1
4 4 INC 1 0 0 0 → 1 1 1 0 4 → 5 INC Incrementar o registro # 1 de 0 a 1
5 5 JZ 0 1 0 1 1 1 0 5 → 1 JZ U-Jump: registro # 0 está vazio
6 1 JZ 2 6 0 1 1 1 0 1 → 2 JZ O salto falha: o registro # 2 contém 1
7 2 DEZ 2 0 0 1 1 → 0 1 0 2 → 3 DEZ Diminuir o registro # 2 de 1 para 0
8 3 INC 3 0 0 1 0 1 → 2 0 3 → 4 INC Incrementar o registro # 3 de 1 para 2
9 4 INC 1 0 0 1 → 2 0 2 0 4 → 5 INC Incrementar o registro # 1 de 1 para 2
10 5 JZ 0 1 0 2 0 2 0 5 → 1 JZ U-Jump: registro # 0 está vazio
11 1 JZ 2 6 0 2 0 2 0 1 → 6 JZ Jump!: Registro # 2 está vazio
mova [1] para 2:
12 6 JZ 1 10 0 2 0 2 0 6 → 7 JZ O salto falha: o registro # 1 contém 2
13 7 DEZ 1 0 0 2 → 1 0 2 0 7 → 8 DEZ Diminuir o registro # 1 de 2 para 1
14 8 INC 2 0 0 1 0 → 1 2 0 8 → 9 INC Incrementar o registro # 2 de 0 a 1
15 9 JZ 0 6 0 1 1 2 0 9 → 6 JZ U-Jump: registro # 0 está vazio
16 6 JZ 1 10 0 1 1 2 0 6 → 7 JZ O salto falha: o registro # 1 contém 1
17 7 DEZ 1 0 0 1 → 0 1 2 0 7 → 8 DEZ Diminuir o registro # 1 de 1 para 0
18 8 INC 2 0 0 0 1 → 2 2 0 8 → 9 INC Incrementar o registro # 2 de 1 para 2
19 9 JZ 0 6 0 0 2 2 0 9 → 6 JZ U-Jump: registro # 0 está vazio
20 6 JZ 1 10 0 0 2 2 0 6 → 10 JZ Jump!: Registro # 1 está vazio
21 10 H 0 0 0 0 2 2 0 10 → 10 H HALT

As funções recursivas parciais: construção de "instruções de conveniência" usando recursão

O exemplo acima demonstra como as primeiras instruções básicas {INC, DEC, JZ} podem criar mais três instruções - salto incondicional J, CLR, CPY. Em certo sentido, o CPY usou CLR e J mais o conjunto de base. Se o registro # 3 tivesse conteúdo inicialmente, a soma dos conteúdos de # 2 e # 3 teria terminado no # 3. Portanto, para ser totalmente preciso, o programa CPY deve ter precedido seus movimentos com CLR (1) e CLR (3).

No entanto, vemos que ADD teria sido possível, facilmente. E, de fato, o que segue é um resumo de como as funções recursivas primitivas como ADD, MULtiply e EXPonent podem ocorrer (ver Boolos-Burgess-Jeffrey (2002) p. 45-51).

  • Conjunto de instruções iniciais: {DEC, INC, JZ, H}
  • Defina o "Salto J (z)" incondicional em termos de JZ (r0, z) dado que r0 contém 0.
{J, DEC, INC, JZ, H}
  • Defina "CLeaR (r) nos termos acima:
{CLR, J, DEC, INC, JZ, H}
  • Defina "CoPY (r j , r k )" enquanto preserva o conteúdo de r j nos termos do acima:
{CPY, CLR, J, DEC, INC, JZ, H}
O texto acima é o conjunto de instruções de Shepherdson-Sturgis (1963).
  • Defina "ADD (r j , r k , r i )", (talvez preservando o conteúdo de r j e r k ), usando o acima:
{ADICIONE, CPY, CLR, J, DEC, INC, JZ, H}
  • Defina "MULtiply (r j , r k , r i )" (MUL) (talvez preservando o conteúdo de r j , r k ), nos termos do acima:
{MUL, ADICIONAR, CPY, CLR, J, DEC, INC, JZ, H}
  • Defina "EXPonential (r j , r k , r i )" (EXP) (talvez preservando o conteúdo de r j , r k ) nos termos acima,
{EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H}

Em geral, podemos construir qualquer função recursiva primitiva parcial ou total que desejarmos, usando os mesmos métodos. De fato, Minsky (1967), Shepherdson-Sturgis (1963) e Boolos-Burgess-Jeffrey (2002) dão demonstrações de como formar os cinco "operadores" de função recursiva primitiva (1-5 abaixo) a partir do conjunto de base (1).

Mas e quanto à equivalência de Turing completa ? Precisamos adicionar o sexto operador - o operador μ - para obter a equivalência completa, capaz de criar as funções recursivas total e parcial :

  1. Função zero (ou função constante)
  2. Função sucessora
  3. Função de identidade
  4. Função de composição
  5. Recursão primitiva (indução)
  6. operador μ (operador de pesquisa ilimitado)

Os autores mostram que isso é feito facilmente em qualquer um dos conjuntos de base disponíveis (1, 2 ou 3) (um exemplo pode ser encontrado no operador µ ). No entanto, o leitor precisa ser avisado que, embora o operador μ seja facilmente criado pelo conjunto de instruções de base, não significa que uma função recursiva parcial arbitrária possa ser facilmente criada com um modelo de base - equivalência de Turing e funções recursivas parciais implicam um operador μ ilimitado , que pode correr para as extremidades da cadeia de registros ad infinitum em busca de seu objetivo. O problema é: os registros devem ser chamados explicitamente por número / nome, por exemplo, INC (47.528) e DEC (39.347) e isso irá exaurir a TABELA de instruções da máquina de estados finitos. Não importa o quão "grande" seja a máquina de estados finitos, podemos encontrar uma função que usa um número "maior" de registradores.

Problemas com o modelo da máquina contrária

Os problemas são discutidos em detalhes no artigo Máquina de acesso aleatório . Os problemas se enquadram em duas classes principais e uma terceira classe de "inconveniência":

(1) Capacidades ilimitadas de registradores versus capacidades limitadas de instruções de máquina de estado: Como a máquina criará constantes maiores do que a capacidade de sua máquina de estado finito?

(2) Números ilimitados de registros versus números limitados de instruções de máquina de estado: Como a máquina acessará registros com números de endereço além do alcance / capacidade de sua máquina de estado finito?

(3) Os modelos totalmente reduzidos são pesados:

Shepherdson e Sturgis (1963) não se desculpam por seu conjunto de 6 instruções. Eles fizeram sua escolha com base na "facilidade de programação ... ao invés de economia" (p. 219 nota de rodapé 1).

Instruções de Shepherdson e Sturgis ([r] indica "conteúdo do registro r"):

    • INCREMENTO (r); [r] +1 → r
    • REDUÇÃO (r); [r] -1 → r
    • CLEAR (r); 0 → r
    • CÓPIA (r s a r d ); [r s ] → r d
    • SALTO-INCONDICIONAL para a instrução I z
    • JUMP IF [r] = 0 para a instrução I z

Minsky (1967) expandiu seu conjunto de 2 instruções {INC (z), JZDEC (r, I z )} para {CLR (r), INC (r), JZDEC (r, I z ), J (I z )} antes de sua prova de que uma "Máquina de Programa Universal" pode ser construída com apenas dois registradores (p. 255ss).

Máquinas de dois contadores são equivalentes a Turing (com uma ressalva)

Para cada máquina de Turing , existe um 2CM que a simula, desde que a entrada e a saída do 2CM estejam devidamente codificadas. Isso é provado no livro de Minsky ( Computation , 1967, p. 255-258), e uma prova alternativa é esboçada abaixo em três etapas. Primeiro, uma máquina de Turing pode ser simulada por uma máquina de estado finito (FSM) equipada com duas pilhas. Então, duas pilhas podem ser simuladas por quatro contadores. Finalmente, quatro contadores podem ser simulados por dois contadores. A máquina de dois contadores usa o conjunto de instruções {INC (r, z), JZDEC (r, z verdadeiro , z falso )}.

Etapa 1: uma máquina de Turing pode ser simulada por duas pilhas.

Uma máquina de Turing consiste em um FSM e uma fita infinita, inicialmente preenchida com zeros, na qual a máquina pode escrever uns e zeros. A qualquer momento, o cabeçote de leitura / gravação da máquina aponta para uma célula da fita. Essa fita pode ser conceitualmente cortada pela metade nesse ponto. Cada metade da fita pode ser tratada como uma pilha , onde o topo é a célula mais próxima do cabeçote de leitura / gravação e o fundo fica a alguma distância do cabeçote, com todos os zeros na fita além do fundo. Consequentemente, uma máquina de Turing pode ser simulada por um FSM mais duas pilhas. Mover a cabeça para a esquerda ou direita equivale a tirar um pedaço de uma pilha e empurrá-la para a outra. Escrever é equivalente a mudar o bit antes de pressioná-lo.

Etapa 2: uma pilha pode ser simulada por dois contadores.

Uma pilha contendo zeros e uns pode ser simulada por dois contadores quando os bits na pilha são considerados como representando um número binário (o bit mais alto da pilha é o bit menos significativo). Colocar um zero na pilha é equivalente a dobrar o número. Empurrar um é equivalente a dobrar e adicionar 1. Popping é equivalente a dividir por 2, onde o resto é o bit que foi estourado. Dois contadores podem simular esta pilha, em que um dos contadores contém um número cuja representação binária representa os bits na pilha e o outro contador é usado como um bloco de notas. Para dobrar o número no primeiro contador, o FSM pode inicializar o segundo contador para zero, então diminuir repetidamente o primeiro contador uma vez e incrementar o segundo contador duas vezes. Isso continua até que o primeiro contador chegue a zero. Nesse ponto, o segundo contador conterá o número duplicado. A redução pela metade é executada diminuindo um contador duas vezes e incrementando o outro uma vez, e repetindo até que o primeiro contador chegue a zero. O restante pode ser determinado se atingiu zero após um número par ou ímpar de etapas, onde a paridade do número de etapas é codificada no estado do FSM.

Etapa 3: quatro contadores podem ser simulados por dois contadores.

Como antes, um dos contadores é usado como bloco de notas. O outro contém um número inteiro cuja fatoração primária é 2 a 3 b 5 c 7 d . Os expoentes a , b , c e d podem ser considerados como quatro contadores virtuais que estão sendo compactados (por meio da numeração de Gödel ) em um único contador real. Se o contador real for definido como zero e depois incrementado uma vez, isso é equivalente a definir todos os contadores virtuais como zero. Se o contador real for duplicado, isso é equivalente a incrementar a , e se for dividido pela metade, isso será equivalente a decrementar a . Por um procedimento semelhante, ele pode ser multiplicado ou dividido por 3, que é equivalente a aumentar ou diminuir b . Do mesmo modo, c e d pode ser incrementado ou decrementado. Para verificar se um contador virtual como c é igual a zero, basta dividir o contador real por 5, ver o que resta, depois multiplicar por 5 e adicionar novamente o resto. Isso deixa o contador real inalterado. O restante terá sido diferente de zero se e somente se c for zero.

Como resultado, um FSM com dois contadores pode simular quatro contadores, que por sua vez simulam duas pilhas, que simulam uma máquina de Turing. Portanto, um FSM mais dois contadores é pelo menos tão poderoso quanto uma máquina de Turing. Uma máquina de Turing pode simular facilmente um FSM com dois contadores, portanto, as duas máquinas têm potência equivalente.

A advertência: * Se * seus contadores forem inicializados com N e 0, então um 2CM não pode calcular 2 N

Este resultado, junto com uma lista de outras funções de N que não são calculáveis ​​por uma máquina de dois contadores - quando inicializada com N em um contador e 0 no outro - como N 2 , sqrt ( N ), log 2 ( N ), etc., aparece em um artigo de Schroeppel (1972). O resultado não é surpreendente, porque o modelo da máquina de dois contadores foi provado (por Minsky) ser universal apenas quando o argumento N é apropriadamente codificado (por Gödelização) para simular uma máquina de Turing cuja fita inicial contém N codificado em unário; além disso, a saída da máquina de dois contadores será codificada de forma semelhante. Esse fenômeno é típico de bases de computação muito pequenas, cuja universalidade é provada apenas por simulação (por exemplo, muitos tarpits de Turing , as menores máquinas de Turing universais conhecidas , etc.).

A prova é precedida por alguns teoremas interessantes:

  • "Teorema: Uma máquina de três contadores pode simular uma máquina de Turing" (p. 2, também cf Minsky 1967: 170-174)
  • "Teorema: Uma 3CM [máquina de três contadores] pode computar qualquer função recursiva parcial de uma variável. Ela começa com o argumento [ie N ] em um contador, e (se parar) deixa a resposta [ie F ( N )] em um balcão. " (p. 3)
  • "Teorema: Uma máquina de contador pode ser simulada por um 2CM [máquina de dois contadores], desde que uma codificação obscura seja aceita para a entrada e saída" [p. 3; a "codificação obscura" é: 2 W 3 X 5 Y 7 Z onde os contadores simulados são W, X, Y, Z]
  • "Teorema: Qualquer máquina de contador pode ser simulada por um 2CM, desde que uma codificação obscura seja aceita para a entrada e saída." (p. 3)
    • "Corolário: o problema da parada para 2CMs é insolúvel.
    • "Corolário: Um 2CM pode calcular qualquer função recursiva parcial de um argumento, desde que a entrada seja codificada como 2 N e a saída (se a máquina parar) for codificada como 2 resposta ." (p. 3)
  • "Teorema: Não há duas máquinas de contador que calcule 2 N [se um contador for inicializado com N ]." (p. 11)

Com relação ao segundo teorema de que "Um 3CM pode calcular qualquer função recursiva parcial", o autor desafia o leitor com um "Problema difícil: multiplique dois números usando apenas três contadores" (p. 2). A prova principal envolve a noção de que as máquinas de dois contadores não podem computar sequências aritméticas com taxas de crescimento não lineares (pág. 15), ou seja, "a função 2 X cresce mais rapidamente do que qualquer progressão aritmética". (p. 11).

Um exemplo prático de cálculo por contagem

A calculadora Friden EC-130 não tinha lógica de somador como tal. Sua lógica era altamente serial, fazendo aritmética por contagem. Internamente, os dígitos decimais eram raiz-1 - por exemplo, um seis era representado por seis pulsos consecutivos dentro do intervalo de tempo alocado para aquele dígito. Cada intervalo de tempo carregava um dígito, o menos significativo primeiro. Carries definiu um flip-flop que fez com que uma contagem fosse adicionada ao dígito no próximo intervalo de tempo.

A adição foi feita por um contador ascendente, enquanto a subtração foi feita por um contador inferior, com um esquema semelhante para lidar com empréstimos.

O esquema de intervalo de tempo definiu seis registros de 13 dígitos decimais, cada um com um bit de sinal. Multiplicação e divisão foram feitas basicamente por adição e subtração repetidas. A versão de raiz quadrada, o EC-132, efetivamente subtraia inteiros ímpares consecutivos, cada decréscimo exigindo duas subtrações consecutivas. Após o primeiro, o minuendo foi incrementado em um antes da segunda subtração.

Veja também

Referências

  • 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 (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 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.
  • Fischer, Patrick C .; Meyer, AR ; Rosenberg, Arnold L. (1968), "Counter machines and counter languages", Mathematical Systems Theory , 2 : 265-283, doi : 10.1007 / bf01694011 , MR  0235932. Desenvolve teoremas de hierarquia de tempo e hierarquia de espaço para máquinas de contador, análogos às hierarquias para máquinas de Turing.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232-245.
  • Hopcroft, John; Jeffrey Ullman (1979). Introdução à Teoria dos Autômatos, Linguagens e Computação (1ª ed.). Leitura da missa: 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 dos Bell telephone Laborators e com o Dr. H. Wang da Universidade de Oxford".
  • Marvin Minsky (1961, recebido em 15 de agosto de 1960). "Insolucionabilidade recursiva do problema de 'tag' de Post e outros tópicos da teoria das máquinas de Turing". Annals of Mathematics . Annals of Mathematics. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR  1970290 . Verifique os valores de data em: |date=( ajuda )
  • 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. Semesterberichte (Göttingen) 4 (1954), 42–53.
  • A. Schōnhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. Em que Schōnhage mostra a equivalência de seu SMM com o "sucessor RAM" (Random Access Machine), etc.
  • Rich Schroeppel , maio de 1972, "A Two counter Machine Cannot Calculate 2 N ", Massachusetts Institute of Technology, AI Laboratory, Artificial Intelligence Memo # 257. O autor faz referência a Minsky 1967 e observa que " Frances Yao provou independentemente a não computabilidade usando um método semelhante em abril de 1971."
  • Peter van Emde Boas , Machine Models and Simulations, pp. 3-66, aparecendo em:
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.
O tratamento de van Emde Boas de SMMs aparece nas pp. 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.

links externos

  1. ^ [1]