8.Computation§
We can easily demonstate simple computation on unary representation.
An Important TM
.
.
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.
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?
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.