home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 171.lha / DME_v1.30 / dme-tm.edr < prev    next >
Encoding:
Text File  |  1988-04-28  |  5.6 KB  |  137 lines
  1. # Macros to make DME simulate a universal Turing Machine
  2. # This is a DME script.  I'm using DME v1.29.
  3. # Written by Jim Blandy, 1988  (O I hope the cancel works...)
  4.  
  5. # I thought it might be fun to write.  When it worked, my comment was,
  6. # "How gross." :-)
  7. # Take it as a tribute to Mr. Dillon.
  8.  
  9. # How to work it:
  10. #   SOURCE this file to load in the bindings.  It will bring up two
  11. #    windows with sample Turing machines in them.
  12. #   Put your desired input tape on the first line of the buffer.
  13. #   Leave the second line blank.
  14. #   Put the name of the initial state on the third line.
  15. #   Put the source code for the TM at or below the fourth line:
  16. #    Describe each transition of the tm using the following syntax:
  17. #        state(symbol)=(write-symbol) direction nextstate
  18. #    For example, to say "when in state q and reading symbol x,
  19. #        write a y, move left, and enter state p,"  write
  20. #        `q(x)=(y) < p' (without the quotes).
  21. #    State names can be any non-null alpha-numeric string.
  22. #    Symbols can be any character (I think...)
  23. #    Directions can be < (left) or > (right)
  24. #   Press c-enter (control-keypad enter) to start the TM running; it will
  25. #    run until it reads a symbol it doesn't know what to do with;
  26. #    I just tell it to go to states named `accept' or `reject' so
  27. #    I can tell the difference.
  28. #   To single-step,
  29. #    Press c-nk0  (control-keypad zero) to initialize the head.
  30. #    Press c-nk-  (control-keypad minus) to step the TM through one
  31. #        transition.
  32. #   A 'Pattern not found' message indicates that the TM has halted; the
  33. #    state it died in is left on the third line.
  34. #   I wouldn't recommend trying to flip between single-step and running
  35. #    modes during the same TM run.  Separate runs are okay, of course.
  36. #   I wouldn't be surprised to hear of a better way to do this;  I couldn't
  37. #    think of one, though.  Problems I had to overcome:
  38. #        I was thinking of defining a key for each state, bound to
  39. #        a long ifelse string, where each transition was a recursive
  40. #        call to the next key/state.  Unfortunately, DME won't
  41. #        support recursion past 20 levels, nor will it eliminate
  42. #        tail recursion. :-)  Go for it, Matt!
  43. #        DME doesn't support marks, i.e. variables referring to a
  44. #        position in the buffer;  these would have been very handy.
  45. #        There aren't clean ways to insert $scanf into the buffer or
  46. #        grab the character you're sitting on into $scanf.
  47. #        No multi-line macros.
  48. #   Two sample TMs are included at the end of this file; when you source
  49. #    it, they'll pop up in windows.
  50. #   Coming soon, to be implemented in DME
  51. #    A full lisp
  52. #    Floating point support
  53. #   :-)
  54.  
  55. # c-nk. - put the character under the cursor in $scanf. (utility routine)
  56. #      This routine fakes a blank at the end of the line.
  57. map c-nk. `ifelse r `` _' left left sc-nk. del del' sc-nk.'
  58.  
  59. # sc-nk. - subroutine for above
  60. #      the phrase `scanf %1s scanf %c' reads the next character
  61. #      (even if it's a space) into $scanf;  the `scanf %1s' makes
  62. #      sure the scanf buffer is zero-terminated.  :-)
  63. map sc-nk. `scanf %1s scanf %c'
  64.  
  65. # c-nk7 - read the symbol under the tape head into $scanf
  66. map c-nk7 `goto 1 last find `^' up c-nk.'
  67.  
  68. # c-nk8 - given symbol in $scanf, set line 3 to `state(symbol)'
  69. map c-nk8 `goto 3 last `(_)' left left left findr `_' $scanf'
  70.  
  71. # c-nk9 - given current state:symbol pair on line 3, find that transition
  72. map c-nk9 `goto 3 first scanf %[~] find $scanf'
  73.  
  74. # c-nk4 - read symbol to write for current transition into $scanf
  75. map c-nk4 `c-nk9 find `=(' right right c-nk.'
  76.  
  77. # c-nk5 - replace the character under the write head with $scanf
  78. #      I go through that findr locution because a 'find-and-replace'
  79. #      operation seems to be the only way to insert the value of
  80. #      $scanf into the buffer.
  81. map c-nk5 `goto 1 last find `^' up ` _' del left left findr `_' $scanf bs'
  82.  
  83. # c-nk6 - put the cursor on the head direction for the current transition
  84. map c-nk6 `c-nk9 find `=(' find `)' right while c=32 right'
  85.  
  86. # c-nk1 - if the cursor is on a <, move the head left; otherwise, move
  87. #      it right.
  88. map c-nk1 `ifelse c=60 `goto 2 first del' `goto 2 first ` '''
  89.  
  90. # c-nk2 - read the current transition's next state into $scanf
  91. map c-nk2 `c-nk9 find `=(' find `)' scanf `)%*[<>]%s''
  92.  
  93. # c-nk3 - set the current state (line 3) to the contents of $scanf
  94. map c-nk3 `goto 3 first remeol ` _' del left left findr `_' $scanf bs'
  95.  
  96. # c-nk- - single-step the TM
  97. map c-nk- `c-nk7 c-nk8 c-nk4 c-nk5 c-nk6 c-nk1 c-nk2 c-nk3'
  98.  
  99. # c-nk0 - initialize the TM
  100. map c-nk0 `goto 2 first remeol `^''
  101.  
  102. # c-ENTER - the whole shebang.    Given a setup as described above,
  103. # go until you run out of transitions.
  104. map c-ENTER `c-nk0 repeat -1 `c-nk-''
  105.  
  106.  
  107. # ==================== Sample TM #1 ====================
  108. topedge 0 height 100 newwindow chfilename `add'
  109. `1111+111' return
  110. return
  111. `start' return
  112. return
  113. `start(1)   =(1) > start     start(+)=(1) > 2nd' return
  114. `2nd(1)     =(1) > 2nd       2nd( )  =( ) < wipelast' return
  115. `wipelast(1)=( ) > done' return
  116. `# sample Turing machine #1 - given a string like 11111+111 (two' return
  117. `# numbers written in base 1), leave their sum on the tape.  For' return
  118. `# the above the result would be 11111111.' return'
  119. top
  120.  
  121. # ==================== Sample TM #2 ====================
  122. topedge 100 newwindow chfilename `anbn'
  123. `aaaaabbbbb' return
  124. return
  125. `start' return
  126. return
  127. `start(a)=(X) > findb    start( )=( ) > accept' return
  128. `findb(a)=(a) > findb    findb(Y)=(Y) > findb    findb(b)=(Y) < findX' return
  129. `findX(Y)=(Y) < findX    findX(a)=(a) < findX    findX(X)=(X) > nexta' return
  130. `nexta(a)=(X) > findb    nexta(Y)=(Y) > accept' return
  131. `# sample Turing machine #2 - accepts if the string consists of a group'
  132. return
  133. (# of a's followed by the same number of b's, rejects otherwise) return
  134. (# (halting in any state but `accept' means a rejection) ) return
  135. top
  136.  
  137.