home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Clean 1.2.4 / IO Examples / Turing / TuringHelp < prev   
Encoding:
Text File  |  1993-04-14  |  4.8 KB  |  124 lines  |  [TEXT/3PRM]
  1. \About
  2. \DTuring
  3.  
  4. \dTuring machine interpreter
  5. \cby Halbe Huitema
  6.  
  7. \cThis application is developed using the Concurrent
  8. \cClean System, a programming environment for the
  9. \cfunctional language Concurrent Clean. This system
  10. \cis developed by the research group Parallel
  11. \cSystems and Computational Models at the
  12. \cUniversity of Nijmegen, the Netherlands.
  13.  
  14. \dThe Concurrent Clean System is
  15. \dfreely available via FTP for
  16. \dMacintosh, Sun3 and Sun4.
  17. \EndAbout
  18.  
  19. \Help
  20. \DTuring
  21.  
  22. A Turing Machine Interpreter written in Concurrent Clean, a functional language developed
  23. at the Research Institute for Declarative Systems of the University of Nijmegen.
  24.  
  25. This program is a complete programming environment for the simplest computer of all:
  26.                                          
  27. \dThe Turing Machine.
  28.  
  29.  
  30. \DConventions
  31.  
  32. In this Turing machine interpreter the following conventions are used:
  33.  
  34. - The start state must be "S".
  35. - The halt state must be "halt".
  36. - An empty tapecell is filled with a '#'.
  37. - A transition has the following form: from,head -> to,move where from and to are
  38.    states, head can be any symbol except L and R and move can be any symbol. When
  39.    move is L or R the head will move one cell to the left resp. right.
  40. - Moving the head over the left edge of the tape is considered to be an error, which will
  41.    be reported.
  42. - The interpreter will stop with an error message when there is no transition applicable.
  43. - A state can be up to 4 characters long.
  44. - The name of the T.M. can be up to 29 characters long.
  45. - There is no explicit alphabet the T.M. works on.
  46. - There is no explicit set of states.
  47. The alphabet and the set of states are defined implicitly by the transitions.
  48.  
  49. A file containing a T.M. contains the transitions and the initial tape contents. First the
  50. transitions must be specified, one on each line. A transition consists of the parts 'from',
  51. 'head', 'to' and 'move', where 'from' and 'to' are states (max. four characters) and
  52. 'head' and 'move' are characters. These parts must be separated by blanks, or one or
  53. more of the following characters: (){}[],.;:->. When a complete transition has been read
  54. the rest of the line is considered to be comment. The following are all valid transitions:
  55.  
  56.    S # Q1 1                 From state 'S' reading '#', go to state 'Q1' and write '1'
  57.    ((Q1,1),(Q2,R))      Read a '1' and go right
  58.      Q2   #  ->  halt L
  59.  
  60. The tape is separated from the transitions by a line beginning with the word "Tape":
  61.  
  62.    Tape:
  63.    #0000011111#
  64.    
  65. Empty lines and lines beginning with a '|' (comment lines) are ignored.
  66.  
  67.  
  68. \DMenus and commands
  69. \L
  70. \bThe File menu:
  71.  
  72. - The command New will open a new empty Turing Machine.
  73. - With the commands Open, Save and Save As a T.M. can be opened and saved.
  74.  
  75. \bWarning:
  76.    A T.M. is saved in a standard format (see the sample machines). Comments and special
  77.    transition layouts will be lost!
  78.  
  79. - Help gives you the information you are reading now.
  80. - With the command Quit you can quit the program.
  81. \L
  82. \bThe Machine Menu:
  83.  
  84. - Step: let the T.M. do one step (transition).
  85. - Run:  change the state into S and let the T.M. run until the halt-state is reached.
  86. - Halt/Continue: Halt halts a running T.M., Continue continues a halted T.M.
  87. - Speed: a submenu to set the speed of the T.M. (Very Slow - Very Fast).
  88. \L
  89. \bEditing the Turing Machine:
  90.  
  91. By clicking anywhere on the Turing Machine the machine can be edited. When you click
  92. on the state a dialog appears that lets you alter the state of the machine, when you click
  93. on a transition a dialog appears that lets you change or remove that transition etcetera.
  94. When you click inside the transitions area but outside the existing transitions you can
  95. add a new transition. When you Command-click on the tape the head will move to the
  96. cell you clicked on. The empty cells between the current head position and the new position
  97. will be filled with #'s.
  98.  
  99.  
  100. \DSample machines.
  101.  
  102. Five sample machines have been defined which perform the following actions:
  103.  
  104. \baddunary.tm
  105. Adds the two unary coded integers that are on the tape. The head position must be on the
  106. first empty cell on the right of the input.
  107.  
  108. \bsleft.tm
  109. Shifts the input (consisting of 0's and 1's) one cell to the left. The head can begin anywhere
  110. in the input. The input is bounded by the empty cells to left and the right of it.
  111.  
  112. \bsright.tm
  113. Shifts the input (consisting of a's and b's) one cell to the right. The head can begin
  114. anywhere in the input. The input is bounded by the empty cells to left and the right of it.
  115.  
  116. \beright.tm
  117. Shifts the input one cell to the right (just like sright.tm) and after that starts again.
  118. Therefore it will continue to shift the input to the right "eternally" (until the heap is full).
  119.  
  120. \bbininc.tm
  121. Increments the binary number that is on the tape. The binary number on the tape is
  122. reversed (low bits to the left, high bits to the right, e.g. 001 = 8 decimal). After
  123. incrementing the number it starts again.
  124. \EndHelp