# Andrei Machine 9000

The Andrei Machine 9000 is an esoteric programming language, based on the observation that Kolmogorov is hard to remember. It is based on a Kolmogorov machine.

## Language overview

The Andrei Machine 9000 is based on the original Kolmogorov machine. It consists of an undirected graph, where each node is of type Ti, i being an integer. A node cannot be surrounded by nodes of the same type.

The following types have a particular meaning :

• 0 : There must be one and only one node of type 0 during the execution of the program (related to the transformation rules and I/O)
• 1 : When the node 0 is transformed into 1, the program halts.
• 2 : Increase the register.
• 3 : Empty the register.
• 4 : Output the value of the register.
• 5 : Input (see below for 2 through 5)

For convenience purpose, nodes can also be of a type "x", where x can be any character.

The other part of the program is a set of transformation rules to be applied on the graph. It turns the active part of a graph into another graph, the inactive part remaining unchanged. The active part consists of a graph (possibly unconnected) containing the node 0. The inactive part is the rest of the graph, also possibly unconnected (though the union of the two is connected). The intersection of the two is the boundary, which does not change during the transformation. It only contains nodes, no edges.

For instance :

The first rectangle represents the active zone, the second represent the boundary, and all nodes outside are in the inactive part. The transformation rules only need the two rectangles, and the machine will search if the graph contains them.

## Input-Output

After every transformations, the interpreter (if it one day exists) will travel the graph, from 0 (or 1) to the next node. If more than one node can be the next, it will chose the node with the lowest type. Nodes of type "x" are considered higher than any other type.

For every node of type 2 that it encounters, it will increase a register, zero it for a node of type 3, and set it to the value of x for a node of type "x". A node of type 4 will then output it to the screen.

The nodes of type 5 will wait for input from the keyboard, and change into a linear graph of the form i-j-k-i-j-k-i-...-j-k-i, where i appears n times, n being the ASCII value of the input. i, j and k can be of any type (though different, and i should be different than the surrounding nodes), although it can be useful to use i as type 2 (since it doesn't have any other effects if no output is present).

## Syntax

The language defines each graph as a list of n nodes, and then n² relations on it (a table of the relations between all nodes, with 0 if there is no edge or 1 otherwise). The relations give n² binary digits, with then 1 placed in front and converted to base 32 to save space. If the graph is completely linear, - can be used instead.

A graph is then written as a list of nodes, separated by dashes, and preceded by * if they're part of the boundary, and the number for the relations, the two being separated by commas. If the graph is unconnected, the pieces of the graph should be separated by strokes. The graph is then written as the list of nodes and the digits representing the relations, separated by a comma. If the nodes are actually linear, - can be used instead of the digits.

A program is composed of the initial graph, and a list of transformation rules, separated by semi-colons. A transformation rules is composed of two graphs, [active zone of to be transformed]>[new graph]

## Examples

```0,-;0,->1-"H"-4-6-"e"-4-6-"l"-4-6-"l"-4-6-"o"-4-6-","-4-6-" "-4-6-"w"-4-"o"-4-6-"r"-4-6-"l"-4-6-"d"-4-6-"!"-4
```
```0-5-4,-;0-4,->0-5-4,-;0-*2|*2-4,->0-*2|*2,-;0-2-6-7-2-4,->0-5-4,-;0-2,->0-5-4,-;0-2-6-7-*2,->0-*2,-
```

4-Hadamard graph / 4-cube skeleton. This is simply an initial state, without any transformations, but demonstrates the base 32 encoding of non-linear graphs.

```0-2-3-6-7-8-9-10-11-12-13-14-15-16-17-18,2m08kg2540l1062o0ii04kg1k408b02a80ii06go11a098g2a40q
```