Turing machine power point presentations

Turing machine

1. FORMAL LANGUAGES,
AUTOMATA, AND
COMPUTABILITY
15-453
* Read chapter 4 of the book for next time *
Lecture9x.ppt

2. REVIEW

3. A Turing Machine is represented by a 7-tuple T
= (Q, Σ, Γ, , q
0, q
accept, q
reject):
Q is a finite set of states
Γ is the tape alphabet, a superset of Σ;   Γ
q
0  Q is the start state
Σ is the input alphabet, where   Σ
 : Q  Γ

→ Q  Γ  {L, R} is the transition
func
q
accept
 Q is the accept state
q
reject
 Q is the reject state, and q
reject
 q
accept

4. CONFIGURATION: (1) tape contents,
(2)
 current state, (3) location of read/write head.
11010q
700110
q
7
10 000 01 1 11
q
7
10 000 01 1 11

5. A TM recognizes a language iff it accepts all
and only those strings in the language.
A TM decides a language L iff it accepts all
strings in L and rejects all strings not in L.
A language L is called Turing-recognizable
or recursively enumerable
iff some TM recognizes L.
A language L is called decidable or recursive
iff some TM decides L.

6. A language is called Turing-recognizable or
recursively enumerable (r.e.) if some TM
recognizes it.
A language is called decidable or recursive
if some TM decides it.
recursive
languages
r.e.
languages
recursive
languages
r.e.
languages

7. Theorem: If A and A are r.e. then A is decidable.
Given:
a Turing Machine TM
A
that recognizes A and
a Turing Machine TM
R that recognizes A,
we can build a new machine that decides A.
How can we prove this?
•Run TM
A
and TM
R
in parallel.
(Or more precisely, interleave them.)
•One of them will eventually recognize the
input string.
•If TM
A recognizes it, then accept.
•If TM
R
recognizes it, then reject.

8. A TM that decides { 0 | n ≥ 0 }
High-Level Idea.
•Repeatedly divide the number of zeros in half
until it becomes an odd number.
•If we are left with a single zero, then accept.
•Otherwise, reject.
2
n
We want to accept iff:
•the input string consists entirely of zeros, and
•the number of zeros is a power of 2.

9. A TM that decides { 0 | n ≥ 0 }
1.Sweep from left to right, cross out every other 0.
(Divides number in half.)
2.If in step 1, the tape had only one 0, accept.
3.Else if the tape had an odd number of 0’s, reject.
4.Move the head back to the first input symbol.
5.Go to step 1.
PSEUDOCODE:
2
n

10. C = {a
i
b
j
c
k
| k = i×j, and i, j, k ≥ 1}
Example
aaabbbbcccccccccccc
3 3×4 = 124

11. C = {a
i
b
j
c
k
| k = i×j, and i, j, k ≥ 1}
High-Level Idea.
For each occurrence of a: {
For each occurrence of b: {
Delete an occurrence of c.
}
}

12. C = {a
i
b
j
c
k
| k = i×j, and i, j, k ≥ 1}
1.If the input doesn’t match a*b*c*, reject.
2.Move the head back to the leftmost symbol.
3.Cross off an a, scan to the right until b.
Sweep between b’s and c’s, crossing out one of
each until all b’s are out. If too few c’s, reject.
4.Uncross all the b’s.
If there’s another a left, then repeat stage 3.
If all a’s are crossed out,
Check if all c’s are crossed off.
If yes, then accept, else reject.
PSEUDOCODE:

13. C = {a
i
b
j
c
k
| k = i×j, and i, j, k ≥ 1}
aabbbcccccc
xabbbcccccc
xayyyzzzccc
xabbbzzzccc
xxyyyzzzzzz

14. TURING-MACHINE VARIANTS
Turing machines can be extended in various ways,
but so long as a new TM only reads and writes a
finite number of symbols in each step,
an old TM can still simulate it!
Example: Turing machines with multiple tapes.
Input comes in on one tape, and
other tapes are used for scratch work.

15. MULTITAPE TURING MACHINES
 : Q  Γ
k

→ Q  Γ
k

{L,R}
k
FINITE
STATE
CONTROL

16. Theorem: Every Multitape Turing Machine can be
transformed into a single tape Turing Machine
FINITE
STATE
CONTROL
001
FINITE
STATE
CONTROL
001 # # #
. . .

17. Theorem: Every Multitape Turing Machine can be
transformed into a single tape Turing Machine
FINITE
STATE
CONTROL
001
FINITE
STATE
CONTROL
001 # # #
. . .

18. THE CHURCH-TURING THESIS
Anything that can be computed
by algorithm (in our intuitive
sense of the term “algorithm”)
can be computed by a Turing
Machine.

19. We can encode a TM as a string of 0s and 1s
0
n
 1 0
m
 1 0
k
 1 0
s
 1 0
t
 1 0
r
 1 0
u
 1…
n states
m tape symbols
(first k are input
symbols)
start
state
accept
state
reject
state
blank
symbol
( (p, a), (q, b, L) ) = 0
p
10
a
10
q
10
b
10
( (p, a), (q, b, R) ) = 0
p
10
a
10
q
10
b
11

20. Similarly, we can encode DFAs, NFAs,
CFGs, etc. into strings of 0s and 1s
A
DFA = { (B, w) | B is a DFA that accepts string w }
A
NFA = { (B, w) | B is an NFA that accepts string w }
A
CFG
= { (G, w) | G is a CFG that generates string w }
So we can define the following languages:

21. A
DFA
= { (B, w) | B is a DFA that accepts string w }
Theorem: A
DFA
is decidable
Proof Idea: Simulate B on w
A
CFG
= { (G, w) | G is a CFG that generates string w }
Theorem: A
CFG
is decidable
Proof Idea: Transform G into Chomsky Normal
Form. Try all derivations of length 2|w|-1
A
NFA
= { (B, w) | B is an NFA that accepts string w }
Theorem: A
NFA is decidable

22. UNDECIDABLE PROBLEMS

23. w  L ?
accept reject
TM
yes no
w  Σ*
L is decidable
(recursive)
w  L ?
acceptreject or no output
TM
yes no
w  Σ*
L is semi-decidable
(recursively enumerable,
Turing-recognizable)
Theorem: L is decidable if both L and L
are recursively enumerable

24. There are languages over {0,1}
that are not decidable.
If we believe the Church-Turing Thesis, this is
major: it means there are things that formal
computational models inherently cannot do.
We can prove this using a counting argument.
We will show there is no function from the set
of all Turing Machines onto the set of all
languages over {0,1}. (Works for any Σ.)
Then we will prove something stronger:
There are semi-decidable (r.e.) languages that
are NOT decidable.

25. Turing
Machines
Languages
over {0,1}

26. Let L be any set and 2
L
be the power set of L
Theorem: There is no map from L onto 2
L
Proof: Assume, for a contradiction, that
there is an onto map f : L  2
L
Let S = { x  L | x  f(x) }
We constructed S so that, for every elem x in L,
the set S differs from f(x):
S ≠ f(x) because x  S iff x  f(x)
Cantor’s Theorem

27. Theorem: There is no onto function from the
positive integers to the real numbers in (0, 1)
1
2
3
4
5
:
0.28347279…
0.88388384…
0.77635284…
0.11111111…
0.12345678…
:
Proof:Suppose f is such a function:
[ n
th
digit of r ] =
2
8
6
1
5
1 if [ n
th
digit of f(n) ]  1
0 otherwise
f(n)  r for all n ( Here, r = 0.11101... )

28. Let Z
+
= {1,2,3,4…}. There exists a bijection
between Z
+
and Z
+
 Z
+
(1,1) (1,2) (1,3) (1,4) (1,5) …
(2,1) (2,2) (2,3) (2,4) (2,5) …
(3,1) (3,2) (3,3) (3,4) (3,5) …
(4,1) (4,2) (4,3) (4,4) (4,5) …
(5,1) (5,2) (5,3) (5,4) (5,5) …
(or Q
+
)
: : : : : ∙.
Sidenote

29. THE MORAL:
For any set L,
2
L
always has ‘more’ elements than L

30. Not all languages over {0,1} are decidable, in fact:
not all languages over {0,1} are semi-decidable
{Turing Machines}
{Strings of 0s and 1s}
{Sets of strings
of 0s and 1s}
{Languages over {0,1}}
Set L Powerset of L: 2
L
{decidable languages over {0,1}}
{semi-decidable langs over {0,1}}

31. A
TM = { (M, w) | M is a TM that accepts string w }
THE ACCEPTANCE PROBLEM
Theorem: A
TM
is semi-decidable (r.e.)
but NOT decidable
A
TM
is r.e. :
Define a TM U as follows:
On input (M, w), U runs M on w. If M ever
accepts, accept. If M ever rejects, reject.
Therefore,
U accepts (M,w)  M accepts w  (M,w)  A
TM
Therefore, U recognizes A
TM
U is a universal TM

32. A
TM
= { (M,w) | M is a TM that accepts string w }
A
TM
is undecidable:(proof by contradiction)
Assume machine H decides A
TM
H( (M,w) ) =
Accept if M accepts w
Reject if M does not accept w
Construct a new TM D as follows: on input M,
run H on (M,M) and output the opposite of H
D( M ) =
Reject if M accepts M
Accept if M does not accept M
D
D D
D D
Contradiction!

33. Theorem: A
TM
is r.e. but NOT decidable
Theorem: A
TM
is not even r.e.!
The Halting Problem is Not Decidable

34. We have shown:
Given any presumed machine H for A
TM,
we can effectively construct a TM D such that
(D,D)  A
TM but H fails to tell us that.
In other words,
For any machine H that recognizes A
TM
we can effectively give an instance
where H fails to decide A
TM
In other words,
Given any good candidate for deciding the
Halting Problem, we can effectively construct
an instance where the machine fails.

35. HALT
TM = { (M,w) | M is a TM that halts on string w }
Theorem: HALT
TM is undecidable
THE HALTING PROBLEM
Proof: Assume, for a contradiction, that TM H
decides HALT
TM
We use H to construct a TM D that decides A
TM
On input (M,w), D runs H on (M,w)
If H rejects then reject
If H accepts, run M on w until it halts:
Accept if M accepts and
Reject if M rejects

36. In many cases, one can show that a
language L is undecidable by showing
that if it is decidable, then so is A
TM
We reduce deciding A
TM to deciding
the language in question
A
TM
≤ L
We just showed: A
TM ≤ Halt
TM
Is Halt
TM
≤ A
TM
?

37. Read chapter 4 of the book for next time