Pointer machine (original) (raw)
In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model. Pointer machines cannot do arithmetic in normal ways. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. "Information" is in the storage structure.
| Property | Value |
|---|---|
| dbo:abstract | In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model. Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common. From its "read-only tape" (or equivalent) a pointer machine receives input—bounded symbol-sequences ("words") made of at least two symbols e.g. { 0, 1 } -- and it writes output symbol-sequences on an output "write-only" tape (or equivalent). To transform a symbol-sequence (input word) to an output symbol-sequence the machine is equipped with a "program"—a finite-state machine (memory and list of instructions). Via its state machine the program reads the input symbols, operates on its storage structure—a collection of "nodes" (registers) interconnected by "edges" (pointers labelled with the symbols e.g. { 0, 1 }), and writes symbols on the output tape. Pointer machines cannot do arithmetic in normal ways. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. "Information" is in the storage structure. (en) 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 . 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. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pointer-machine_2_.jpg?width=300 |
| dbo:wikiPageExternalLink | http://www2.mta.ac.il/~amirben/downloadable/pm.ps.gz http://research.microsoft.com/~gurevich/Opera/78.pdf https://web.archive.org/web/20161105053330/http:/cs.brown.edu/~jes/book/ |
| dbo:wikiPageID | 6144616 (xsd:integer) |
| dbo:wikiPageLength | 13776 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102623526 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Peter_van_Emde_Boas dbr:Vladimir_Andreyevich_Uspensky dbr:Andrey_Kolmogorov dbr:Theoretical_computer_science dbr:John_E._Savage dbc:Register_machines dbr:Directed_graph dbr:Jan_van_Leeuwen dbr:Counter_machine dbr:State_diagram dbr:Arnold_Schönhage dbr:Abstract_machine dbr:Register_machine dbr:Post–Turing_machine dbr:Random-access_machine dbr:Random-access_stored-program_machine dbr:Turing_machine dbr:Universal_Turing_machine dbr:Von_Neumann_architecture dbr:The_Art_of_Computer_Programming dbr:Yuri_Gurevich dbr:Amir_Ben-Amram dbr:File:Pointer-machine_1_.JPG dbr:File:Pointer-machine_2_.JPG dbr:Wang_b-machine |
| dbp:wikiPageUsesTemplate | dbt:ISBN dbt:More_footnotes_needed dbt:Reflist dbt:Tone |
| dct:subject | dbc:Register_machines |
| rdf:type | yago:Artifact100021939 yago:Device103183080 yago:Instrumentality103575240 yago:Machine103699975 yago:Object100002684 yago:PhysicalEntity100001930 yago:Whole100003553 yago:WikicatRegisterMachines |
| rdfs:comment | In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model. Pointer machines cannot do arithmetic in normal ways. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. "Information" is in the storage structure. (en) 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 . 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. (pt) |
| rdfs:label | Pointer machine (en) Máquina de ponteiros (pt) |
| owl:sameAs | freebase:Pointer machine yago-res:Pointer machine wikidata:Pointer machine dbpedia-pt:Pointer machine dbpedia-sr:Pointer machine https://global.dbpedia.org/id/4u4Sk |
| prov:wasDerivedFrom | wikipedia-en:Pointer_machine?oldid=1102623526&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Pointer-machine_1_.jpg wiki-commons:Special:FilePath/Pointer-machine_2_.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Pointer_machine |
| is dbo:knownFor of | dbr:Arnold_Schönhage |
| is dbo:wikiPageRedirects of | dbr:Pointer_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Cycle_detection dbr:Counter-machine_model dbr:Turing_machine_equivalents dbr:Church–Turing_thesis dbr:Andrey_Kolmogorov dbr:Linked_data_structure dbr:Algorithm_characterizations dbr:History_of_the_Church–Turing_thesis dbr:Counter_machine dbr:Range_searching dbr:Arnold_Schönhage dbr:Register_machine dbr:Integer_sorting dbr:Random-access_machine dbr:Random-access_stored-program_machine dbr:SMM dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Pointer_algorithm |
| is dbp:knownFor of | dbr:Arnold_Schönhage |
| is foaf:primaryTopic of | wikipedia-en:Pointer_machine |
