Máquina de ponteiros
# 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.
(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.

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