# 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

## 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 - paper by Yuri Gurevich
- "К определению алгоритма" (1958) by A.N. Kolmogorov and V.A. Uspensky