# Markov Computation

**Posted:**January 8, 2014

**Filed under:**Uncategorized Leave a comment

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.