Hierarchies and space measures for pointer machines (Q2366564)

Pointer machines are computational devices that mainly differ with respect to the traditional Random Access Machine in the memory structure they operate on: bounded degree directed (or, as was the case for the original model as introduced by Kolmogorov and Uspenskii, undirected) graphs. As such these models have a natural time and space measure, being the number of computation steps performed and the size of the graph respectively. The model is equivalent with the standard sequential devices meaning that both families simulate each other with polynomial overhead in time and constant factor overhead in space. It has been observed independently by the authors of this paper and by the reviewer that in order for the latter constant factor overhead to be valid the size of graphs has to be measured in a nonstandard way: an \(n\)- node graph obtains size \(n.\log(n)\). The reason is that an \(n\)-node graph easily is seen to encode \(O(n.\log(n))\) bits of information. The authors obtain an optimal real-time simulation for an \(O(s.\log(s))\) space bounded Turing Machine by a pointer machine operating on \(O(s)\) nodes. Another result gives a constant factor speed-up theorem for the number of nodes used in a computation. Given the tight space overheads for simulations between Turing Machines and pointer machines the tight space hierarchy for Turing Machines is easily seen to translate to pointer machines. The authors also obtain a tight time hierarchy by programming an universal point machine with no more than a constant factor delay, supporting the sort of diagonalization known to be sufficient for obtaining tight hierarchies. Finally the authors show how to simulate a \(t(n)\) time-bounded alternating pointer machine using only \(t(n)/\log(t(n))\) nodes.