Máquina de registradores
Na lógica matemática e na ciência da computação teórica uma máquina de registradores é uma classe genérica de máquinas abstratas usadas de uma maneira similar a máquina de Turing. Todos os modelos são Turing equivalentes. Visão geralA 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:
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. [1] Definição formal
Uma máquina de registradores consiste de:
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.
Desevolvimento histórico do modelo da máquina de registradoresDuas tendências apareceram no começo dos anos 1950 - a primeira para caracterizar o computador como uma máquina de Turing; e a segunda para definir modelos de computador com instruções sequenciais e saltos condicionais-com o poder de uma máquina de Turing, i.e. uma chamada Turing equivalência. Necessidades para este trabalho foram realizados no âmbito de dois problemas "difíceis": o problema da palavra indicesivel mostrado por Emil Post-seu problema da "parada"-e os "dificílimos" problemas de Hilbert-a 10 questão sobre equações diofantinas. Pesquisadores estavam procurando por modelos Turing-equivalentes que fossem menos "lógicos" em natureza e mais "aritmético". (cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218). A primeira tendência-em direção a caracterização de computadores-parece ter originado[4] 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:
Aparentemente Lambek, Melzak, Minsky e Shepherdson e Sturgis anteciparam independentemente a mesma idéia ao mesmo tempo. A história começa com o modelo de Wang. (1954, 1957) Modelo de Wang: Máquina de Post-TuringO 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:
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":
Wangs expressou esperanças de que seu modelo fosse uma "aproximação" (p. 63) entre as máquinas teóricas deTuring e o computador do mundo prático. O trabalho de Wang foi altamente influente. Nós o vemos ser referenciado por Minsky (1961) e (1967), Melzak (1961), Shepherdson e Sturgis (1963). De fato, Shepherdson e Sturgis (1963) observaram que:
Martin Davis eventualmente evoluiu esse modelo na Máquina de Post-Turing de 2 símbolos. Dificuldades com o modelo de Wang/modelo de Post-Turing: Exceto de que havia um problema: o modelo de Wang(as seis instruções no modelo de 7 na máquina de Post-Turing) ainda era como uma máquina de Turing de de fita única, não importando o quanto o seu programa de instruções sequenciais era bom. Tanto Melzak (1961) e Shepherdson e Sturgis (1963) observaram isso (no contexto de certas provas e investigações):
Ela tem somente uma fita, então existe certa dificuldade de se encontrar o número em que se deseja trabalhar e mantê-lo separado dos outros números" (Shepherdson and Sturgis (1963) p. 218). Modelos de "corte de fita" de Minsky, Melzak-Lambek e Shepherdson-SturgisxEntao por que não cortar a fita para que cada uma seja infinitamente longa(para acomodar numerais de qualquer número), mas com finais a esquerda, e chamar esse modelo de "Post-Turing de três fitas"? As cabeças individuais irão mover para esquerda(para decrementar) e para direita(para incrementar). Em um sentido as cabeças indicam "o topo da pilha" dos pontos concatenados. Ou em Minsky (1961) e Hopcroft e Ullman (1979, p. 171ff) a fita está sempre vazia exceto pela marca a esquerda - em nenhum momento uma cabeça imprime ou apaga. Nós apenas temos que tomar cuidado para escrever nossas instruções para que um teste por zero e saltos ocorram antes de decrementar, senão nossa máquina irá "cair para fim"-nós temos uma instância de função parcial. Antes de uma diminuição, nossa máquina deve sempre perguntar: "A fita está vazia? Se sim, então eu não posso decrementar. Se não, então eu posso." Minsky (1961) e Shepherdson-Sturgis (1963) provaram que apenas algumas fitas-quase nenhumas-ainda permitiam que a máquina fosse Turing equivalente SE o dado na fita fosse representado como um número de Gödel(ou outro número unicamente decodificável); este número vai evoluir conforme a computação procede. Na versão versão de uma fita com o número de Gödel , a máquina de contador deve ser capaz de (i) multiplicar o número de Gödel por uma constante(números "2" ou "3"), e (ii) dividir por uma constante, e saltar se o restante for zero. Minsky (1967) mostra que é necessário para que esse conjunto de instruções bizarro possa ser simplificado para { INC (r), JZDEC (r, z) } e as instruções { CLR (r), J (r) } se as duas fitas estiverem disponíveis. No entanto, uma simples Gödelização ainda é necessária. Um resultado similar aparece em Elgot-Robinson (1964) com respeito ao modelo RASP. (1961) O modelo de Melzak é diferente: grupos de pedras vão pra dentro e pra fora de aberturasO modelo de Melzak (1961) é significativamente diferente. Ele pegou seu próprio modelo, virou as fitas verticalmente, chamou-as de “aberturas no chão” a serem enchidos por “contadores pedras”. Diferente do “incremente” e “decremente” de Minsky, Melzak permitiu subtração, e adição, convencional de qualquer quantidade de pedras. Ele define endereçamento indireto para seu modelo (p. 288) e mostra dois exemplos de seu uso (p. 89); sua prova (p. 290-292) de que o modelo é Turing equivalente é tão “nebulozamente” explicada que o leitor não consegue distinguir se ele desejava ou não que endereçamento indireto fosse necessário para a prova. O legado do modelo de Melzak é a simplificação do modelo de Lambek e a reaparição de suas convenções mnemônicas em Cook e Reckhow (1973). Lambek (1961) reduz o modelo de Melzak no modelo de Minsky (1961): INC e DEC-with-testLambek (1961) tomou o modelo ternário de Melzak e o reduziu às duas instruções unárias —X+, X- if possible else jump— exatamente as mesmas que Minsky (1961) apresentou. No entanto, como o modelo de Minsky (1961), o modelo de Lambek executa suas instruções de uma maneira sequencial—tanto X+ quanto X- carregam o identificador da próxima instrução, e X- também carrega a instrução jump-to se o teste condicional ocorrer com sucesso. Elgot-Robinson (1964) e o problema da RASP sem endereçamento indiretoUma RASP ou máquina RASP começa como uma máquina de contador com sua “programa de instruções” em seus “registradores”. Analogamente ao, mas independente do, “Registrador de Instruções” de uma máquina de estado finita, pelo menos um de seus registradores (chamado de “contador de programa” (PC)) e um ou mais registradores “temporários” mantém um registro de, e operam no, número da instrução atual. A tabela de instruções de uma máquina de estado finita é responsável por (i) buscar a instrução de programa atual do registrador apropriado, (ii) ler a instrução de programa, (iii) buscar os operados especificados pela instrução de programa, e (iv) executar a instrução de programa. No entanto há um problema: Se for baseada na “máquina de contadores” esse “computador”, máquina de von Neumann não será Turing-equivalente. Ela não consegue computar tudo que é computável. Intrinsecamente, o modelo e limitado pelo tamanho de suas instruções de máquina de estado (bastante) “finitas”. O RASP baseado numa máquina de contadores pode computar qualquer função recursiva primitiva (como multiplicação, por exemplo), mas não todas as funções mu-recursivas, como a função de Ackermann. Elgot-Robinson investigou a possibilidade de permitir seu modelo RASP a modificar por si só suas próprias instruções de programa. Essa era uma ideia antiga, proposta por Burks-Goldstine-von Neumann (1946-7), e algumas vezes chamada de “o goto computado”. Melzak (1961) menciona especificamente o “goto computado” por esse nome, mas provê seu modelo com endereçamento indireto em seu lugar. Goto computado: Um programa RASP de instruções que modifica o “endereço goto” em uma instrução de pulo (jump) condicional ou incondicional. Mas isso não resolve o problema (a não ser que se faça uso de números de Gödel. O que é necessário é um método de buscar o endereço de uma instrução de programa que está (bastante) “depois/acima” do limite superior do registrador e tabela de instruções da máquina de estados finita.
Minsky (1967) menciona esse problema em sua investigação de uma máquina de contadores. (ele as chama de “modelos de computador de programas”) equipado com as instruções { CLR (r), INC (r), e RPT (repita as instruções de m a n um certo número de vezes) }. Ele não nos diz como consertar o problema, mas ele observa que:
Mas Elgot e Robinson resolveram o problema: eles aumentaram seus RASP P0 com um conjunto de instruções indexado - uma forma, de uma certa maneira, mais complicada (mas mais flexível) de endereçamento indireto. Seu modelo P'0 endereça os registradores adicionando o conteúdo do registrador “base” (especificado na instrução) ao “index”, especificado explicitamente na instrução (ou vice versa, trocando “base” e “index”). Dessa maneira, a instruções indexadoras P'0 possuem um parâmetro a mais quando comparado com as instruções não-indexadoras P0:
Hartmanis (1971)Em 1971, Hartmanis simplificou a indexação para indireção com o objetivo de usá-lo em seu modelo RASP. Endereçamento Indireto: Um registrador-ponteiro provê à máquina de estados finita o endereço do registrador “alvo” requerido pela instrução. Em outras palavras: O “conteúdo” do registrador-ponteiro é o “endereço” do registrador “alvo” a ser usado pela instrução. Se o registrador ponteiro for ilimitado, a RAM, e um RASP adequado anexado no seu chassi, vai ser Turing-equivalente. O registrador “alvo” pode servir tanto como um registrador fonte (source) ou destino (destination), da maneira que estiver especificado na instrução. Note que a máquina de estado finita não tem que especificar explicitamente o endereço desse registrador alvo. Ele apenas diz para o resto da máquina: Dê-me o conteúdo do registrador apontado pelo meu registrador-ponteiro e depois faça xyz com isso. Esse registrador ponteiro deve ser especificado explicitamente por nome (“N”, ou “72, ou “PC”, por exemplo), através da respectiva instrução, mas não é necessário ter conhecimento do conteúdo desse registrador. Cook e Reckhow (1973) descrevem a RAMCook e Reckhow (1973) citam Hartmanis (1971) e simplificam seu modelo para o que eles chamam de Máquina de acesso randômico (em inglês, Random Access Machine, RAM, i.e. uma máquina com indireção e arquitetura Harvard). De uma certa maneira voltando a ideia presentada por Melzak (1961), mas com um modelo bem mais simples. PrecedênciaMinsky estava trabalhando no M.I.T. Lincoln Labs, onde publicou seu trabalho. Seu artigo foi recebido para publicação nos “Anais de Matemática” em 15 de Agosto, 1960, mas nao publicado até Novembro de 1961. Mesmo tendo sido submetido um ano antes dos trabalhos de Melzak e Lambek fosse submetido e publicado (recebidos, respectivamente, em 15 de Maio e 15 de Junho de de 1961 e publicados juntos em setembro de 1961). O fato de (i) ambos serem canadenses e publicados no Boletim de Matemática Canadense, (ii) nenhum dos dois referenciarem o trabalho de Minsky, pois esse ainda não havia sido publicado em um periódico, mas (iii) Melzak referenciar Wang, e Lambek referenciar Melzak, leva a hipótese de que seus trabalhos se desenvolveram simultaneamente e independentemente. Quase exatamente a mesma coisa aconteceu com Shepherdson e Sturgis. Seus artigos foram recebidos em dezembro de 1961 - alguns meses depois dos artigos de Melzak e Lambek. Novamente, eles tiveram pouca (no máximo um mês) ou nenhuma chance de revisar o trabalho de Minsky. Eles foram cuidados em observar em uma nota de rodapé que artigos de Eschov, Kaphengst e Peter haviam “aparecido recentemente” (p. 219). Na verdade, esses foram publicados muito antes, mas em jornais alemães, publicados em alemão, o que dificultou a acessibilidade ao trabalho. O ultimo artigo de Shepherdson e Sturgis não apareceram em um periódico até 1963. Além disso, como eles honestamente descrevem no Apendix A, os ‘sistems’ de Kaphengst (1959), Ershov (1958), Peter (1958) são todos tão similares entre si quanto aos resultados obtidos, descritos como um conjunto indistinguível do seguinte:
Realmente, Shepherson e Sturgis concluem:
Ordenados pela data de publicação, os trabalhos de Kaphengst (1959), Ershov (1958) e Peter (1958) vieram primeiro. Veja tambémBibliografiaTextos base A seguinte bibliografia de artigos inclui alguns textos a serem usados como base. A matemática que leva ao conjunto de artigos sobre máquinas abstratas nos anos 50 e 60 podem ser encontrados em van Heijenoort (1967) - uma coletânea de artigos originais cobrindo os 50 anos desde Frege (1879) até Gödel (1964) (p. 71); os artigos original de Alan Turing (1936-7) e Emil Post (1936) estão incluídos em “The Indecidable”. As matemáticas de Church, Rosser e Kleene que aparecem como reimpressões dos artigos original em “The Indecidable” continuaram a ser exploradas em Kleene (1952), um texto indispensável para qualquer pessoa procurando um entendimento mais profundo da matemática por trás das máquinas. Tanto Kleene (1952) quanto Davis (1958) são referenciados por vários artigos. Para um bom estudo da máquina de registradores veja Minsky (1967), capítulo 11, “Modelos similares a Computadores Digitais” - onde ele chama a máquina de registradores de “computador-programa”. Uma nova visão é encontrada em van Emde Boas (1990). Um estudo recente do modelo de Minsky (1961)/Lambek (1961) pode ser encontrado em Boolos-Burgeess-Jeffrey (2002); eles reencarnaram o “modelo do ábaco” de Lambek para demonstrar equivalência entre máquinas de Turing e funções parcialmente recursivas, e eles disponibilizam uma introdução de nível de mestrado para tanto modelos de máquinas abstratas (contadoras e de Turing) e a matemática da teoria da recursão. Começando com a primeira edição de Boolos-Burgess (1970), esse modelo apareceu com virtualmente o mesmo nível de detalhe. Os artigos: Os artigos começam com Wang (1957) e sua dramática simplificação da máquina de Turing. Turing (1936), Kleene (1952), Davis (1958) e em particular Post (1936) são citados em Wang (1957); por sua vez, Wang é referenciado por Melzak (1961), Minsky (1961) e Shepherdson -Sturgis (1961-3) na maneira em como eles independentemente reduzem as fitas da máquina de Turing a “contadores”. Melzak (1961) mostra seu modelo de máquina de contadores “pebble-in-holes” (pedra-em-buracos, literalmente) com indireção, mas não conduz o estudo a frente. O trabalho de Elgot-Robinson (1964) define a máquina RASP (Random Access Stored Program) e parece ser o primeiro a investigar a falha que máquinas de contadores limitadas tem em calcular funções mu-recursivas. Essa falha - com exceção do uso draconiano do Número de Gödel a moda de Minsky (1961) - leva a sua definição de instruções “indexadas” (i.e. endereçamento indireto) para seu modelo RASP. Elgot-Robinson (1964) e também Hartmanis (1971) investigam RASPs com programas que modificam a si mesmos. Hartmanis (1971) especifica um conjunto de instruções com indireção, citando notas de aula de Cook (1970). Para uso em investigações de complexidade computacional, Cook e seu estudante de graduação Reckhow (1973) provem a definição de uma RAM (o modelo e a convenção mnemônica são similares as de Melzak, mas não o referenciam no artigo). As máquinas de ponteiros são um trabalho de Knuth (1968, 1973) e, independentemente, de Schönhage (1980). Em sua maior parte os artigos contem matemática que ultrapassa o nível de um curso de graduação - em particular funções recursivas primitivas e funções mu-recursivas apresentadas elegantemente em Kleene (1952) e superficialmente, mas útil de qualquer maneira, em Boolos-Burgess-Jeffrey (2002). Todos os textos e artigos com exceção dos quatro marcados com asteriscos foram revisados. Esses quatro estão escritos em alemão e aparecem como referencia em Shepherdson-Sturgis (1963) e Elgot-Robinson (1964), Shepherson-Sturgis (1963) oferecem uma breve discussão de seus resultados no apendix A do trabalho de Shepherson-Sturgis. A terminologia de pelo menos um artigo (Kaphengst (1959) parece usar a mesma análise de arquitetura de computadores de Burke-Goldstine-von Neumann(1946-7).
ReferênciasNotas
Fontes
Ligações externas |