From: pvh@leftside.wcape.school.za (Peter van Heusden) Newsgroups: alt.sysadmin.recovery Subject: Turing Machine in Sendmail (v. 2) Date: 18 Sep 1998 07:29:44 GMT Organization: Adamastor Message-ID: X-Newsreader: slrn (0.9.5.2 UNIX) After posting my initial efforts at creating a Turing Machine simulator in sendmail, I had another look at it, and now I present to the world a generalised Turing Machine simulator, written entirely in sendmail! The sendmail.cf rulesets below implement the machine. To run it, all you need is a state machine representation, and sendmail's rule testing mode. For example, here is a state machine to substract two numbers expressed in unary form - i.e. given 1 1 1 1 0 1 1, the result would be 1 1. 1 0 M R M 2 ! 1 M R M 1 ! H M H M H 2 0 M R M 2 ! 0 M L M 3 ! H M H M H 3 0 M L M 3 ! 0 M R M 2 ! H M H M H compile this into a map with the command 'makemap hash turing ' where tape is a sequence like that shown about (or read the rulesets for more info). If you try anything more than say 3 - 2, your sendmail will probably hit a recursion limit - read the ruleset for info on that. Of course, this proves that sendmail can do ANYTHING. Anyone going to write an operating system in sendmail now? Peter P.S. check the ruleset for line wraps before you use it, and replace spaces with tabs appropriately (i.e. between each LHS and RHS of each rule, and between the RHS of the rule and the comment) # turing machine - implement a turing machine simulator # machine representations: # # alphabet: # 1, 0 and blank (N) # # state machine input map: # ! ! # where is a number, and each is a representation # of the decisions made for matching that particular symbol on tape, of # the form < ReplaceChar M MoveDir M NextState >, where ReplaceChar is # the symbol to replace the symbol at the current position with, MoveDir # is either L or R for moving either left or right, and NextState is # the number of the next state to go into. # # tape input representation: # # where X is a symbol in the alphabet # # tape internal representation: # ! ! # where is the symbol currently under the head, # is the tape the the left of the head, with # symbols from right to left (i.e. symbol closest to the head first), # in the form i.e. symbols seperated by the char M # is the tape to the right of the head, with symbols # from left to right (i.e. symbol closest to the head first), in the # same format as tape the the left of the head. # # the total internal representation is then (initially): # T # # an example of a state machine: # # 1 H M H M H ! 0 M R M 1 ! H M H M H # # this state machine clears the 1's on a tape (by writing 0's) until # it finds a 0 or the end of tape. The H M H M H states ares halt # states, which must be specified if no action is defined for that # particular symbol. # # to run this tape, you'd create the turing map (using # 'makemap hash turing <') and then load the config file # in rule test mode. To start the machine, enter 'tStart ', e.g. # 'tStart 1 1 1 1 0 1 1'. Your output should be '0 0 0 0 0 1 1'. # # NOTE: for any significant amount of data, you will probably # max out sendmail's recursion limit. To get around this, change # the MAXRULERECURSION constant in the sendmail source's conf.c, and # recompile sendmail (at least that works for my sendmail 8.8.8). # Turing machine state machine map Kturing hash -o /home/pvh/src/mysrc/turing/turing # # turing machine - starting point, converts input into internal rep. and # starts at the first state of substraction machine StStart R$* $: $>tInputTape $1 R$* $: $1 T $>tInputStateMachine $(turing 1 $: NOTFOUND 1 $) R$* NOTFOUND . $- $@ $#error $: No state $2 defined! R$* $@ $>tReadTape $1 StEnd R$* T $* $@ $>tOutputTape $2 # 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 - read in turing machine's state machine rep. and # strip comments StInputStateMachine R$* C $* $@ $1 # turing machine - convert input of the form X X X X to internal # tape representation StInputTape R$- $* $@ $1 ! N ! $>tAddMark $2 StAddMark R$- $+ $@ $1 M $>tAddMark $2 # turing machine - convert internal tape representation to the form # X X X X StOutputTape 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 StReadTape R0 ! $* $@ $>tZeroOnTape 0 ! $1 R1 ! $* $@ $>tOneOnTape 1 ! $1 RN ! $* $@ $>tBlankOnTape N ! $1 StZeroOnTape R$* T $* ! $* ! $* $: $2 C $2 ! $3 ! $4 T $1 focus on state 1 R$* $@ $>tParseState $1 StOneOnTape R$* T $* ! $* ! $* $: $3 C $2 ! $3 ! $4 T $1 focus on state 1 R$* $@ $>tParseState $1 StBlankOnTape R$* T $* ! $* ! $* $: $4 C $2 ! $3 ! $4 T $1 focus on state 1 R$* $@ $>tParseState $1 StParseState RH $* $@ $>tEnd $1 detect halt case R$* $: $>tChangeTape $1 R$* M $* M $* C $* T $* $: $2 S $1 M $2 M $3 C $4 T $5 R$* $: $>tMoveTape $1 R$* T $* $: $2 T $1 R$* T $* M $* M $* C $* $: $1 T $>tInputStateMachine $(turing $4 $: NOTFOUND $4 $) R$* NOTFOUND . $- $@ $#error $: No state $2 defined! R$* $@ $>tReadTape $1 StChangeTape R$* M $* M $* C $* T $* ! $* $@ $1 M $2 M $3 C $4 T $1 ! $6 StMoveTape RL S $* T $* $@ $1 T $>tL $2 RR S $* T $* $@ $1 T $>tR $2 -- Peter van Heusden | Its the 90's, and collective action is STILL cool! pvh@leftside.wcape.school.za | Get active in your union today!