Kolmogorov machine
A Kolmogorov machine (also known as a Kolmogorov-Uspenski machine) is similar to a Turing machine in most respects except that its storage unit, instead of an unbounded linear tape, is a particular kind of connected graph.
"Real" Kolmogorov machines are very obscure; nearly every researcher who cites Kolmogorov and Uspenski's original paper (in Russian) uses a modified model, simplified for their purposes. So, bear in mind that the following is currently only an approximation.
Storage graph
The storage graph must have the Kolmogorov property, which is that, starting at some vertex, every other vertex is uniquely addressable. This was done by Kolmogorov and Uspenski by inserting intermediate 'address' vertices in an undirected graph; an alternate technique is to use a directed graph and simply to label the edges of the graph, with a different label bestowed upon each out-edge of a vertex.
The storage graph has a vertex which is thought of as the current vertex (much like Turing's tape has a read/write head that points to a current cell.) The current vertex has a neighbourhood of some fixed radius.
Control unit
Also like the Turing machine, the Kolmogorov machine also has a control unit which decides what to do by looking at the storage unit. However, instead of looking for symbols, it reacts to the configuration of the neighbourhood itself - the "shape" formed by the local vertices and edges. This determines a list of actions to take, which contains instructions drawn from:
- Add a vertex to the neighbourhood;
- Remove a vertex from the neighbourhood;
- Add an edge to the neighbourhood;
- Remove an edge from the neighbourhood;
- Halt.
Computational class
Kolmogorov machines are in the same computational class as Turing machines; that is, they are Turing-complete. They may, however, have efficiency advantages, due to their freedom from the restriction of a linear storage medium.
See Also
- Eodermdrome, a language formulated along similar principles.
- Andrei Machine 9000
- Kolmogorov
External resources
- Section 1.2.1 of Uspensky and Semenov's Algorithms: Main Ideas and Applications (1993, Kluwer Academic Publishers, ISBN 0-7923-2210-X)
- On Kolmogorov machines and related issues (from the Wayback Machine; retrieved on 13 September 2008) - paper by Yuri Gurevich
- "К определению алгоритма" (1958) by A.N. Kolmogorov and V.A. Uspensky
- wikipedia:Pointer machine, of which the Kolmogorov machine is a variety.