Processing math: 100%

Partial Coursenotes for Formal Languages and Automata

Chapter 8 Week 10

| About « 8.2. Decideability vs. Acceptability :: Contents :: 8.4. Turing Machine Extensions »

8.3. Combining Turing Machines¶

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

q0
q1
q2
q3
q4
q5
q6
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
#
#
#
#
a
a
b
b
c
c
#
#
#
#
#

Saving...
Server Error
Resubmit

8.3.2. .¶

.

8.3.3. 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.

8.3.4. 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.

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

8.3.6. More Machines (2)¶

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

$>L$
$\overline{\#}$
$\#$
$M$
$>L_{\#}$
$M$

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

8.3.8. More Machines (3)¶

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

$R$
$\# R^{2}_{\#} \sigma L^{2}_{\#} \sigma$
$R_{\#}$
$\overline{\#}$
$\#$
$>L_{\#}$

8.3.9. 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”]

8.3.10. 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.

Contact Us || Privacy | | License « 8.2. Decideability vs. Acceptability :: Contents :: 8.4. Turing Machine Extensions »