home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume2 / vi-turing < prev    next >
Internet Message Format  |  1991-08-07  |  9KB
  1. From: hitz@mips.COM (David Hitz)
  2. Newsgroups: comp.sources.misc
  3. Subject: v02i057: vi macros simulate a Turing Machine
  4. Message-ID: <7240@ncoast.UUCP>
  5. Date: 18 Feb 88 02:32:40 GMT
  6. Approved: allbery@ncoast.UUCP
  7.  
  8. Comp.sources.misc: Volume 2, Issue 57
  9. Submitted-By: "David Hitz" <hitz@mips.COM>
  10. Archive-Name: vi-turing
  11.  
  12. [A posting true to the intent of this newsgroup.  ++bsa]
  13.  
  14. To win a bet I wrote a set of vi macros that let vi simulate a Turing
  15. Machine.  Since Turing Machines are universal computational devices,
  16. this should settle the editor wars debate for once and for all.
  17.  
  18. Other editors may have better user interfaces than vi, but they are
  19. certainly no more "powerful".
  20.  
  21. These macros have been tested on several systems, including versions of
  22. both BSD and SYSV, but since they depend on nits/bugs in vi, some
  23. versions of vi could break them.
  24.  
  25. The shar file below contains the macros themselves in a file called
  26. tm.uuencode and some turing machine descriptions in files named TM*.  
  27.  
  28. The following sequence executes the TMupdown turing machine.
  29.  
  30.     1) Decode the tm file:            $ uudecode tm.uuencode
  31.     2) Edit the TM file:            $ vi TMupdown
  32.     3) Source the macros:            :so tm
  33.     4) From vi ESC mode, type g (for go):    g
  34.  
  35. I've included three turing machine descriptions.  TMupdown just moves
  36. the turing machine tape head up and down.  TMabc and TMabc2 both
  37. recognize the pattern of N "a"s followed by N "b"s followed by N "c"s
  38. for any integer N.
  39.  
  40. The README file describes the format of the Turing Machines themselves.
  41. I have an annotated version of the tm macros for people who care.
  42.  
  43. --
  44. Dave Hitz
  45. UUCP: {decvax,ucbvax,ihnp4}!decwrl!mips!hitz     DDD: hitz@408-991-0345
  46.  
  47.  
  48. #--------------------------------CUT HERE-------------------------------------
  49. #! /bin/sh
  50. #
  51. # This is a shell archive.  Save this into a file, edit it
  52. # and delete all lines above this comment.  Then give this
  53. # file to sh by executing the command "sh file".  The files
  54. # will be extracted into the current directory owned by
  55. # you with default permissions.
  56. #
  57. # The files contained herein are:
  58. #
  59. # -rw-r--r--  1 hitz         2280 Feb 15 17:22 README
  60. # -rw-r--r--  1 hitz          983 Feb 15 17:11 tm.uuencode
  61. # -r--r--r--  1 hitz          513 Mar 14  1987 TMabc
  62. # -rw-r--r--  1 hitz          536 Mar 25  1987 TMabc2
  63. # -r--r--r--  1 hitz          130 Mar 14  1987 TMupdown
  64. #
  65. echo 'x - README'
  66. if test -f README; then echo 'shar: not overwriting README'; else
  67. sed 's/^X//' << '________This_Is_The_END________' > README
  68. X
  69. X            Vi Turing Machine Emulation
  70. X            ---------------------------
  71. X
  72. XThis directory contains a set of macros which allow vi to simulate a
  73. XTuring Machine.  The file "tm" contains the macros.  The "TM*" files
  74. Xeach contain a turing machine description.
  75. X
  76. XTo execute the TMupdown machine, do the following:
  77. X
  78. X    $ vi TMupdown
  79. X    :so tm
  80. X
  81. XThen, from escape mode in vi, type 'g' for go.
  82. X
  83. XI've included a simple turing machine description to use as an example
  84. Xin explaining the format.
  85. X
  86. X----------------------- cut here for sample turing machine ---------------------
  87. X
  88. XSTART    {####:####:R:DOWN}
  89. XDOWN    {up:down:R:DOWN}    {%%%%:%%%%:L:UP}
  90. XUP    {down:up:L:UP}        {####:####:R:DOWN}
  91. X
  92. X####
  93. Xup
  94. Xup
  95. Xup
  96. Xup
  97. X%%%%
  98. X--------------------------- end of turing machine ------------------------------
  99. X
  100. XThe blank top line is used as a scratch pad by the macros and must not
  101. Xbe removed. The lines from the second line to the line containing
  102. X"####" encode the turing machine's state table, and the lines from
  103. X"####" to "%%%%" represent the turing machine's tape.
  104. X
  105. XThe tape is lying on its side such that left is up and right is down.
  106. XEach line represents one tape symbol.  "####" is the start symbol on
  107. Xthe tape, and "%%%%" is the end symbol.
  108. X
  109. XEach line above "####" represents the information for one state
  110. Xof the turing machine.   I'll describe the format using an example:
  111. X
  112. X    DOWN    {up:down:R:DOWN}    {%%%%:%%%%:L:UP}
  113. X
  114. XThe name of the state, in this case "DOWN", comes first.  Following that
  115. Xcomes any number of 4-tuples describing the action to take for a particular
  116. Xtape symbol.   The first 4-tuple states that if the current tape symbol
  117. Xis "up", then that symbol should be replaced by "down", the current position
  118. Xon the tape should be moved "R" -- that is, to the right -- and the
  119. Xturing machine should enter the "DOWN" state.
  120. X
  121. XThe general format of these 4-tuples is:
  122. X
  123. X   '{' <current symbol> ':' <new symbol> ':' <direction> ':' <next state> '}'
  124. X
  125. XWhere <direction> is "R", "L", or "N" for move left, move right, or no move.
  126. XThe other fields can contain any alpha-numeric string.  (In fact, any string
  127. Xthat does not include "{}:" or any vi magic characters will probably work.)
  128. X
  129. XWhen a turing machine first starts, after the 'g' command, it is in the
  130. X"START" state with its head positioned on the "####" symbol on the tape.
  131. ________This_Is_The_END________
  132. if test `wc -l < README` -ne 63; then
  133.     echo 'shar: README was damaged during transit (should have been 63 bytes)'
  134. fi
  135. fi        ; : end of overwriting check
  136. echo 'x - tm.uuencode'
  137. if test -f tm.uuencode; then echo 'shar: not overwriting tm.uuencode'; else
  138. sed 's/^X//' << '________This_Is_The_END________' > tm.uuencode
  139. Xbegin 644 tm
  140. XM;6%P"4,).B`*;6%P"4,).B`)5'5R:6YG($UA8VAI;F4@16UU;&%T:6]N($UA
  141. XM8W)O<RX*;6%P"4,).B`*;6%P"4,).B`)5W)I='1E;B`Q.3@W(&)Y($1A=F4@
  142. XM2&ET>BX@"FUA<`E#"3H@"4QE879E('1H:7,@;F]T:6-E('1O('-A=&ES9GD@
  143. XM;7D@96=O+@IM87`)0PDZ(`IM87`)0PDZ"5550U`Z('MD96-V87@L=6-B=F%X
  144. XM+&EH;G`T?2%D96-W<FPA;6EP<R%H:71Z(`D*;6%P"4,).@E$1$0Z(&AI='I`
  145. XM-#`X+3DY,2TP,S0U"FUA<`E#"3H@"FUA<`E#"3H@"51O('5S92!T:&5S92!M
  146. XM86-R;W,L('9I(&$@5$TL('-O=7)C92!T:&ES(&9I;&4L"FUA<`E#"3H@"6%N
  147. XM9"!T>7!E(")G(B`H9F]R(&=O*2!F<F]M($530R!M;V1E+@IM87`)0PDZ(`IS
  148. XM970)<F5M87`*;6%P"6<)>%,*;6%P"5,))W1L&#%':W=6=E@G<T!B9CIL;7-7
  149. XM)W1K=VUT3V!S9CIL;7-70&)#8'-F.FQE,4=K=T580&)M;F!S<6!N46US<PIM
  150. XM87`)<PE3"FUA<`E8"2)B60IM87`)&`DB8GDD"FUA<`E7"2)B>70Z"FUA<`EE
  151. XM"2)B>71]"FUA<`EW"2)B4`IM87`)4@DG="MM=`IM87`)3`DG="UM=`IM87`)
  152. XM3@DG=&UT"FUA<`E%"5YI+UY;*B!=&PIM87`)0PE>:'(J"FUA<`EC"5YH(&P*
  153. XM;6%P"5$)7FAR*@IM87`)<0D_7"H-7G(@;`IM87`)5@E)+WL;"FUA<`EV"4$Z
  154. XM&PIM87`)3PE>:2`;"FUA<`EK"19\1`IM87`)>`DZ)7,O7B\@+PTQ1R]>(",C
  155. X8(R,D+PUM=$,Q1R]>(%-405)4+PUM<U$*
  156. X`
  157. Xend
  158. ________This_Is_The_END________
  159. if test `wc -l < tm.uuencode` -ne 19; then
  160.     echo 'shar: tm.uuencode was damaged during transit (should have been 19 bytes)'
  161. fi
  162. fi        ; : end of overwriting check
  163. echo 'x - TMabc'
  164. if test -f TMabc; then echo 'shar: not overwriting TMabc'; else
  165. sed 's/^X//' << '________This_Is_The_END________' > TMabc
  166. X
  167. X
  168. XSTART{####:####:R:check}
  169. Xcheck{a:a:N:find_b}{b:REJECT:N:HALT}{c:REJECT:N:HALT}{%%%%:ACCEPT:N:HALT}
  170. Xfind_b{a:a:R:find_b}{b:b:L:kill_a1}{c:REJECT:N:HALT}{%%%%:REJECT:N:HALT}
  171. Xkill_a1{a:b:R:find_c}
  172. Xfind_c{b:b:R:find_c}{c:c:L:kill_b2}{%%%%:REJECT:N:HALT}
  173. Xkill_b2{b:c:L:kill_b1}
  174. Xkill_b1{b:c:R:find_end}
  175. Xfind_end{c:c:R:find_end}{%%%%:%%%%:L:kill_c3}
  176. Xkill_c3{c:%%%%:L:kill_c2}
  177. Xkill_c2{c:%%%%:L:kill_c1}
  178. Xkill_c1{c:%%%%:L:RETURN}
  179. XRETURN{a:a:L:RETURN}{b:b:L:RETURN}{c:c:L:RETURN}{####:####:N:START}
  180. X
  181. X####
  182. Xa
  183. Xa
  184. Xb
  185. Xb
  186. Xc
  187. Xc
  188. X%%%%
  189. ________This_Is_The_END________
  190. if test `wc -l < TMabc` -ne 23; then
  191.     echo 'shar: TMabc was damaged during transit (should have been 23 bytes)'
  192. fi
  193. fi        ; : end of overwriting check
  194. echo 'x - TMabc2'
  195. if test -f TMabc2; then echo 'shar: not overwriting TMabc2'; else
  196. sed 's/^X//' << '________This_Is_The_END________' > TMabc2
  197. X
  198. XSTART    {a:a:L:START}    {b:b:L:START}    {c:c:L:START}    {####:####:R:kill_a}
  199. X    {a':a':L:START}  {b':b':L:START}  {c':c':L:START}
  200. Xkill_a    {a:a':R:kill_b}  {b:NO:N:NO}       {c:NO:N:NO}       {%%%%:YES:N:YES}
  201. X    {a':a':R:kill_a} {b':b':R:kill_a} {c':c':R:kill_a}
  202. Xkill_b    {a:a:R:kill_b}   {b:b':R:kill_c}  {c:NO:N:NO}       {%%%%:NO:N:NO}
  203. X    {a':NO:N:NO}     {b':b':R:kill_b} {c':NO:N:NO}
  204. Xkill_c    {a:NO:N:NO}       {b:b:R:kill_c}   {c:c':L:START}   {%%%%:NO:N:NO}
  205. X    {a':NO:N:NO}     {b':NO:N:NO}     {c':c':R:kill_c}
  206. X
  207. X####
  208. Xa
  209. Xa
  210. Xa
  211. Xb
  212. Xb
  213. Xb
  214. Xc
  215. Xc
  216. Xc
  217. X%%%%
  218. ________This_Is_The_END________
  219. if test `wc -l < TMabc2` -ne 21; then
  220.     echo 'shar: TMabc2 was damaged during transit (should have been 21 bytes)'
  221. fi
  222. fi        ; : end of overwriting check
  223. echo 'x - TMupdown'
  224. if test -f TMupdown; then echo 'shar: not overwriting TMupdown'; else
  225. sed 's/^X//' << '________This_Is_The_END________' > TMupdown
  226. X
  227. X
  228. XSTART{####:####:R:DOWN}
  229. XDOWN{up:down:R:DOWN}{%%%%:%%%%:L:UP}
  230. XUP{down:up:L:UP}{####:####:R:DOWN}
  231. X
  232. X####
  233. Xup
  234. Xup
  235. Xup
  236. Xup
  237. Xup
  238. Xup
  239. Xup
  240. X%%%%
  241. ________This_Is_The_END________
  242. if test `wc -l < TMupdown` -ne 15; then
  243.     echo 'shar: TMupdown was damaged during transit (should have been 15 bytes)'
  244. fi
  245. fi        ; : end of overwriting check
  246. exit 0
  247. -- 
  248. Dave Hitz
  249. UUCP: {decvax,ucbvax,ihnp4}!decwrl!mips!hitz     DDD: hitz@408-991-0345
  250.