Turing machine sim. in sendmail

[Peter van Heusden]

I don't know if this has been done before, but just as a challenge (and
for the historical value of it all), I decided to see if I could write
a Turing Machine in sendmail. Well, I did! Below is the code for a
Turing Machine which does substraction. (Of course, it would be better
to write something more flexible - i.e. something which parses some
abstract representation of a state machine and executes it - but that's
left as an exercise for the reader)

The input format for the machine is a tape as follows:

X X X X

where X is a 1 or 0. The counting system is unary, so 1 is 1, 2 is 1 1,
3 is 1 1 1, and so forth. The tapes for this machine should be in the form

Number A 0 Number B

where Number A is bigger than Number B, e.g.

1 1 0 1

Once you've got a tape, run it through tStart in rule-testing mode, i.e.

tStart 1 1 0 1

the output is the same format as the input. BTW. a 'N' character is a
blank (i.e. non-defined) space on the tape.

Finally, doing any meaningful calculation with this machine is going to
stress your sendmail's recursion - you might consider upping the recursion
limit by changing MAXRULERECURSION in conf.c in the sendmail source, and
recompiling (at least that works for my sendmail 8.8.8).

Have fun,
Peter

# turing machine - starting point, converts input into internal rep. and
# starts at the first state of substraction machine
StStart
R$* $: $>tInput $1
R$* $@ $>tPass $1

# turing machine - move the tape right
StR
RN ! N ! $* M $* $@ $1 ! N ! $2
RN ! N ! $* $@ $1 ! N ! N
R$* ! N ! $* M $* $@ $2 ! $1 ! $3
R$* ! N ! $* $@ $2 ! $1 ! N
R$* ! $* ! $* M $* $@ $3 ! $1 M $2 ! $4
R$* ! $* ! $* $@ $3 ! $1 M $2 ! N

# turing machine - move the tape left
StL
R$* ! $* M $* ! $* $@ $2 ! $3 ! $1 M $4
RN ! N ! $* $@ N ! N ! $1
R$* ! N ! $* $@ N ! N ! $1 M $2
R$* ! $* ! $* $@ $2 ! N ! $1 M $3

# turing machine - convert input of the form X X X X to internal
# tape representation
StInput
R$- $* $@ $1 ! N ! $>tAddMark $2

StAddMark
R$- $+ $@ $1 M $>tAddMark $2

# turing machine - convert internal tape representation to the form
# X X X X
StOutput
R$* ! $* ! $* $: $1 ! $3 ! $>tReverse $2 S
R$* ! $* ! $* $: $1 ! $2 ! $>tStripMark $3
R$* ! $* ! $* $: $1 ! $3 ! $>tStripMark $2
R$* ! $* ! $* $@ $2 $1 $3

StReverse
R$- S $@ $1
R$* M $* M $- S $+ $@ $>tReverse $2 M $3 S $1 M $4
R$* M $* M $- S $@ $>tReverse $2 M $3 S $1
R$* M $* S $+ $@ $2 M $1 M $3
R$* M $* S $@ $2 M $1

StStripMark
R$* M $+ $@ $>tStripMark $1 $2

# state machine for doing subtraction

# turing machine - go past the initial 1's
StPass
R1 $* $@ $>tPassMatchOne 1 $1
R0 $* $@ $>tPassMatchZero 0 $1

StPassMatchOne
R$* $: $>tR $1
R$* $@ $>tPass $1

StPassMatchZero
R$* $: $>tR $1
R$* $@ $>tFind2nd $1

# turing machine - find the start of the 2nd number, chop off a 1, and
# reverse direction
StFind2nd
R0 $* $@ $>tFind2ndMatchZero 0 $1
R1 $* $@ $>tFind2ndMatchOne 0 $1
RN $* $@ $>tFind2ndMatchBlank N $1

StFind2ndMatchZero
R$* $: $>tR $1
R$* $@ $>tFind2nd $1

StFind2ndMatchOne
R$* $: $>tL $1
R$* $@ $>tDelete $1

StFind2ndMatchBlank
R$* $: $>tL $1
R$* $@ $>tOutput $1

# turing machine - reverse the tape till you find a 1, and delete it
StDelete
R0 $* $@ $>tDeleteMatchZero 0 $1
R1 $* $@ $>tDeleteMatchOne 0 $1

StDeleteMatchZero
R$* $: $>tL $1
R$* $@ $>tDelete $1

StDeleteMatchOne
R$* $: $>tR $1
R$* $@ $>tFind2nd $1

--
Peter van Heusden p...@leftside.uwc.ac.za