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. Harold Abelson e Gerald Jay Sussman com Julie Sussman, Structure and Interpretation of Computer Programs, MIT Press, Cambridge, Massachusetts, 2nd Ed, 1996
Definição formal Nenhuma terminologia padrão existe; cada autor é responsável por definir os seus mnemônicos ou símbolos. Muitos autores usam um símbolismo “registrar-transferir” para explicar as ações dos seus modelos, mas novamente eles são responsáveis por definir suas sintaxe.
Uma máquina de registradores consiste de:
Um não vinculado número de rotulados, discretos, registradores não vinculados por extensão(capacidade): um finito(ou infinito, em alguns modelos) conjunto de registradores cada um considerado como de extensão infinita e cada um suportando um numeral não negativo (0,1,2,...).". . . uma sequência contável de registradores numerados 1,2,3, ..., cada um podendo armazenar números naturais 0,1,2,... Cada programa particular, no entanto, envolve apenas um número finito desses registradores, os outros permanecendo vazios(i.e. contendo 0) durante a computação." Shepherdson e Sturgis 1961:219. Lambek 1961:295 propuseram "um contável conjunto infinito de localidades (buracos, fios, etc). Os registradores podem fazer a sua própria aritmética, ou pode ser que haja um ou mais registrador especial que faz a aritmética. Por exemplo, um "acumulador" e/ou um "registrador de endereços". Contadores ou marcadores:Por exemplo, Lambek 1961:295 propôs o uso de pedras, grânulos, etc. discretos, indistinguíveis objetos ou marcadores de um ou mais números adequados ao modelo. No mais reduzido modelo de máquina de contador, para cada operação aritmética apenas um objeto/marcador é ou adicionado ou removido de sua localidade/fita. Em alguns modelos de máquina de contador(ex: Melzak (1961), Minsky (1961)) e maior parte dos modelos RAM e RAPS podem adicionar ou remover mais de um objeto/marca com a operação de "adição" e geração "subtração"; ocasionalmente com "multiplicação" e/ou "divisão". Alguns modelos tem operações de controle como "copiar" (variavelmente: "mover", "ler", "armazenar") que move grupos de objetos/marcas de registrador a registrador em uma ação. Um limitado conjunto de instruções: as instruções tendem a ser divididas em duas classes: aritmé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). 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 (r1,r2), subtração-própria (r1,r2), Incrementar acumulador, Decrementar acumulador, Limpar acumulador, Adicionar para acumulador conteúdo do registrador r, subtração-própria do conteúdo do acumulador registrado r, } Augmented RAM, RASP: Todas funções reduzidas e mais: { Multiplicar, Dividar, várias funções booleanas de bit(left-shift, teste de bit, etc.)} Controle: Modelos de máquina de controle: opcional { Copiar tal (r1,r2) } Modelos RAM e RASP: deve haver { Copiar (r1,r2) }, ou { Ler acumulador de r, Guardar acumulador em r, Ler acumulador com uma constante imediata } Todos modelos: ao menos um "salto" condicional (branch, goto) seguindo teste de um registrador ex: { Jump-if-zero, Jump-if-not-zero (i.e. Jump-if-positive), Jump-if-equal, Jump-if-not equal } Todos modelos opcionais: { "salto" de programa incondicional (goto) } Método de endereçamento de registrador: Máquina de contador: sem endereçamento indireto, operações imediatas em modelos altamente atomizados RAM and RASP: endereçamento indireto viável, operações imediatas típicas Input-output: opcional em todos os modelos. Registrador de estados: Um registrador de instruções especiais "IR", finito e separado dos outros registradores acima, armazenando a instrução atual para ser executa e endereça na TABELA de instruções; este registrador e a TABELA é localizada na máquina de estados finitos. O IR é limitante para todos os modelos. No caso do RAM e RASP, por propósito de determinar o "endereço" de um registrador, o modelo pode selecionar tanto (i) no caso de endereçamento direto é especificado pela TABELA e temporariamente localizados no IR ou (ii) no caso de endereçamento indireto - o conteúdo do registrador é especificado pela instruções de IR. O IR "não" é o "contador de programação"(PC) do RASP(ou computador convencional). O PC é só outro registrador similar ao acumulador, mas dedicado a armazenar números da atual instrução de registro do RASP. Assim, o RASP tem duas "instruções/programações" registradores—(i) o IR (Registrador de instrução da máquina de estado finito), e (ii) um PC (contador de programação) para o programa localizado nos registos. (Bem como um registro dedicado à "PC", um RASP podem dedicar outro registro para o "Registro de instruções do programa" (indo por qualquer número de nomes como "PIR" IR "," PR ", etc.) Lista de instruções rotulados, geralmente em ordem sequencial: Uma lista de instruções finitas . 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, ztrue, zfalse ) }.Veja McCarthy Formalism para mais sobre expressões condicionais "IF r=0 THEN ztrue ELSE zfalse" (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 originadoVeja a "Nota" em Shepherdson e Sturgis 1963:219. No seu apêndice A o autor segue com uma listagem e discussão sobre o conjunto de instruções de Kaphengst, Ershov and Péter(cf p. 245ff). 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 ideia 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 de Turing 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: