8.2. Combining Turing Machines¶
8.2.1. Computation¶
8.2.3. .¶
.
8.2.4. 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 end of input.\(M_2\) retrieves control when \(M_1\) has completed.
8.2.5. 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.2.6. 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.2.7. More Machines (2)¶
Find first blank square to left: \(L_{\#}\)
8.2.8. 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.2.9. More Machines (3)¶
Copy Machine: Transform \(\#w\underline{\#}\) into \(\#w\#w\underline{\#}\).
8.2.10. 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?What is the technical meaning of the word “thesis”?
8.2.11. 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.