|
Máquina de ponteirosEm Ciência da computação teórica uma máquina de ponteiros é uma máquina abstrata computacional "atomística", cujo modelo é parecido com a máquina de acesso aleatório. Dependendo do tipo, uma máquina de ponteiros pode ser chamado de um autômato de ligação, uma KU-Machine, um SMM, uma máquina LISP atomísitica, uma tree-pointer machine, etc (cf Ben-Amram 1995). Pelo menos três principais variedades existem na literatura, o modelo de Kolmogorov-Uspenskii (KUM, KU-Machine), o autômato de ligação de Knuth, e o modelo de Máquina de Modificação de Armazenamento de Schönhage (Storage Modification Machine - SMM). O SMM parece ser o mais comum. Desde a sua fita apenas de leitura (read-only tape ou equivalente) uma máquina de ponteiros recebe uma entrada - sequência de símbolos delimitados ("palavras") feitas de pelo menos dois símbolos por exemplo, {0, 1} - e escreve sequências de símbolos de saída em uma fita apenas de escrita(write-only tapeou equivalente). Para transformar uma sequência de símbolos (palavra de entrada) para sequência de símbolos de saída, a máquina é equipada com um "programa" - uma máquina de estados finitos (memória e lista de instruções). Através da sua máquina de estados o programa lê os símbolos de entrada , opera em sua estrutura de armazenamento - uma coleção de "nós" (registros) interligados por "arestas" (ponteiros marcaoas com os símbolos por exemplo, {0, 1}), e escreve símbolos na fita de saída. Máquinas de Ponteiros não podem fazer aritmética. A computação se procede apenas pela leitura dos símbolos de entrada, por modificações e pela execução vários testes sobre a sua estrutura de armazenamento, o padrão de nós e ponteiros e símbolos de saída com base nos testes. As "informações" estão na estrutura de armazenamento. Tipos de Máquinas de PonteirosAmbos Gurevich e Ben-Amram listam uma série de modelos "atomísticos" muito similares de "máquinas abstratas"; Ben-Amram acredita que os seis "modelos atomísticos" devem ser diferenciados de modelos de "alto nível". Este artigo irá discutir os seguintes três modelos atomísticos em particular:
Mas Ben-Amram adiciona mais:
Problemas com o modelo da Máquina de PonteirosO uso do modelo na teoria da complexidade: van Emde Boas (1990) manifesta a sua preocupação de que esta forma de modelo abstrato é:
Gurevich 1988 também expressa preocupação:
O fato de que , no § 3 e § 4 (pp. 494-497), o próprio Schönhage (1980) demonstra as equivalências em tempo real de seus dois modelos de Máquinas de Acesso Randômicos "RAM0" e "RAM1" leva alguém a questionar a necessidade da SMM para estudos de complexidade. Usos potenciais para o modelo: No entanto, Schönhage (1980) demonstra em seu § 6 ,Integer-multiplication in linear time. E Gurevich se pergunta se a "KU-Machine Paralela" assemelha-se um pouco ao cérebro humano (Gurevich (1988) p.5). Modelo da Máquina de Modificação de Armazenamento de Schönhage (SMM)O modelo SMM de Schönhage parece ser a mais comum e a mais aceita. É muito diferente do modelo da Máquina de Registro e outros modelos computacionais comuns, por exemplo, a Máquina de Turing baseada em fita ou a de espaços marcados e seixos indistinguíveis da Máquina de Contagem. O computador é composto por um alfabeto fixo de símbolos de entrada, e um Grafo orientado mutável (ou seja, um Diagrama de transição de estados), com suas setas marcadas por símbolos do alfabeto. Cada nó do grafo tem exatamente uma seta de saída marcada com cada símbolo, embora algumas destas podem voltar para o nó original. Um nó fixo do grafo é identificado como o início ou o nó de ativação. Cada palavra de símbolos do alfabeto pode ser então traduzido para um caminho através da máquina; por exemplo, 10011 se traduziria tendo um caminho a partir do nó de início saindo da seta 1, em seguida o caminho 0 do nó resultante, então caminho 0, em seguida, o caminho 1, e então caminho 1. O caminho pode por sua vez ser identificado com o nó resultante, mas esta identificação mudará conforme o grafo muda durante a computação. A máquina pode receber instruções que mudam o layout do gráfico. As instruções básicas são as new w , que cria um novo nó que é o "resultado" de seguir a string w , e a set w para v que (re)direciona uma aresta para um nó diferente. Aqui w e v representam palavras. v é uma seqüência de símbolos criada anteriormente de modo que a aresta redirecionada irá apontar "para trás" para um nó antigo que é o "resultado" dessa cadeia.  (1)new w: Cria um novo nó. 'W' representa a nova 'palavra' que cria o novo nó. A máquina lê a palavra w, segue o caminho representado pelos símbolos de w até que a máquina chegue no último símbolo "adicional" na palavra. O símbolo adicional por sua vez força o último estado a criar um novo nó, e "inverte" sua seta correspondente (aquela marcada com esse símbolo) de sua antiga posição para apontar para o novo nó. O novo nó por sua vez aponta todas as suas arestas de volta ao último estado antigo, onde elas apenas "descansam" ou "esperam "até que sejam redirecionadas por um outro new ou set. Em certo sentido os novos nós estão "dormindo", esperando por uma atribuição. No caso de o nó de partida ou um nó central que queríamos começar com ambas de suas arestas apontando de volta para eles mesmos.
(2) set w para v: Redireciona(move) uma aresta (seta) do caminho representado pela palavra w para um nó anterior que representa palavra v. Mais uma vez, é a última seta no caminho que é redirecionada.
(3) if v = w then instrução z: Instrução condicional que compara dois caminhos representados pelas palavras w e v para verificar se eles acabam no mesmo nó; se assim for, salta para a instrução z, caso contrário continue. Esta instrução corresponde a capacidade da Máquina de Turing de saltar para um novo estado.  Modelo de "Autômato de Ligação" de KnuthDe acordo com Schoenhage, Knuth observou que o modelo SMM coincide com um tipo especial de "autômato de ligação" brevemente explicado no primeiro volume de The Art of Computer Programming (cf. [4, pp. 462-463]) Modelo da Máquina de Kolmogorov-Uspenskii (KU-Machine)A KUM se difere da SMM em permitir apenas os ponteiros invertíveis: para cada ponteiro de um nó x para um nó y, um ponteiro inverso de y para x deve estar presente. Como os ponteiros de saída devem ser marcados por símbolos distintos do alfabeto, ambos os grafos KUM e SSM têm o grau de saída de arestas de complexidade O(1). No entanto, a invertibilidade dos ponteiros de KUM restringe o grau de entrada de arestas em O (1) também. Isso resolve alguns problemas físicos (ao oposto aos puramente de informação), como os que van Emde citara acima. Uma diferença adicional é que o KUM foi concebido como uma generalização da Máquina de Turing, e por isso permite que o nó atualmente "ativo" possa ser movido em torno do gráfico. Assim, os nós podem ser especificados por caracteres individuais em vez de palavras, e a ação a ser tomada pode ser determinado por uma tabela de estado em vez de uma lista de instruções fixa. Veja também
Referências
. * Peter van Emde BoasMachine Models and Simulations pp. 3–66, aparecendo em:
|
Portal di Ensiklopedia Dunia
