Languages and Finite Automata

Undecidable Problems
(unsolvable problems)
Fall 2006
Costas Busch - RPI
1
Decidable Languages
Recall that:
A language A is decidable,
if there is a Turing machine M (decider)
that accepts the language A and
halts on every input string
Decision
On Halt:
Turing Machine M
YES
Accept
Input
Decider for A
string
NO
Reject
Fall 2006
Costas Busch - RPI
2
A computational problem is decidable
if the corresponding language is decidable
We also say that the problem is solvable
Fall 2006
Costas Busch - RPI
3
Problem: Does DFA M accept
the empty language L(M )  ?
Corresponding Language:
X
(Decidable)
EMPTYDFA 
{ M : M is a DFA that accepts empty language}
Description of DFA M as a string
(For example, we can represent M as a
binary string, as we did for Turing machines)
Fall 2006
Costas Busch - RPI
4
Decider for EMPTYDFA :
On input M :
Determine whether there is a path from
the initial state to any accepting state
DFA M
Decision:
Fall 2006
DFA M
L(M )  
L(M )  
Reject M
Accept M
Costas Busch - RPI
5
Problem: Does DFA M accept
a finite language?
Corresponding Language:
X
(Decidable)
FINITEDFA 
{ M : M is a DFA that accepts a finitelanguage}
Fall 2006
Costas Busch - RPI
6
Decider for FINITEDFA :
On input M :
Check if there is a walk with a cycle
from the initial state to an accepting state
DFA M
Decision:
Fall 2006
DFA M
infinite
finite
Reject M
(NO)
Accept M
(YES)
Costas Busch - RPI
7
Problem: Does DFA M
Corresponding Language:
X
accept string w ?
(Decidable)
ADFA 
{ M ,w : M is a DFA that accepts string w }
Fall 2006
Costas Busch - RPI
8
Decider for ADFA :
On input string M ,w :
Run DFA M on input string w
If M accepts w
Then accept M ,w (and halt)
Else reject M ,w (and halt)
Fall 2006
Costas Busch - RPI
9
Problem: Do DFAs M1 and M2
accept the same language?
Corresponding Language:
X
(Decidable)
EQUALDFA 
{ M1 , M2 : M1 and M2 are DFAs that accept
the same languages}
Fall 2006
Costas Busch - RPI
10
Decider for EQUALDFA :
On input
Let
Let
M1, M2 :
L1 be the language of DFA M1
L2 be the language of DFA M2
Construct DFA M such that:
L(M)  (L1  L2 )  (L1  L2 )
(combination of DFAs)
Fall 2006
Costas Busch - RPI
11
( L1  L2 )  ( L1  L2 )  
and
L1  L2  
L1
L1  L2  
L2
L2 L
2
L1  L2
L1 L1
L2  L1
L1  L2
Fall 2006
Costas Busch - RPI
12
( L1  L2 )  ( L1  L2 )  
L1  L2  
L1
or
L1  L2  
L2
L2
L1  L2
L1
L2  L1
L1  L2
Fall 2006
Costas Busch - RPI
13
Therefore, we only need
to determine whether
L(M)  (L1  L2 )  (L1  L2 )  
which is a solvable problem for DFAs:
EMPTYDFA
Fall 2006
Costas Busch - RPI
14
Undecidable Languages
undecidable language = not decidable language
There is no decider:
there is no Turing Machine
which accepts the language
and makes a decision (halts)
for every input string
(machine may make decision for some input strings)
Fall 2006
Costas Busch - RPI
15
For an undecidable language,
the corresponding problem is
undecidable (unsolvable):
there is no Turing Machine (Algorithm)
that gives an answer (yes or no)
for every input instance
(answer may be given for some input instances)
Fall 2006
Costas Busch - RPI
16
We have shown before that there are
undecidable languages:
L
Turing-Acceptable
L
Decidable
L
is Turing-Acceptable and undecidable
Fall 2006
Costas Busch - RPI
17
We will prove that two particular problems
are unsolvable:
Membership problem
Halting problem
Fall 2006
Costas Busch - RPI
18
Membership Problem
Input:
•Turing Machine
•String w
Question:
Does M
M
accept w ?
w L(M ) ?
Corresponding language:
ATM  { M ,w : M is a Turing machine that
accepts string w }
Fall 2006
Costas Busch - RPI
19
Theorem:
ATM
is undecidable
(The membership problem is unsolvable)
Proof:
Basic idea:
We will assume that ATM is decidable;
We will then prove that
every decidable language
is Turing-Acceptable
A contradiction!
Fall 2006
Costas Busch - RPI
20
Suppose that
Input
string
M ,w
M
w
Fall 2006
ATM
is decidable
Decider
for ATM
H
YES
M accepts w
NO
M rejects w
Costas Busch - RPI
21
Let
L be a Turing recognizable language
Let ML be the Turing Machine that accepts
We will prove that
L is also decidable:
we will build a decider for
Fall 2006
L
Costas Busch - RPI
L
22
String description of ML
Decider for
ML
L
Decider for ATM
ML accepts s ?
s
Input
string
Fall 2006
YES
accept s
(and halt)
NO
reject s
(and halt)
Costas Busch - RPI
23
Therefore,
L is decidable
Since L is chosen arbitrarily, every
Turing-Acceptable language is decidable
But there is a Turing-Acceptable language
which is undecidable
Contradiction!!!!
Fall 2006
END OF PROOF
Costas Busch - RPI
24
We have shown:
Undecidable
ATM
Decidable
Fall 2006
Costas Busch - RPI
25
We can actually show:
Turing-Acceptable
ATM
Decidable
Fall 2006
Costas Busch - RPI
26
ATM
is Turing-Acceptable
Turing machine that accepts
1. Run M on input
M ,w
Fall 2006
ATM
:
w
2. If M accepts w
then accept M ,w
Costas Busch - RPI
27
Halting Problem
Input:
•Turing Machine
•String w
Question:
M
Does M halt while
processing input string w ?
Corresponding language:
HALTTM  { M ,w : M is a Turing machine that
halts on inputstring w }
Fall 2006
Costas Busch - RPI
28
Theorem:
HALTTM
is undecidable
(The halting problem is unsolvable)
Proof:
Basic idea:
Suppose that HALTTM is decidable;
we will prove that
every decidable language
is also Turing-Acceptable
A contradiction!
Fall 2006
Costas Busch - RPI
29
Suppose that
HALTTM
is decidable
Input
string
M ,w
M
w
Fall 2006
Decider for
HALTTM
YES
NO
Costas Busch - RPI
M
halts on
input
w
M
doesn’t halt
on input
w
30
Let
Let
L be a Turing-Acceptable language
ML
be the Turing Machine that accepts
We will prove that
L is also decidable:
we will build a decider for
Fall 2006
L
Costas Busch - RPI
L
31
Decider for
L
Decider for
ML
s
Input
string
HALTTM
ML halts on s ?
NO
YES
ML halts
Run ML
with input
and accepts
s
ML halts
and rejects
Fall 2006
Costas Busch - RPI
reject s
and halt
accept
s
reject
s
and halt
and halt
32
Therefore,
L is decidable
Since L is chosen arbitrarily, every
Turing-Acceptable language is decidable
But there is a Turing-Acceptable language
which is undecidable
Contradiction!!!!
Fall 2006
END OF PROOF
Costas Busch - RPI
33
An alternative proof
Theorem:
HALTTM
is undecidable
(The halting problem is unsolvable)
Proof:
Basic idea:
Assume for contradiction that
the halting problem is decidable;
we will obtain a contradiction
using a diagonilization technique
Fall 2006
Costas Busch - RPI
34
Suppose that
Input
string
M ,w
M
w
Fall 2006
HALTTM
is decidable
Decider
for HALTTM
H
YES
M halts on w
NO
doesn’t
halt on
Costas Busch - RPI
M
w
35
Looking inside
H
Decider for HALTTM
Input string:
M ,w
H
q0
qaccept YES
M halts on w?
qreject NO
Fall 2006
Costas Busch - RPI
36
Construct machine
H
H
M ,w
H :
Loop forever
qacceptYES
qa
qb
q0 M halts on w?
qreject NO
If
M halts on input w Then Loop Forever
Else Halt
Fall 2006
Costas Busch - RPI
37
Construct machine F :
F
M
Copy M
on tape
If
M, M
H
M halts on input M
Then loop forever
Else halt
Fall 2006
Costas Busch - RPI
38
Run F
with input itself
F
F
If
Copy F
on tape
F ,F
F halts on input F
Then F loops forever on input F
Else F halts on input F
CONTRADICTION!!!
Fall 2006
H
Costas Busch - RPI
END OF PROOF
39
We have shown:
Undecidable HALTTM
Decidable
Fall 2006
Costas Busch - RPI
40
We can actually show:
Turing-Acceptable
HALTTM
Decidable
Fall 2006
Costas Busch - RPI
41
HALTTM is Turing-Acceptable
Turing machine that accepts HALTTM :
1. Run M on input w
M ,w
Fall 2006
2. If M halts on w
then accept M ,w
Costas Busch - RPI
42

Download Report