Theoretical Models and Abstract Concepts of Information Structures

Key Insight

Information structures inherently represent relationships among data elements either implicitly, through their relative order in memory, or explicitly, by employing links within nodes to point to others. The specific amount of structural detail needed in a computer program directly correlates with the operations intended for those nodes. While the focus often lies on internal representations within high-speed random-access memory, the broader subject of information structures also encompasses complexities like searching for specific node values, handling external data representation for input/output, and optimizing for slower memory devices where efficient algorithms and data schemes for linked nodes become critically intensified.

To further develop the theory of linked sets of nodes beyond practical implementations, an abstract machine model, termed a 'linking automaton' (or pointer machine), was proposed. This theoretical device is characterized by nodes containing 'k' link fields and 'r' information fields, alongside 'l' link registers and 's' information registers to manage its processes. Its foundational operations include creating new nodes, comparing information symbols or link values for equality, and transferring information or link values between registers and nodes, with the crucial constraint that only nodes pointed to by link registers are immediately accessible for manipulation.

A related model of computation, A. N. Kolmogorov's graph machine, introduced in 1952, operates by local modifications to graphs, replacing subgraphs within a fixed distance 'n' from a starting vertex. While linking automata can efficiently simulate graph machines, the reverse simulation is challenging, likely requiring unbounded running time for arbitrary linking automata unless the graph model is adjusted to directed graphs due to the bounded degree of vertices. The linking automaton model, aligning closely with operations available on real machines, is considered a more appropriate and relevant theory for the complexity of algorithms than Turing machines, particularly for practical values of 'n', despite Turing machines being more 'realistic' for 'n' approaching infinity due to fixed link field sizes.