Markov Computation

Markov computation is an attractively simple definition of universal computability.

A program is a list of rewrite rules:

xxx => yyy

or a terminal rule:

xxx =>. yyy

where xxx and yyy are arbitrary strings over some alphabet.

A computation takes a string over that alphabet and repeatedly rewrites it until termination: each rewrite uses the first rule with a LHS occuring anywhere in the string, which is then replaced by the RHS of the rule. If the rule is terminal the computation stops, it also stops if no rule matches.

Since I had a need to brush up on my Perl recently, I came up with this:

#!/usr/bin/perl -w
use strict;

my $line = shift @ARGV;
my @rules;

while (<>) {
    if (/^\s*(\S*)\s*=>(\.?)\s*(\S*)/) {
        push @rules,[$1,length $1,$3,$2 ne ""];
    }
}

print "$line\n";
for (my $i = 0; $i < @rules; ) {
     my ($lhs,$len,$rhs,$term) = @{$rules[$i++]};
     my $ix = index $line,$lhs;
     if ($ix >= 0) {
        substr($line,$ix,$len) = $rhs;
        print "$line\n";
        $i = $term?@rules:0;
     }
}

The line to rewrite is given as a command line argument and the program is read from input (either stdin or from files given on the command line). We use some regexps to match the program lines and, while it’s tempting to use regexp rewriting for running the program, we want to avoid any string characters being interpreted specially – we can use quotemeta for this but here we just use the non-regexp string operators (note the slightly wacky Perl use of substr as an l-value).

Now we have our evaluator, let’s write some programs:

Here is a multiplication program:

$ cat mult.mkv
x1 => 1x
x| => |1
x => |1
+| => |
+1 => 1+x
1* => *+
*1 => *
*| =>

$ ./markov '111*11' mult.mkv
111*11
11*+11
11*1+x1
11*1+1x
11*1+1|1
11*11+x|1
11*11+|11
11*11|11
1*+11|11
1*1+x1|11
1*1+1x|11
1*1+1|111
1*11+x|111
1*11+|1111
1*11|1111
*+11|1111
*1+x1|1111
*1+1x|1111
*1+1|11111
*11+x|11111
*11+|111111
*11|111111
*1|111111
*|111111
111111

Add small Roman numerals:

$ cat roman.mkv
# Final change to subtractive form
@X => X@
@IIII =>. IV
@VIIII =>. IX
@ =>.
# Initial expansion of subtractive form
IV => IIII
IX => VIIII
# Simplification
IIIII => V
VV => X
# Rules for *
I*X => XI*
I*V => VI*
V*X => XV*
* =>
# Move from LHS to RHS
I+I => II
V+I => VI
V+V => X
X+ => X
I+ => +I*
V+ => +V*
# Go to finish
+ => @

$ ./markov I+II+III+IV+V+VI+VII+VIII+IX+X < roman.mkv
I+II+III+IV+V+VI+VII+VIII+IX+X
I+II+III+IIII+V+VI+VII+VIII+IX+X
I+II+III+IIII+V+VI+VII+VIII+VIIII+X
III+III+IIII+V+VI+VII+VIII+VIIII+X
IIIIII+IIII+V+VI+VII+VIII+VIIII+X
VI+IIII+V+VI+VII+VIII+VIIII+X
VIIIII+V+VI+VII+VIII+VIIII+X
VV+V+VI+VII+VIII+VIIII+X
X+V+VI+VII+VIII+VIIII+X
X+XI+VII+VIII+VIIII+X
XXI+VII+VIII+VIIII+X
XX+I*VII+VIII+VIIII+X
XX+VI*II+VIII+VIIII+X
XX+VIII+VIII+VIIII+X
XXVIII+VIII+VIIII+X
XXVII+I*VIII+VIIII+X
XXVII+VI*III+VIIII+X
XXVII+VIIII+VIIII+X
XXVI+I*VIIII+VIIII+X
XXVI+VI*IIII+VIIII+X
XXVI+VIIIII+VIIII+X
XXVI+VV+VIIII+X
XXVI+X+VIIII+X
XXVI+XVIIII+X
XXV+I*XVIIII+X
XXV+XI*VIIII+X
XXV+XVI*IIII+X
XXV+XVIIIII+X
XXV+XVV+X
XXV+XX+X
XXV+XXX
XX+V*XXX
XX+XV*XX
XX+XXV*X
XX+XXXV*
XX+XXXV
XXXXXV

And here is one for checking the Collatz conjecture:

$ cat collatz.mkv
>11 => 1>
>1 => <111
> =>
1< => <111111
< => 1
11 => >11

$ ./markov 11111 collatz.mkv
11111
>11111
1>111
11>1
11<111
1<111111111
1111111111111111
1>11111111111111
11>111111111111
111>1111111111
1111>11111111
11111>111111
111111>1111
1111111>11
11111111>
11111111
>11111111
1>111111
11>1111
111>11
1111>
1111
>1111
1>11
11>
11
>11
1>
1

See the 1st edition of Mendelson’s excellent book on Mathematical Logic for a full treatment, including a demonstration of equivalence with other notions of computability.