Undecidable Problems
(unsolvable problems)
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
A computational problem is decidable
if the corresponding language is decidable
We also say that the problem is solvable
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)
Decider for EMPTYDFA :
On input M :
Determine whether there is a path from
the initial state to any accepting state
Decision:
DFA M
DFA M
L (M )
L (M )
Reject M
Accept M
Problem: Does DFA M accept
a finite language?
Corresponding Language:
X
(Decidable)
FINITE DFA
{ M : M is a DFA that accepts a finite language }
Decider for FINITE DFA :
On input M :
Check if there is a walk with a cycle
from the initial state to an accepting state
DFA M
Decision:
DFA M
infinite
finite
Reject M
(NO)
Accept M
(YES)
Problem: Does DFA M
Corresponding Language:
X
accept string w ?
(Decidable)
ADFA
{ M ,w : M is a DFA that accepts string w }
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)
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 }
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)
( L1 L2 ) ( L1 L2 )
L1 L2
L1
and
L2 L
2
L1 L2
L1 L2
L2
L1 L1
L2 L1
L1 L2
( L1 L2 ) ( L1 L2 )
L1 L2
L1
or
L1 L2
L2
L2
L1 L2
L1
L2 L1
L1 L2
Therefore, we only need
to determine whether
L(M ) (L1 L2 ) (L1 L2 )
which is a solvable problem for DFAs:
EMPTYDFA
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)
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)
We have shown before that there are
undecidable languages:
L
Turing-Acceptable
Decidable
is Turing-Acceptable and undecidable
We will prove that two particular problems
are unsolvable:
Membership problem
Halting problem
Membership Problem
Input:
Turing Machine
String w
Question:
Does M
accept w ?
w L(M ) ?
Corresponding language:
ATM { M ,w : M is a Turing machine that
accepts string w }
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!
Suppose that
Input
string
M ,w
ATM is decidable
Decider
for ATM
YES
accepts
NO
rejects
Let
be a Turing recognizable language
Let ML be the Turing Machine that accepts
We will prove that
is also decidable:
we will build a decider for
String description of ML
Decider for
ML
Decider for ATM
ML accepts s ?
s
Input
string
YES
accept s
(and halt)
NO
reject s
(and halt)
Therefore,
is decidable
Since L is chosen arbitrarily, every
Turing-Acceptable language is decidable
But there is a Turing-Acceptable language
which is undecidable
Contradiction!!!!
END OF PROOF
We have shown:
Undecidable
Decidable
ATM
We can actually show:
Turing-Acceptable
Decidable
ATM
ATM is Turing-Acceptable
Turing machine that accepts
1. Run M on input
M ,w
ATM :
2. If M accepts w
then accept M ,w
Halting Problem
Input:
Turing Machine
String w
Question:
Does M halt while
processing input string w ?
Corresponding language:
HALTTM { M ,w : M is a Turing machine that
halts on input string w }
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!
Suppose that
HALTTM is decidable
Input
string
M ,w
M
w
Decider for
HALTTM
YES
NO
halts on
input
doesnt halt
on input
Let
Let
be a Turing-Acceptable language
ML be the Turing Machine that accepts L
We will prove that
is also decidable:
we will build a decider for
Decider for
ML
s
Input
string
Decider for
HALTTM
ML halts on s ?
L
NO
YES
ML halts
Run ML
with input s
and accepts
ML halts
and rejects
reject s
and halt
accept s
and halt
reject s
and halt
Therefore,
is decidable
Since L is chosen arbitrarily, every
Turing-Acceptable language is decidable
But there is a Turing-Acceptable language
which is undecidable
Contradiction!!!!
END OF PROOF
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
Suppose that
Input
string
M ,w
M
w
HALTTM is decidable
Decider
for HALTTM
YES
NO
halts on
doesnt
halt on
Looking inside
Decider for HALTTM
Input string:
M ,w
H
q0
qaccept YES
halts on
w?
qreject NO
Construct machine
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
Construct machine F :
F
M
Copy M
on tape
If
M, M
M halts on input M
Then loop forever
Else halt
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!!!
END OF PROOF
We have shown:
Undecidable HALTTM
Decidable
We can actually show:
Turing-Acceptable
Decidable
HALTTM
HALTTM is Turing-Acceptable
Turing machine that accepts HALTTM :
1. Run M on input
M ,w
2. If M halts on w
then accept M ,w