Máquina de ponteiro - Pointer machine

Na ciência da computação teórica, uma máquina de ponteiro é um modelo de máquina computacional abstrato "atomístico" semelhante à máquina de acesso aleatório . Um algoritmo de ponteiro é um algoritmo restrito ao modelo de máquina de ponteiro.

Dependendo do tipo, uma máquina de ponteiro pode ser chamada de autômato de ligação, uma máquina KU, um SMM, uma máquina LISP atomística, uma máquina de ponteiro de árvore, etc. (cf Ben-Amram 1995). Existem pelo menos três variedades principais na literatura - o modelo Kolmogorov-Uspenskii (KUM, KU-machine), o autômato de ligação Knuth e o modelo Schönhage Storage Modification Machine (SMM). O SMM parece ser o mais comum.

De sua "fita somente leitura" (ou equivalente), uma máquina de ponteiro recebe a entrada - sequências de símbolos vinculadas ("palavras") feitas de pelo menos dois símbolos, por exemplo {0, 1} - e escreve sequências de símbolos de saída em um saída de fita "somente gravação" (ou equivalente). Para transformar uma sequência de símbolos (palavra de entrada) em uma sequência de símbolos de saída, a máquina é equipada com um "programa" - uma máquina de estado finito (memória e lista de instruções). Por meio de sua máquina de estado, o programa lê os símbolos de entrada, opera em sua estrutura de armazenamento - uma coleção de "nós" (registros) interconectados por "bordas" (ponteiros rotulados com os símbolos, por exemplo, {0, 1}) e escreve símbolos no fita de saída.

Máquinas de ponteiro não podem fazer aritmética. A computação prossegue apenas lendo símbolos de entrada, modificando e fazendo vários testes em sua estrutura de armazenamento - o padrão de nós e ponteiros e emitindo símbolos com base nos testes. "Informações" estão na estrutura de armazenamento .

Tipos de "máquinas apontadoras"

Tanto Gurevich quanto Ben-Amram listam vários modelos "atomísticos" muito semelhantes de "máquinas abstratas"; Ben-Amram acredita que os 6 "modelos atomísticos" devem ser distinguidos dos modelos de "alto nível". Este artigo irá discutir os seguintes 3 modelos atomísticos em particular:

  • Máquinas de modificação de armazenamento (SMM) de Schönhage,
  • Máquinas Kolmogorov – Uspenskii (máquinas KUM ou KU),
  • O "autômato de vinculação" de Knuth

Mas Ben-Amram acrescentou mais:

  • Máquina atomística pure-LISP (APLM)
  • Máquina atomística full-LISP (AFLM),
  • Máquinas apontadoras atomísticas gerais,
  • Linguagem I de Jone (dois tipos)

Problemas com o modelo de ponteiro-máquina

Uso do modelo na teoria da complexidade : van Emde Boas (1990) expressa a preocupação de que esta forma de modelo abstrato seja:

"um modelo teórico interessante, mas ... sua atratividade como modelo fundamental para a teoria da complexidade é questionável. Sua medida de tempo é baseada em um tempo uniforme em um contexto onde essa medida subestima a verdadeira complexidade de tempo. 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 de Schönhage fornece uma boa medida da complexidade do tempo no estado da arte atual (embora eu prefira 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, em §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áquina de acesso aleatório "RAM0" e "RAM1" leva a questionar a necessidade do SMM para estudos de complexidade.

Usos potenciais para o modelo : No entanto, Schönhage (1980) demonstra em seu §6, Integer-multiplation in linear time . E Gurevich se pergunta se a "máquina KU paralela" "se assemelha ou não ao cérebro humano" (Gurevich (1988) p. 5)

Modelo de máquina de modificação de armazenamento (SMM) de Schönhage

O modelo SMM de Schönhage parece ser o mais comum e mais aceito. É bem diferente do modelo da máquina de registro e de outros modelos computacionais comuns, por exemplo, a máquina de Turing baseada em fita ou os orifícios marcados e seixos indistinguíveis da máquina de contagem .

O computador consiste em um alfabeto fixo de símbolos de entrada e um gráfico direcionado mutável (também conhecido como diagrama de estado ) com suas setas marcadas por símbolos do alfabeto. Cada nó do gráfico tem exatamente uma seta de saída rotulada com cada símbolo, embora alguns deles possam retornar ao nó original. Um nó fixo do gráfico é identificado como o nó inicial ou "ativo".

Cada palavra de símbolos no alfabeto pode então ser traduzida para um caminho através da máquina; por exemplo, 10011 se traduziria em pegar o caminho 1 do nó inicial, depois o caminho 0 do nó resultante, o caminho 0, o caminho 1 e o caminho 1. O caminho pode, por sua vez, ser identificado com o nó resultante, mas esta identificação mudará conforme o gráfico muda durante o cálculo.

A máquina pode receber instruções que alteram o layout do gráfico. As instruções básicas são a nova instrução w , que cria um novo nó que é o "resultado" de seguir a string w , e o conjunto de instruções w a v que (re) direciona uma aresta para um nó diferente. Aqui w e v representam palavras . v é uma palavra anterior - isto é, uma string de símbolos criada anteriormente - de forma que a borda redirecionada apontará "para trás" para um nó antigo que é o "resultado" dessa string.

As etapas na criação de um novo "nó" em uma máquina de 2 símbolos {0,1}: Quando confrontada com uma nova palavra (aqui: "11"), a máquina é responsável por (i) criar um novo nó 3 e apontar a aresta 1 apropriada para ele, então (ii) criar dois novos ponteiros (um 0- "aresta" e um 1- "aresta"), ambos apontando de volta para o nó anterior (aqui: nó 2).

(1) novo w : cria um novo nó. w representa a nova palavra que cria o novo nó. A máquina lê a palavra w , seguindo o caminho representado pelos símbolos de w até que a máquina chegue ao último, símbolo "adicional" na palavra. Em vez disso, o símbolo adicional força o último estado a criar um novo nó e "inverter" sua seta correspondente (aquela rotulada com aquele símbolo) de sua posição anterior para apontar para o novo nó. O novo nó, por sua vez, aponta todas as suas arestas de volta para o antigo último estado, onde elas apenas "descansam" até serem redirecionadas por outro novo ou conjunto . Em certo sentido, os novos nós estão "adormecidos", aguardando uma atribuição. No caso do nó inicial ou central, da mesma forma começaríamos com ambas as arestas apontando para ele.

  • Exemplo: Seja "w" 10110 [1], onde o caractere final está entre colchetes para denotar seu status especial. Pegamos a 1 aresta do nó alcançado por 10110 (no final de um caminho de cinco arestas, portanto, de seis nós) e apontamos para um novo sétimo nó. As duas arestas desse novo nó apontam "para trás" para o 6º nó do caminho.

(2) Defina w como v : redireciona (move) uma aresta (seta) do caminho representado pela palavra w para um nó anterior que representa a palavra v . Novamente, é a última seta no caminho que é redirecionada.

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

(3) Se v = w, então a instrução z  : Instrução condicional que compara dois caminhos representados pelas palavras w e v para ver se eles terminam no mesmo nó; se for assim, pule para a instrução z senão continue. Essa instrução tem o mesmo propósito que sua contraparte em uma máquina de registro ou máquina B de Wang , correspondendo à capacidade de uma máquina de Turing de saltar para um novo estado.

As etapas na criação de novos "nós" em uma máquina de 2 símbolos {0,1}. Conforme as palavras - cadeias de símbolos 0 e 1 - entram na máquina, a máquina cria o gráfico. Conforme mostrado aqui, após a 5ª etapa, duas palavras - "111" e "10" - ambas apontam para o nó 4. Nesse momento, se a máquina fizesse o se 10 = 111 então xxx, então o teste seria bem-sucedida e a máquina realmente pulará para xxx.

Modelo de "autômato de vinculaçã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 volume um de The Art of Computer Programming (cf. [4, pp. 462-463])

Modelo de máquina Kolmogorov – Uspenskii (máquina KU)

KUM difere do SMM por permitir apenas 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 rotulados por símbolos distintos do alfabeto, os gráficos KUM e SMM têm O (1) grau de saída. No entanto, a invertibilidade dos ponteiros KUM restringe o grau a O (1), também. Isso aborda algumas preocupações com o realismo físico (em oposição ao puramente informativo), como aquelas na citação de van Emde Boas acima.

Uma diferença adicional é que o KUM foi concebido como uma generalização da máquina de Turing e, portanto, permite que o nó atualmente "ativo" seja movido ao redor do gráfico. Consequentemente, os nós podem ser especificados por caracteres individuais em vez de palavras, e a ação a ser executada pode ser determinada por uma tabela de estados em vez de uma lista fixa de instruções.

Veja também

Máquina de registro - modelo computacional de máquina abstrata baseada em registro genérico

Máquina de Turing - modelo computacional de máquina abstrata baseada em fita genérica

  • Máquina pós-Turing - minimalista de uma fita, duas direções, 1 símbolo {espaço em branco, marca} Máquina do tipo Turing, mas com execução de instrução sequencial padrão de uma maneira semelhante às máquinas de contagem de 3 instruções básicas.

Referências

A maioria das referências e bibliografia podem ser encontradas no artigo Register machine . Os itens a seguir são específicos deste artigo:

  • Amir Ben-Amram (1995), O que é uma "máquina Pointer"? , SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory) ", volume 26, 1995. também: DIKU, Departamento de Ciência da Computação, Universidade de Copenhagen, amirben@diku.dk. Em que Ben-Amram descreve os tipos e subtipos: (tipo 1a) Máquinas abstratas: modelos atomísticos, incluindo máquinas Kolmogorov-Uspenskii (KUM), Máquinas de modificação de armazenamento de Schönhage (SMM), "Autômato de ligação" de Knuth, APLM e AFLM (Máquina Atomistic Pure-LISP) e (Atomistic Full-LISP máquina), Máquinas de ponteiro atomísticas gerais, linguagem de Jone's I; (tipo 1b) Máquinas abstratas: modelos de alto nível, (tipo 2) algoritmos de ponteiro.
  • Andrey Kolmogorov e V. Uspenskii , Sobre a definição de um algoritmo, Uspekhi Mat. Nauk 13 (1958), 3-28. Tradução para o inglês em American Mathematical Society Translations, Série II, Volume 29 (1963), pp. 217–245.
  • Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, vol. 1, não. 1, (julho de 2000), páginas 77-111. Em uma única frase, Gurevich compara as "máquinas de modificação de armazenamento" de Schönhage [1980] às "máquinas de ponteiro" de Knuth. Para saber mais, modelos semelhantes, como referências de Gurevich "máquinas de acesso aleatório":
  • Yuri Gurevich (1988), On Kolmogorov Machines and Related Issues , a coluna "Logic in Computer Science", Bulletin of European Association for Theoretical Computer Science, Number 35, June 1988, 71-82. Introduzida a descrição unificada das máquinas Schönhage e Kolmogorov-Uspenskii usadas aqui.
  • Arnold 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 de seu SMM com a "RAM sucessora" (Máquina de Acesso Aleatório), etc. Ele se refere a um artigo anterior onde ele apresenta o SMM:
    • Arnold Schönhage (1970), Universelle Turing Speicherung , Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Bibliogr. Institut, Mannheim, 1970, pp. 69-383.
  • Peter van Emde Boas , Machine Models and Simulations, pp. 3-66, aparecendo em:
Jan van Leeuwen , ed. "Handbook 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.
O tratamento de van Emde Boas de SMMs aparece nas páginas 32-35. Este tratamento esclarece Schönhage 1980 - segue de perto, mas expande ligeiramente o tratamento de Schönhage. Ambas as referências podem ser necessárias para um entendimento eficaz.