// turing machine in rmutt

program: (
 init    // initialize tape
 display // display initial contents / head position of tape
 s0      // enter first state; this will only return if the TM halts
 display // display final contents / head position of tape
);

// the following example implements the following TM:

// [s0, 0, s0, 0, >>]
// [s0, 1, s1, 0, <<]
// [s1, 0, s2, 1, >>]
// [s1, 1, s2, 1, >>]
// [s2, 0, s3, 0, >>]
// [s2, 1, s3, 0, >>]
// [s3, 0, s4, 1, <<]
// [s3, 1, s4, 1, <<]
// s4: halt

// which moves right along the tape until it finds a 1,
// moves left, writes 101, moves left, and halts.

// implementation of the example TM
s0: head > ("0" % (w0 R s0)
            "1" % (w0 L s1));
s1: head > ("0" % (w1 R s2)
            "1" % (w1 R s2));
s2: head > ("0" % (w0 R s3)
            "1" % (w1 R s3));
s3: head > ("0" % (w1 L s4)
            "1" % (w1 L s4));
s4: ; // halt state

// set up the initial state of the tape
init:
[$left = "0000"]       // portion of the tape to the left of the r/w head
[$head = "0"]          // symbol at the r/w head
[$right = "000000100"] // portion of the tape to the right of the r/w head
;

// produce text representation of tape and r/w head
display:
left "[" head "]" right "\n"
;

// move the r/w head one cell to the left
L:
[swap = head]
[$head = left > /.*(.)/\1/]
[$left = left > /(.*)./\1/]
[$right = swap right]
;

// move the r/w head one cell to the right
R:
[$swap = head]
[$head = right > /(.).*/\1/]
[$right = right > /.(.*)/\1/]
[$left = left swap]
;

// write a "0" at the r/w head
w0: [$head = "0"];

// write a "1" at the r/w head
w1: [$head = "1"];