[STAR.TNG] [move head back and forth until the nearest * is found] [Q0 looks for an initial star, halts or shifts right] [Q1 looks for an immediate star, halts or places the right marker] [Q2 places the left marker, halt is illusory] [Q3 runs right until it finds the right fence] [Q4 extends the right fence, bounces] [Q5 erases the left marker] [Q6 extends the left fence, bounces] [Q7 erases the right marker] [Q8 runs left and halts over the star] [Q9 runs left until it finds the left fence] [Q10 runs right and halts over the star] [A Turing machine has a very limited scope of vision, but it can use as many states as necessary to remember what it is running back and forth looking for. It can also use up as much tape as it wants to record intermediate results, but at the price of placing markers to identify the information or using more states to recall where it was deposited.] [It is well known that a Turing machine obtains results through an incredibly complicated series of movements; its principal reason for existence is that the simplicity of its definition and oper- ation permits theorems to be proven about its operation or non- operation, which then apply to any other computation, according to Church's thesis.] [It is quite instructive to set up the generally used programming concepts, such as the use of veriables, the introduction of subroutines, and even structured programming, in terms of the set theory of the state space of a Turing machine. The tradeoff between the number of symbols on the tape and the number of states in the machine can be studied experimentally, as well as most of the other traditional results of Turing machine theory, ending with the construction of a Universal machine.] [[ This Turing machine seeks the nearest "1" on its tape. Type the initial tape, using * for 1, . for 0, but be sure to place a # in front of the bit which is under the reading head. End the tape with a carriage return. For example - ....*........#........ Each succeeding keystroke will display one step of the Turing machine`s operation, showing a segment of the tape followed by the state which produced the line shown. ]] [* at once, quit] (Q0,*,*,H,0) [go right, look there] (Q0,.,.,Q1,+) [found it] (Q1,*,*,H,0) [make right fence, go left] (Q1,.,*,Q2,-) [this won't happen] (Q2,*,*,H,0) [set left fence, go right] (Q2,.,*,Q3,+) [erase fence, look beyond] (Q3,*,.,Q4,+) [keep looking for fence] (Q3,.,.,Q3,+) [found *, go erase l fence] (Q4,*,*,Q9,-) [set in new fence, go left] (Q4,.,*,Q5,-) [erase fence, look beyond] (Q5,*,.,Q6,-) [keep heading left] (Q5,.,.,Q5,-) [found *, go erase r fence] (Q6,*,*,Q7,+) [set in new fence, go right] (Q6,.,*,Q3,+) [found fence, go left to *] (Q7,*,.,Q8,-) [keep looking for fence] (Q7,.,.,Q7,+) [here's * we're looking for] (Q8,*,*,H,0) [keep on looking left] (Q8,.,.,Q8,-) [found fence, go right to *] (Q9,*,.,Q10,+) [keep looking for fence] (Q9,.,.,Q9,-) [here's * we're looking for] (Q10,*,*,H,0) [continue rightward search] (Q10,.,.,Q10,+) [end]