Exercise for the class: Discuss, using the book. One sentence answer.
ID::=left_hand_string state O(head_symbol right_hand_string).
abcqdef
means the machine is in state q and looking at symbol "d". To the left is "abc"
and to the right of the head is "ef".
abcq
means that the machine is looking at the first of the right hand blanks.
qcde
means that the machine is look at c and this is the left-most non-blank
symbol.
Ch 8 pp 318-319 -- Jump/Branch
Can Turing Machines jump or branch like assembly programs?
One way to encode a finite state controller is to use
a gotos like this:
q0: if(tape.head=='1') { tape.write('X'); tape.goRight(); goto q1; }
if(tape.head=='Y') { tape.write('Y'); tape.goRight(); goto q3; }
I think you can say that a TM is nothing but goto statements:-)
TMs pre-date the structured revolution by about 30 years.
8.2.4 Transition Diagrams for Turing Machines
Ch 8 pp 325 -- Transition Diagrams for Turing Machine
How come there is no accepting state in figure 8.12?
This machine is designed to implement a function rather than
accept a language. So it doesn't have an accepting state.
8.2.5 Language of a Turing Machine
Ch 8.2 pp 322-5 -- The Turing Machine
In transition function tables, why is '-' being used to denote both when a TM accepts and dies? Are the accepting states always the rows with ONLY dashes in them?
A Finite State Acceptor reports on string as it reads it -- each read
it either accepts or rejects what it has seen so far.
A TM reports once on the whole string it has
been given and then halts. A TM does not accept until it halts.
Later we will worry about rejecting inputs by never halting.
8.2.6 Turing Machines and Halting
Ch 8.2 pp 327 -- When does a Turing machine not halt ?
It depends on the machine. Try this one:
| State | Symbol | State' | Symbol' | Direction
|
|---|
| q0 | 0 | q0 | 0 | R
|
| q0 | 1 | q2 | 1 | R
|
| q1 | 0 | q2 | 0 | R
|
| q1 | 1 | q0 | 1 | L
|
| q2 | - | - | - | -
|
Sometimes there is a tight little loop, and sometimes a long loop
with the machine wandering all over the tape writing and over-writing
it.
Ch 8 pp 327 -- "Recursive'
Why are Turing machines that halt called "recursive"? When I think
recursion, I think of things that happen over and over again (like a
recursive loop), and I don't see any implicit guarantee that it won't
happen again in that word. Or is it in reference to the necessity of a
base case of a recursive algorithm?
The word "recursive" is historical: Mathematicians were working on the theory
of recursive functions just before and independently of Alan Turing's
work. It turns out that what they called "Recursive Functions" are
precisely those that can be computed by a TM that always halts. We
will spend more time on this in class 09
using the Web too fill in the gaps in the text.
Meanwhile: a machine (that halts) is not recursive, but the existence
of the machine proves that the problem that it
solves is recursive.
8.2.7 Exercises
Hints.
When asked for the IDs you need to trace the progress of
the TM: q00|-Xr0 |- X0r |- Halts.
Be careful to always always always look to the RIGHT of the
state symbol not the left. The TM only sees the symbol to the RIGHT.