Club Amiga de Montreal - CAM/CAM_CD_1.iso/files/171.lha/DME_v1.30/dme-tm.edr

Text File | 1988-04-28 | 6KB | 137 lines

# Macros to make DME simulate a universal Turing Machine
# This is a DME script.  I'm using DME v1.29.
# Written by Jim Blandy, 1988  (O I hope the cancel works...)

# I thought it might be fun to write.  When it worked, my comment was,
# "How gross." :-)
# Take it as a tribute to Mr. Dillon.

# How to work it:
#   SOURCE this file to load in the bindings.  It will bring up two
#    windows with sample Turing machines in them.
#   Put your desired input tape on the first line of the buffer.
#   Leave the second line blank.
#   Put the name of the initial state on the third line.
#   Put the source code for the TM at or below the fourth line:
#    Describe each transition of the tm using the following syntax:
#        state(symbol)=(write-symbol) direction nextstate
#    For example, to say "when in state q and reading symbol x,
#        write a y, move left, and enter state p,"  write
#        `q(x)=(y) < p' (without the quotes).
#    State names can be any non-null alpha-numeric string.
#    Symbols can be any character (I think...)
#    Directions can be < (left) or > (right)
#   Press c-enter (control-keypad enter) to start the TM running; it will
#    run until it reads a symbol it doesn't know what to do with;
#    I just tell it to go to states named `accept' or `reject' so
#    I can tell the difference.
#   To single-step,
#    Press c-nk0  (control-keypad zero) to initialize the head.
#    Press c-nk-  (control-keypad minus) to step the TM through one
#        transition.
#   A 'Pattern not found' message indicates that the TM has halted; the
#    state it died in is left on the third line.
#   I wouldn't recommend trying to flip between single-step and running
#    modes during the same TM run.  Separate runs are okay, of course.
#   I wouldn't be surprised to hear of a better way to do this;  I couldn't
#    think of one, though.  Problems I had to overcome:
#        I was thinking of defining a key for each state, bound to
#        a long ifelse string, where each transition was a recursive
#        call to the next key/state.  Unfortunately, DME won't
#        support recursion past 20 levels, nor will it eliminate
#        tail recursion. :-)  Go for it, Matt!
#        DME doesn't support marks, i.e. variables referring to a
#        position in the buffer;  these would have been very handy.
#        There aren't clean ways to insert $scanf into the buffer or
#        grab the character you're sitting on into $scanf.
#        No multi-line macros.
#   Two sample TMs are included at the end of this file; when you source
#    it, they'll pop up in windows.
#   Coming soon, to be implemented in DME
#    A full lisp
#    Floating point support
#   :-)

# c-nk. - put the character under the cursor in $scanf. (utility routine)
#      This routine fakes a blank at the end of the line.
map c-nk. `ifelse r `` _' left left sc-nk. del del' sc-nk.'

# sc-nk. - subroutine for above
#      the phrase `scanf %1s scanf %c' reads the next character
#      (even if it's a space) into $scanf;  the `scanf %1s' makes
#      sure the scanf buffer is zero-terminated.  :-)
map sc-nk. `scanf %1s scanf %c'

# c-nk7 - read the symbol under the tape head into $scanf
map c-nk7 `goto 1 last find `^' up c-nk.'

# c-nk8 - given symbol in $scanf, set line 3 to `state(symbol)'
map c-nk8 `goto 3 last `(_)' left left left findr `_' $scanf'

# c-nk9 - given current state:symbol pair on line 3, find that transition
map c-nk9 `goto 3 first scanf %[~] find $scanf'

# c-nk4 - read symbol to write for current transition into $scanf
map c-nk4 `c-nk9 find `=(' right right c-nk.'

# c-nk5 - replace the character under the write head with $scanf
#      I go through that findr locution because a 'find-and-replace'
#      operation seems to be the only way to insert the value of
#      $scanf into the buffer.
map c-nk5 `goto 1 last find `^' up ` _' del left left findr `_' $scanf bs'

# c-nk6 - put the cursor on the head direction for the current transition
map c-nk6 `c-nk9 find `=(' find `)' right while c=32 right'

# c-nk1 - if the cursor is on a <, move the head left; otherwise, move
#      it right.
map c-nk1 `ifelse c=60 `goto 2 first del' `goto 2 first ` '''

# c-nk2 - read the current transition's next state into $scanf
map c-nk2 `c-nk9 find `=(' find `)' scanf `)%*[<>]%s''

# c-nk3 - set the current state (line 3) to the contents of $scanf
map c-nk3 `goto 3 first remeol ` _' del left left findr `_' $scanf bs'

# c-nk- - single-step the TM
map c-nk- `c-nk7 c-nk8 c-nk4 c-nk5 c-nk6 c-nk1 c-nk2 c-nk3'

# c-nk0 - initialize the TM
map c-nk0 `goto 2 first remeol `^''

# c-ENTER - the whole shebang.    Given a setup as described above,
# go until you run out of transitions.
map c-ENTER `c-nk0 repeat -1 `c-nk-''


# ==================== Sample TM #1 ====================
topedge 0 height 100 newwindow chfilename `add'
`1111+111' return
return
`start' return
return
`start(1)   =(1) > start     start(+)=(1) > 2nd' return
`2nd(1)     =(1) > 2nd       2nd( )  =( ) < wipelast' return
`wipelast(1)=( ) > done' return
`# sample Turing machine #1 - given a string like 11111+111 (two' return
`# numbers written in base 1), leave their sum on the tape.  For' return
`# the above the result would be 11111111.' return'
top

# ==================== Sample TM #2 ====================
topedge 100 newwindow chfilename `anbn'
`aaaaabbbbb' return
return
`start' return
return
`start(a)=(X) > findb    start( )=( ) > accept' return
`findb(a)=(a) > findb    findb(Y)=(Y) > findb    findb(b)=(Y) < findX' return
`findX(Y)=(Y) < findX    findX(a)=(a) < findX    findX(X)=(X) > nexta' return
`nexta(a)=(X) > findb    nexta(Y)=(Y) > accept' return
`# sample Turing machine #2 - accepts if the string consists of a group'
return
(# of a's followed by the same number of b's, rejects otherwise) return
(# (halting in any state but `accept' means a rejection) ) return
top