An experimental implementation of the esolang Eodermdrome in Clojure, which is a Kolmogorov-Uspensky machine. Inspiration taken from the python version.

The Kolmogorov-Uspensky machine, (KUM), is an abstract machine. Abstract machines were introduced to Computer Science as a mean of formalizing the concept of an algorithm. The most familiar example of this is the Turing Machine where the machine operates on an infinite memory tape dived into cells. Both the Turning Machine and the KUM are in the computational class and considered Turing-complete. The difference between them is in the storage. In the KUM, the tape can change its topology.

The KUM storage is a finite connected undirected graph with an active node that is associated with the active region, or neighborhood, of the graph. The control of the machine reacts configuration of the graph and then modifies it by rewriting it.

An Eodermdrome program creates graphs from a string of letters. For example the graph of abcdae would produce

The program itself consists of series of commands or rules. The command will be executed if the following prereqs are met:

• The match graph in the command is a subgraph of the system graph.
• If an input set is part of the command, the input character read of the system input must match it.

A command is of the form:

• match-graph graph-replacement
  • This will execute if the match-graph is a subgraph and then transform the match to the replacement.
  • Example:a abc
• (input-set) match-graph graph-replacement.
  • This will execute if the match is a subgraph and if the next character of the system input matches. On executing, it will read one char from the input and then transform the match graph with the replacement.
  • Example: (1) a abc
• match-graph (output) graph-replacement.
  • This will execute if the match-graph is a subgraph. On executing, it will print the output to the system and transform the match with the replacement.
  • Example: a (1) abc
• (input-set) match-graph (output) graph-replacement.
  • This will execute if the match is a subgraph and if the next character of the system input matches. On executing, it will read one char from the input, print the output to the system, and then transform the match graph with the replacement.
  • Example: (0) a (1) abc

Comments are also allowed as text in between commas. In this implementation, they must be contained on a single line. Example: ,this is a comment,(1) a abc

The initial state of the graph with a program is the denoted by the graph string thequickbrownfoxjumpsoverthelazydog.

Example program for adding two string of ones together separated by zeros.

,takes input of ones seperated by zeros and adds the ones, thequickbrownfoxjumpsoverthelazydog a
(1) a ab
(0) a a
ab (1) a

Given a system input of "11011", it will print out "1111".

It can be run from the command line with lein run program-file input-string. There is also an optional debug flag, which if used, will cause graph png files to be placed in the home directory to document all the graph transformations.

Examples:

$ lein run examples/adder.eo "11011"
Running program  examples/adder.eo  with input  11011
1111

The doubler.eo example program takes in a string of ones and doubles them

lein run examples/doubler.eo "111"
Running program  examples/doubler.eo  with input  111
111111

using debug option

lein run examples/adder.eo "101" debug

FIXME

• My blog post that walks through an example
• On Kolmogorov Machines And Related Issues
• Kolmogorov's Heritage in Mathematics
• What is a "pointer machine"

Copyright © 2016 Carin Meier

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.