8.An Important TM§

1 / 63 Settings

<<<>>>

In this slideshow, we will trace the acceptance or rejections of some strings. The given machine can accept $L = \{a^nb^nc^n: n> 0\}$.

a;A,R

B;B,R
a;a,R

b;B,R

C;C,R
b;b,R

c;C,L

a;a,L
B;B,L
C;C,L
b;b,L

A;A,R

B;B,R

B;B,R
C;C,R

#;#,L

C;c,L
B;b,L
A;a,L

#;#,R

Saving...

Server Error
Resubmit

.

Combining Turing Machines

Turing machine computations can be combined into larger machines:

M2 prepares string as input to M1.
M2 passes control to M1 with I/O head at start
of input.
M2 retrieves control when M1 has completed.

Some Basic Machines and Notation

|Σ| symbol-writing machines (one for each symbol)
Any give letter σ has a symbol-writing machine named
σ
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 ¯#
Multiple copies of a machine get a superscript: R2 means
move right twice.

More Machines

First do $M_1$ , then do $M_2$ or $M_3$ depending on current symbol.

$>M_1$

$M_2$

$M_3$

$a$

$b$

(For $\Sigma = \{a, b,c\}$ ) Move head to the right until a blank is found.

$>R$

$\overline{\#}$

More Machines (2)

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

$>L$

$\overline{\#}$

$\#$

$M$

$>L_{\#}$

$M$

More Machines (2)

Shift a string left.

$R$

$L \sigma R$

$L\#$

$\overline{\#}$

$\#$

$>L_{\#}$

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{\#}$ .

$R$

$\# R^{2}_{\#} \sigma L^{2}_{\#} \sigma$

$R_{\#}$

$\overline{\#}$

$\#$

$>L_{\#}$

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.