blandy@awamore.cs.cornell.edu (Jim Blandy) (08/03/88)
# 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
--
Jim Blandy - blandy@crnlcs.bitnet
"And now," cried Max, "let the wild rumpus start!"