Eodermdrome

Eodermdrome is a graph-rewriting tarpit created in 2008 by User:ais523.

Syntax

An Eodermdrome program consists of a sequence of commands, separated by whitespace; each command consists of the following, separated by whitespace:

• optionally, a set of 1 or more characters enclosed in parentheses (if a closing parenthesis is in that set, it must be the first character of that set); this is the input set of the command
• a string of letters, representing a graph (see below); this is the match subgraph
• optionally, a string of 1 or more characters enclosed in parentheses (the first character may be a closing parenthesis, but none of the others may be); this is the output string of the command
• a string of letters, representing a graph (see below); this is the replacement subgraph

Graphs are written with a string of lowercase letters; each unique letter in the string represents a different node of the graph, and if the same letter is used more than once, it refers to the same node of the graph. There is an arc between any two letters which are consecutive in the string, but not otherwise. For instance, the string abcdae would map to the following graph:

c-d
| |
b-a-e

Comments can be included in the source file between commas, and are legal anywhere whitespace would be; also, any strings of whitespace that contain punctuation marks other than commas and parentheses are ignored along with the punctuation marks they contain (so abc. def is equivalent to abcdef).

Semantics

An Eodermdrome program works by repeatedly rewriting a graph, which represents the internal state of the program. At the start of any Eodermdrome program, the internal state is the graph corresponding to the string thequickbrownfoxjumpsoverthelazydog. Which letter is used for which node is immaterial between commands; it's the shape of the graph that matters, not the letters used to define it.

Execution of the program works by repeatedly running commands; the commands do not run in any particular order and can run any number of times. However, commands only run if all their prerequisites are met. If no command in the program has its prerequisites met, the program will exit; otherwise, an unspecified command whose prerequisites are met will be run (this means that an interpreter can always choose the first, or the last, or a random command, or use any other method to determine which command runs, if more than one can run).

If a command has an input set, it has a prerequisite that the next character to be read in from standard input must be a member of the set.

All commands also have a prerequisite based on their subgraphs and the internal state graph: the match subgraph must be a subgraph of the internal state graph (i.e. there is a 1-to-1 mapping of a subset of the internal state graph's nodes to the match subgraph's nodes, such that all arcs in the match subgraph also exist between the corresponding nodes in the internal state graph), and also all closed nodes in the match subgraph must have the same degree as the corresponding node in the internal state graph. A node in a match subgraph is open if the letter used to describe it in the match subgraph is also used to describe a node in the replacement subgraph, and closed otherwise; likewise, a node in a replacement subgraph is open if the letter used to describe it in the replacement subgraph is used to describe a node in the match subgraph, and closed otherwise.

When a command runs, it does the following, in order:

1. Removes a character from standard input, if it has an input set
2. Prints its output string to standard output, if it has one
3. Deletes all arcs in the internal state graph corresponding to arcs in the match subgraph
4. Deletes all nodes from the internal state graph that correspond to closed nodes in the match subgraph
5. Creates a node in the internal state graph corresponding to each closed node in the replacement subgraph
6. For each arc in the replacement subgraph, create an arc in the internal state graph corresponding to it (i.e. such that if two nodes are joined in the replacement subgraph, an arc is created between the two nodes in the internal state graph that correspond to them)

Initial state graph

The initial state graph is planar, and has no cycles of length 3 or 5, but has every other cycle length from 4 up to the maximum of 18. It has 1 node of degree 1, 21 nodes of degree 2, 2 nodes of degree 4, one node of degree 5 and one node of degree 8. It has a single nontrivial automorphism, switching w and f.

Example programs

• Bitwise Cyclic Tag (see below)
• Hello, World!
• Truth-machine
• An interpreter for +-=: AKA a decimal counter with output

3-cube

 thequickbrownfoxjumpsoverthelazydog (Cube) tacit-space-pats-nice-nits

4-cube

, 4-Hadamard graph / Tesseract skeleton in Eodermdrome
   CC0 Salpynx 2019
   Ozone wl ≅ 250nm,
thequickbrownfoxjumpsoverthelazydog four_hadamard; a_mural: half-a-dour-aura-dahl-ham; half-our-hard-lad-rum-foam
abacadabarar-alakazam (Hypercube Magic!) chosen_i_bind_no_zones_'ere_we_win_in_one's_ozone_wl. we_wind_no_hose_so_husks_use_no_humus. oh_i_hone_new_use_sewer_ewes

Computational class

The following program is a Bitwise Cyclic Tag interpreter, proving Eodermdrome to be Turing complete. However, this is in the sense of "at least one universal Turing machine which takes external input can be simulated in Eodermdrome" (see ℒ.) Eodermdrome cannot be Turing-complete in the sense of "Every Turing machine can be mapped to an Eodermdrome program", because there are only a finite number of Eodermdrome programs when I/O matching is not considered.

A version including ASCII drawings of relevant subgraphs is available.

Note: BCT program part should be at least 3 characters long.

thequickbrownfoxjumpsoverthelazydog (Program: ) miewehit
(1) byanad buguramat
(0) byanad buramat
(
) sehened (Data: ) sihiabruramat
(
) ianadabar (Running: ) iamtmabar
abrand (end.
) a
psewelklihiandnabarfrux (1 appended, ) chewelisksiamtmaybobyargruz
psewelklihiandnarfryx (1 not appended, ) chewelisksiamtmargrux
scewelklihiandnabarfrux (0 appended, ) wheliosokoiamtmaybyargruz
scewelklihiandnarfryx (0 not appended, ) wheliosokoiamtmargrux
sceweihiandnarfrux (1 deleted, ) sowoieheiamtmaur
sceweihiandnarfryx (0 deleted, ) sowoieheiamtmaurux

Implementations

Matching rules in Eodermdrome requires solving a variant of the wikipedia:subgraph isomorphism problem. There are a small number of interpreters, all based on Ullmann's algorithm (essentially a brute-force search):

• Proof-of-concept Python interpreter that can run a few commands per second.
• A Haskell interpreter that can run a few hundred commands per second.
• Experimental implementation in Clojure, inspired by the Python version above.

Subgraph isomorphism is NP-complete, so a simple interpreter will take up to exponential time (in the size of the match graphs) for each rewrite step. Improving on this would be an interesting challenge, if one could be bothered to work on it.

External resources

• Blog post by the creator of the Clojure interpreter discussing Kolmogorov-Uspensky Machines in general, and Eodermdrome specifically, with worked 'add' example.

See also

• Kolmogorov machine, an abstract graph-rewriting machine.