7.Combining Turing Machines (1)§

Lemma: If

$(q_1,\ w_1\underline{a_1}u_1) \vdash_M^* (q_2,\ ww_2\underline{a_2}u_2)$

for string $w$ and

$(q_2,\ w_2\underline{a_2}u_2) \vdash^*_M (q_3,\ w_3\underline{a_3}u_3)$,

then

$(q_1,\ w_1\underline{a_1}u_1) \vdash^*_M (q_3,\ ww_3\underline{a_3}u_3)$.

Insight: Since $(q_2,\ w_2\underline{a_2}u_2) \vdash^*_M (q_3,\ w_3\underline{a_3}u_3)$, this computation must take place without moving the head left of $w_2$.

The machine cannot “sense” the left end of the tape.

And if it had moved left, it would have hung.

Combining Turing Machines (2)

Thus, the head won’t move left of $w_2$ even if it is not at the left end of the tape.

This means that 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.

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 appropriately
Start 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.

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.

More Machines (2)

Find first blank square to left: $L_{\#}$

Shift a string left.

More Machines (3)

Copy Machine: Transform $\#w\underline{\#}$ into $\#w\#w\underline{\#}$.

Turing’s Thesis

You now have some intuition for what can be accomplished by a Turing Machine

Acceptor, transducer, math computations
Might be painful to write in “machine code”, but possible
And we have the beginnings of a more powerful graphical
language to express our ideas

Turing 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”?

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.