8.An Important TM§

Saving...

Server Error
Resubmit

.

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.

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_{\#}\)

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 #”.

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?

[Technically, we can’t, unless we could really nail down the meaning of “mechanical means”]

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.