Máquina de ponteiros

Em 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 Ponteiros

Ambos 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:

• Máquinas de Modificação de Armazenamento de Schönhage (Storage Modification Machine - SMM),
• Máquinas de Kolmogorov-Uspenskii (KUM ou KU-Machines),
• "Autômato de Ligação" de Knuth.

Mas Ben-Amram adiciona mais:

• Máquina Atomística Pure-LISP (APLM)
• Máquina Atomística Full-LISP (AFLM),
• Máquinas de Ponteiros Atomísticas em geral.

Problemas com o modelo da Máquina de Ponteiros

O uso do modelo na teoria da complexidade: van Emde Boas (1990) manifesta a sua preocupação de que esta forma de modelo abstrato é:

"Um modelo teórico interessante, mas ... a sua atratividade como um modelo fundamental para a teoria da complexidade é questionável. A sua medida do tempo é baseada no tempo uniforme num contexto em que esta medida é conhecida a subestimar a complexidade de tempo real. A mesma observação vale para a medida de espaço para a máquina "(van Emde Boas (1990) p. 35)

Gurevich 1988 também expressa preocupação:

"Pragmaticamente falando, o modelo Schönhage fornece uma boa medida da complexidade de tempo no estado atual do estudo (embora eu preferiria algo na linha dos computadores de acesso aleatório de Angluin e Valiant)" (Gurevich (1988) p 6. com referência a Angluin D. e Valiant LG, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings ", Journal of Computer and System Sciences 18 (1979) 155-193.)

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.

As etapas da criação de um novo "nó" em uma máquina 2-símbolo {0,1}: Quando deparada com uma nova palavra (aqui: "11" ), a máquina é responsável por (i) criação do novo nó 3 e apontar a "aresta-1" apropriada para ele, em seguida, (ii) a criação de dois novos ponteiros (uma "aresta-0" e uma "aresta-1") ambos de que apontam para o nó anterior (aqui: o nó 2).

(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.

• Exemplo: Seja "w" = 10110[1], onde o caractere final está entre parênteses para denotar a sua característica especial. Tomamos a "aresta-1" do nó atingido por 10110 (no final de um caminho de aresta cinco, portanto, o sexto nó), e apontá-lo para um novo nó 7. As duas arestas deste novo nó então apontam para "trás" em direção ao nó 6 do caminho.

(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.

• Exemplo: set 1011011 para 1011 , após a instrução acima, mudaria a "aresta-1" do novo nó em 101101 para apontar para o quinto nó do caminho, alcançado em 1011. Assim, o caminho 1011011 teria agora o mesmo resultado que 1011.

(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.

As etapas de criação de novos "nós" em uma máquina 2-símbolo{0,1}. Enquanto as palavras - cadeias de símbolos 0 e 1 - entram na máquina, esta cria o grafo. Como mostrado aqui, após o passo 5 duas palavras - "111" e "10" - ambas apontam para o nó 4. Neste momento, se a máquina fosse fazer o if 10 = 111 then xxx, então o teste seria bem sucedido e a máquina iria de fato saltar para a instrução xxx.

Modelo de "Autômato de Ligação" de Knuth

De 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

• Máquina de Registro - Modelo comupacional de [Máquina abstrata] genérica baseada em registradores
• Máquina de Contagem - Máquina mais primitiva, conjunto de instruções dos modelos de base são utilizados em toda a classe de máquinas de regsitro
• Máquina de Acesso Aleatório - RAM: Máquina de contagem com a capacidade de endereçamento indireto adicionada
• Máquina de Accesso Aleatório a Programas Armazenados - RASP: Máquina baseada em contagem ou em acesso randômico com um "programa de instruções" para ser encontrado nos próprios registros no contexto de uma máquina de Turing Universal ou seja, a Arquitetura devon Neumann.
• Máquina de Turing - Modelo computacional de Máquina abstrata genérica baseada em fita
• Máquina de Post-Turing - Tipo de Máquina de Turing minimalista de apenas uma fita, de duas direções de um símbolo {em branco, marcado}, mas com execução da sequência de instruções padrão de forma semelhante às máquinas de contagem básicas 3 de instrução.

Referências

• Amir Ben-Amram (1995), What is a "Pointer machine?, SIGACTN: SIGACT News, SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory))", volume 26, 1995 também: DIKU, Department of Computer Science, University of Copenhagen, amirben@diku.dk. No qual Ben-Amram descreve os tipos e subtipos: (tipo 1a) Máquinas Abstratas: Modelos Atomísticos incluind a máquina de Kolmogorov-Uspenskii (KUM), a máquina de Modificação de Armazenamento de Schönhage (SMM), o "Autômato de Ligação" de Knuth, APLM e AFLM (Máquina Atomística Pure-LISP) and (Máquina Atomística Full-LISP), Máquinas de Ponteiro Atomísticas em geral, Jone's I Language; (tipo 1b) Máquinas Abstratas: Modelos de alto nível, (tipo 2) Algoritmos de Ponteiros.

• Andrey Kolmogorov e V. Uspenskii , On the definition of an algorithm, Uspehi Mat. Nauk. 13 (1958), 3-28. English translation in American Mathematical Society Translations, Series II, Volume 29 (1963), pp. 217–245.

• Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (Julho 2000), páginas 77–111. Em uma única frase Gurevich compara a Máquina de Modificação de Armazenamento de Schönhage [1980] com "máquinas de ponteiro" de Knuth. Para mais, os modelos similares, como "máquinas de acesso aleatório" Gurevich referencia:
  • JE Savage (1998), Models of Computation: Exploring the Power of Computing. Addison Wesley Longman.

• Yuri Gurevich (1988), On Kolmogorov Machines and Related Issues, a coluna "Logic in Computer Science", Boletim da Associação Europeia para a Ciência da Computação Teórica, Número 35, Junho de 1988, 71-82. Introduziu a descrição unificada de máquinas Schōnhage e Kolmogorov-Uspenskii usadas aqui.

• A. 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 do sua SMM com o "sucessor RAM" (Máquina de Acesso Aleatório), etc. Ele se refere a um artigo anterior onde ele introduz o SMM:
  • A. Schōnhage (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dōrr, Hotz, eds. Bibliogr. Institut, Mannheim, 1970, pp. 69–383.

. * Peter van Emde BoasMachine Models and Simulations pp. 3–66, aparecendo em:

Jan van Leeuwen, ed. "Handbbook 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.

Tratamento de van Emde Boas para as SMMs aparece nas páginas 32-35. Este tratamento esclarece Schōnhage 1980 como - que segue de perto, mas que expande um pouco o tratamento Schōnhage. Ambas as referências podem ser necessárias para a compreensão efetiva.