home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / sigm / vol166 / star.rec < prev    next >
Encoding:
Text File  |  1984-04-29  |  3.6 KB  |  90 lines
  1.  
  2. [STAR.REC]
  3.  
  4. [move head back and forth until the nearest * is found]
  5.  
  6. [Q0 looks for an initial star, halts or shifts right]
  7. [Q1 looks for an immediate star, halts or places the right marker]
  8. [Q2 places the left marker, halt is illusory]
  9. [Q3 runs right until it finds the right fence]
  10. [Q4 extends the right fence, bounces]
  11. [Q5 erases the left marker]
  12. [Q6 extends the left fence, bounces]
  13. [Q7 erases the right marker]
  14. [Q8 runs left and halts over the star]
  15. [Q9 runs left until it finds the left fence]
  16. [Q10 runs right and halts over the star]
  17.  
  18. [A Turing machine has a very limited scope of vision, but it can
  19.  use as many states as necessary to remember what it is running 
  20.  back and forth looking for. It can also use up as much tape as it
  21.  wants to record intermediate results, but at the price of placing
  22.  markers to identify the information or using more states to recall
  23.  where it was deposited.]
  24.  
  25. [It is well known that a Turing machine obtains results through an
  26.  incredibly complicated series of movements; its principal reason
  27.  for existence is that the simplicity of its definition and oper-
  28.  ation permits theorems to be proven about its operation or non-
  29.  operation, which then apply to any other computation, according
  30.  to Church's thesis.]
  31.  
  32. [It is quite instructive to set up the generally used programming
  33.  concepts, such as the use of veriables, the introduction of
  34.  subroutines, and even structured programming, in terms of the
  35.  set theory of the state space of a Turing machine. The tradeoff
  36.  between the number of symbols on the tape and the number of states
  37.  in the machine can be studied experimentally, as well as most of
  38.  the other traditional results of Turing machine theory, ending
  39.  with the construction of a Universal machine.]
  40.  
  41. [[]]
  42.  
  43. {
  44.   [head right]            (AAB;'.'I;;)+
  45.   [head left]            (B;'.'I;;)-
  46.   [head stationary]        (;)0
  47.   [test equality]        (pGm=n;nL)=
  48.   [cr.lf]            (2573TL;)&
  49.   [read phrase]            (R13%='';T08%(=2080[sp,bs]TL)(@J|;L@J;);)J
  50.   [sign-on message]        ('
  51. This Turing machine seeks the nearest "1" on its tape.
  52. Type the initial tape, using * for 1, . for 0, but be sure
  53. to place a # in front of the bit which is under the reading
  54. head. End the tape with a carriage return.  For example -
  55.  
  56.             ....*........#........
  57.  
  58. Each succeeding keystroke will display one step of the
  59. Turing machine`s operation, showing a segment of the tape
  60. followed by the state which produced the line shown.
  61. 'TL@&'Initial Tape:'TL@&@JI'#'FD;:)R
  62.   [write tape segment]        (j(20b;J;)qtz' 'TABqtTLz(20a;LZ;)qtB;) W
  63.                 (@R'Q0'(@&@WRLT
  64.  
  65. [* at once, quit]        ('Q0'@='*'E;)D'*'IL'H'@0:
  66. [go right, look there]        ('Q0'@='.'E;)D'.'IL'Q1'@+:
  67. [found it]            ('Q1'@='*'E;)D'*'IL'H'@0:
  68. [make right fence, go left]    ('Q1'@='.'E;)D'*'IL'Q2'@-:
  69. [this won't happen]        ('Q2'@='*'E;)D'*'IL'H'@0:
  70. [set left fence, go right]    ('Q2'@='.'E;)D'*'IL'Q3'@+:
  71. [erase fence, look beyond]    ('Q3'@='*'E;)D'.'IL'Q4'@+:
  72. [keep looking for fence]    ('Q3'@='.'E;)D'.'IL'Q3'@+:
  73. [found *, go erase l fence]    ('Q4'@='*'E;)D'*'IL'Q9'@-:
  74. [set in new fence, go left]    ('Q4'@='.'E;)D'*'IL'Q5'@-:
  75. [erase fence, look beyond]    ('Q5'@='*'E;)D'.'IL'Q6'@-:
  76. [keep heading left]        ('Q5'@='.'E;)D'.'IL'Q5'@-:
  77. [found *, go erase r fence]    ('Q6'@='*'E;)D'*'IL'Q7'@+:
  78. [set in new fence, go right]    ('Q6'@='.'E;)D'*'IL'Q3'@+:
  79. [found fence, go left to *]    ('Q7'@='*'E;)D'.'IL'Q8'@-:
  80. [keep looking for fence]    ('Q7'@='.'E;)D'.'IL'Q7'@+:
  81. [here's * we're looking for]    ('Q8'@='*'E;)D'*'IL'H'@0:
  82. [keep on looking left]        ('Q8'@='.'E;)D'.'IL'Q8'@-:
  83. [found fence, go right to *]    ('Q9'@='*'E;)D'.'IL'Q10'@+:
  84. [keep looking for fence]    ('Q9'@='.'E;)D'.'IL'Q9'@-:
  85. [here's * we're looking for]    ('Q10'@='*'E;)D'*'IL'H'@0:
  86. [continue rightward search]    ('Q10'@='.'E;)D'.'IL'Q10'@+:
  87. 'H'=;);)}
  88.  
  89. [end]
  90.