8.3. Combining Turing Machines¶
8.3.2. .¶
.
8.3.3. Combining Turing Machines¶
Turing machine computations can be combined into larger machines:\(M_2\) prepares string as input to \(M_1\).\(M_2\) passes control to \(M_1\) with I/O head at start of input.\(M_2\) retrieves control when \(M_1\) has completed.
8.3.4. Some Basic Machines and Notation¶
\(|\Sigma|\) symbol-writing machines (one for each symbol)Any give letter \(\sigma\) has a symbol-writing machine named \(\sigma\)Head-moving machines, name R and L, move the head appropriatelyStart state indicated with >Transitions on anything other than the given symbol (for example, #) are labeled \(\overline{\#}\)Multiple copies of a machine get a superscript: \(R^2\) means move right twice.
8.3.5. More Machines¶
First do \(M_1\), then do \(M_2\) or \(M_3\) depending on current symbol.
(For \(\Sigma = \{a, b,c\}\)) Move head to the right until a blank is found.
8.3.6. More Machines (2)¶
Find first blank square to left: \(L_{\#}\)
8.3.7. More Machines (2)¶
Shift a string left.
Notice: The last step is “L#”, NOT with # a subscript! Meaning, “move left, then write #”. NOT “Move left until you see a #”.
8.3.8. More Machines (3)¶
Copy Machine: Transform \(\#w\underline{\#}\) into \(\#w\#w\underline{\#}\).
8.3.9. Turing’s Thesis¶
You now have some intuition for what can be accomplished by a Turing MachineAcceptor, transducer, math computationsMight be painful to write in “machine code”, but possibleAnd we have the beginnings of a more powerful graphical language to express our ideasTuring Thesis: Any computation that can be carried out by mechanical means can be performed by some Turing machine.How would we prove or disprove this?[Technically, we can’t, unless we could really nail down the meaning of “mechanical means”]
8.3.10. Formal Concept of Algorithm¶
A useful working definition:An algorithm to compute a function is a Turing Machine program that solves it.Using this definition lets us reason formally about what problems (functions) do or do not have algorithms.
