Vi macros can simulate a Turing Machine -- try them, they work.
David Hitz
hitz at mips.COM
Tue Feb 16 14:15:55 AEST 1988
To win a bet I wrote a set of vi macros that let vi simulate a Turning
Machine. Since Turing Machines are universal computational devices,
this should settle the editor wars debate for once and for all.
Other editors may have better user interfaces than vi, but they are
certainly no more "powerful".
These macros have been tested on several systems, including versions of
both BSD and SYSV, but since they depend on nits/bugs in vi, some
versions of vi could break them.
The shar file below contains the macros themselves in a file called
tm.uuencode and some turing machine descriptions in files named TM*.
The following sequence executes the TMupdown turing machine.
1) Decode the tm file: $ uudecode tm.uuencode
2) Edit the TM file: $ vi TMupdown
3) Source the macros: :so tm
4) From vi ESC mode, type g (for go): g
I've included three turing machine descriptions. TMupdown just moves
the turing machine tape head up and down. TMabc and TMabc2 both
recognize the pattern of N "a"s followed by N "b"s followed by N "c"s
for any integer N.
The README file describes the format of the Turning Machines themselves.
I have an annotated version of the tm macros for people who care.
--
Dave Hitz
UUCP: {decvax,ucbvax,ihnp4}!decwrl!mips!hitz DDD: hitz at 408-991-0345
#--------------------------------CUT HERE-------------------------------------
#! /bin/sh
#
# This is a shell archive. Save this into a file, edit it
# and delete all lines above this comment. Then give this
# file to sh by executing the command "sh file". The files
# will be extracted into the current directory owned by
# you with default permissions.
#
# The files contained herein are:
#
# -rw-r--r-- 1 hitz 2280 Feb 15 17:22 README
# -rw-r--r-- 1 hitz 983 Feb 15 17:11 tm.uuencode
# -r--r--r-- 1 hitz 513 Mar 14 1987 TMabc
# -rw-r--r-- 1 hitz 536 Mar 25 1987 TMabc2
# -r--r--r-- 1 hitz 130 Mar 14 1987 TMupdown
#
echo 'x - README'
if test -f README; then echo 'shar: not overwriting README'; else
sed 's/^X//' << '________This_Is_The_END________' > README
X
X Vi Turing Machine Emulation
X ---------------------------
X
XThis directory contains a set of macros which allow vi to simulate a
XTuring Machine. The file "tm" contains the macros. The "TM*" files
Xeach contain a turing machine description.
X
XTo execute the TMupdown machine, do the following:
X
X $ vi TMupdown
X :so tm
X
XThen, from escape mode in vi, type 'g' for go.
X
XI've included a simple turing machine description to use as an example
Xin explaining the format.
X
X----------------------- cut here for sample turing machine ---------------------
X
XSTART {####:####:R:DOWN}
XDOWN {up:down:R:DOWN} {%%%%:%%%%:L:UP}
XUP {down:up:L:UP} {####:####:R:DOWN}
X
X####
Xup
Xup
Xup
Xup
X%%%%
X--------------------------- end of turing machine ------------------------------
X
XThe blank top line is used as a scratch pad by the macros and must not
Xbe removed. The lines from the second line to the line containing
X"####" encode the turing machine's state table, and the lines from
X"####" to "%%%%" represent the turing machine's tape.
X
XThe tape is lying on its side such that left is up and right is down.
XEach line represents one tape symbol. "####" is the start symbol on
Xthe tape, and "%%%%" is the end symbol.
X
XEach line above "####" represents the information for one state
Xof the turing machine. I'll describe the format using an example:
X
X DOWN {up:down:R:DOWN} {%%%%:%%%%:L:UP}
X
XThe name of the state, in this case "DOWN", comes first. Following that
Xcomes any number of 4-tuples describing the action to take for a particular
Xtape symbol. The first 4-tuple states that if the current tape symbol
Xis "up", then that symbol should be replaced by "down", the current position
Xon the tape should be moved "R" -- that is, to the right -- and the
Xturing machine should enter the "DOWN" state.
X
XThe general format of these 4-tuples is:
X
X '{' <current symbol> ':' <new symbol> ':' <direction> ':' <next state> '}'
X
XWhere <direction> is "R", "L", or "N" for move left, move right, or no move.
XThe other fields can contain any alpha-numeric string. (In fact, any string
Xthat does not include "{}:" or any vi magic characters will probably work.)
X
XWhen a turing machine first starts, after the 'g' command, it is in the
X"START" state with its head positioned on the "####" symbol on the tape.
________This_Is_The_END________
if test `wc -l < README` -ne 63; then
echo 'shar: README was damaged during transit (should have been 63 bytes)'
fi
fi ; : end of overwriting check
echo 'x - tm.uuencode'
if test -f tm.uuencode; then echo 'shar: not overwriting tm.uuencode'; else
sed 's/^X//' << '________This_Is_The_END________' > tm.uuencode
Xbegin 644 tm
XM;6%P"4,).B`*;6%P"4,).B`)5'5R:6YG($UA8VAI;F4 at 16UU;&%T:6]N($UA
XM8W)O<RX*;6%P"4,).B`*;6%P"4,).B`)5W)I='1E;B`Q.3 at W(&)Y($1A=F4@
XM2&ET>BX@"FUA<`E#"3H@"4QE879E('1H:7,@;F]T:6-E('1O('-A=&ES9GD@
XM;7D at 96=O+ at IM87`)0PDZ(`IM87`)0PDZ"5550U`Z('MD96-V87 at L=6-B=F%X
XM+&EH;G`T?2%D96-W<FPA;6EP<R%H:71Z(`D*;6%P"4,). at E$1$0Z(&AI='I`
XM-#`X+3DY,2TP,S0U"FUA<`E#"3H@"FUA<`E#"3H@"51O('5S92!T:&5S92!M
XM86-R;W,L('9I(&$@5$TL('-O=7)C92!T:&ES(&9I;&4L"FUA<`E#"3H@"6%N
XM9"!T>7!E(")G(B`H9F]R(&=O*2!F<F]M($530R!M;V1E+ at IM87`)0PDZ(`IS
XM970)<F5M87`*;6%P"6<)>%,*;6%P"5,))W1L&#%':W=6=E at G<T!B9CIL;7-7
XM)W1K=VUT3V!S9CIL;7-70&)#8'-F.FQE,4=K=T580&)M;F!S<6!N46US<PIM
XM87`)<PE3"FUA<`E8"2)B60IM87`)&`DB8GDD"FUA<`E7"2)B>70Z"FUA<`EE
XM"2)B>71]"FUA<`EW"2)B4`IM87`)4 at DG="MM=`IM87`)3`DG="UM=`IM87`)
XM3 at DG=&UT"FUA<`E%"5YI+UY;*B!=&PIM87`)0PE>:'(J"FUA<`EC"5YH(&P*
XM;6%P"5$)7FAR*@IM87`)<0D_7"H-7G(@;`IM87`)5 at E)+WL;"FUA<`EV"4$Z
XM&PIM87`)3PE>:2`;"FUA<`EK"19\1`IM87`)>`DZ)7,O7B\@+PTQ1R]>(",C
X8(R,D+PUM=$,Q1R]>(%-405)4+PUM<U$*
X`
Xend
________This_Is_The_END________
if test `wc -l < tm.uuencode` -ne 19; then
echo 'shar: tm.uuencode was damaged during transit (should have been 19 bytes)'
fi
fi ; : end of overwriting check
echo 'x - TMabc'
if test -f TMabc; then echo 'shar: not overwriting TMabc'; else
sed 's/^X//' << '________This_Is_The_END________' > TMabc
X
X
XSTART{####:####:R:check}
Xcheck{a:a:N:find_b}{b:REJECT:N:HALT}{c:REJECT:N:HALT}{%%%%:ACCEPT:N:HALT}
Xfind_b{a:a:R:find_b}{b:b:L:kill_a1}{c:REJECT:N:HALT}{%%%%:REJECT:N:HALT}
Xkill_a1{a:b:R:find_c}
Xfind_c{b:b:R:find_c}{c:c:L:kill_b2}{%%%%:REJECT:N:HALT}
Xkill_b2{b:c:L:kill_b1}
Xkill_b1{b:c:R:find_end}
Xfind_end{c:c:R:find_end}{%%%%:%%%%:L:kill_c3}
Xkill_c3{c:%%%%:L:kill_c2}
Xkill_c2{c:%%%%:L:kill_c1}
Xkill_c1{c:%%%%:L:RETURN}
XRETURN{a:a:L:RETURN}{b:b:L:RETURN}{c:c:L:RETURN}{####:####:N:START}
X
X####
Xa
Xa
Xb
Xb
Xc
Xc
X%%%%
________This_Is_The_END________
if test `wc -l < TMabc` -ne 23; then
echo 'shar: TMabc was damaged during transit (should have been 23 bytes)'
fi
fi ; : end of overwriting check
echo 'x - TMabc2'
if test -f TMabc2; then echo 'shar: not overwriting TMabc2'; else
sed 's/^X//' << '________This_Is_The_END________' > TMabc2
X
XSTART {a:a:L:START} {b:b:L:START} {c:c:L:START} {####:####:R:kill_a}
X {a':a':L:START} {b':b':L:START} {c':c':L:START}
Xkill_a {a:a':R:kill_b} {b:NO:N:NO} {c:NO:N:NO} {%%%%:YES:N:YES}
X {a':a':R:kill_a} {b':b':R:kill_a} {c':c':R:kill_a}
Xkill_b {a:a:R:kill_b} {b:b':R:kill_c} {c:NO:N:NO} {%%%%:NO:N:NO}
X {a':NO:N:NO} {b':b':R:kill_b} {c':NO:N:NO}
Xkill_c {a:NO:N:NO} {b:b:R:kill_c} {c:c':L:START} {%%%%:NO:N:NO}
X {a':NO:N:NO} {b':NO:N:NO} {c':c':R:kill_c}
X
X####
Xa
Xa
Xa
Xb
Xb
Xb
Xc
Xc
Xc
X%%%%
________This_Is_The_END________
if test `wc -l < TMabc2` -ne 21; then
echo 'shar: TMabc2 was damaged during transit (should have been 21 bytes)'
fi
fi ; : end of overwriting check
echo 'x - TMupdown'
if test -f TMupdown; then echo 'shar: not overwriting TMupdown'; else
sed 's/^X//' << '________This_Is_The_END________' > TMupdown
X
X
XSTART{####:####:R:DOWN}
XDOWN{up:down:R:DOWN}{%%%%:%%%%:L:UP}
XUP{down:up:L:UP}{####:####:R:DOWN}
X
X####
Xup
Xup
Xup
Xup
Xup
Xup
Xup
X%%%%
________This_Is_The_END________
if test `wc -l < TMupdown` -ne 15; then
echo 'shar: TMupdown was damaged during transit (should have been 15 bytes)'
fi
fi ; : end of overwriting check
exit 0
--
Dave Hitz
UUCP: {decvax,ucbvax,ihnp4}!decwrl!mips!hitz DDD: hitz at 408-991-0345
More information about the Comp.unix.wizards
mailing list