Undecidability Consequences and Other Problems in Computer Science
CMSC 281
Consequences
of the Undecidability of A
TM
Other Undecidable Problems
•
I stated that there are zillions of problems that are not decidable.
•
Remember that A
TM
={<M,w> M accepts w} is not decidable.
•
Note that A
TM
={<M,w> M accepts w} is trivially recognizable
by a Tm:
The Universal Turing Machine simulates M running on input w, and
accepts iff M accepts w.
Lemma
: L and co-L are both recognizable iff L is decidable.
(co-L is the set of strings not in L)
Other Undecidable Problems
•
Lemma
: L and co-L are both recognizable iff L is decidable
•
Proof
: A decider for L accepts L. Exchanging q
accept
and q
reject
in this Tm gives us a Tm that accepts co-L.
For the other direction, let M
1
and M
2
be Tms that recognize L and co-L
respectively. Consider the Tm M that on input x simulates both M
1
and
M
2
(say it simulates one step of M
1
, then one step of M
2
, then the
next step of M
1
, …) One of the two processes will terminate. M
outputs the correct answer.
Other Undecidable Problems
•
Lemma
: L and co-L are both recognizable iff L is decidable
•
We can now exhibit a language that cannot be recognized by any Tm.
Claim
: co-A
TM
is not c.e.
Proof
: if co-A
TM
were c.e., since A
TM
is c.e., by the Lemma A
TM
would be
decidable.
Other Undecidable Problems
L be a language recognized by a Tm M.
We can assume wlog that for all strings x not in L M does not halt.
Proof: modify M so that all transitions into the state q
reject
go instead to
a new state q
new
, and all transition from q
new
lead back to q
new
Such a machine rejects by not halting, and accepts by halting.
Other Undecidable Problems
L be a language recognized by a Tm M.
We can assume wlog that for all strings x not in L, M does not halt.
Such a machine rejects by not halting, and accepts by halting.
Consider the language HALT
TM
={<M,w> Tm M halts on input w}This is called the
Halting Problem
.
Other Undecidable Problems
L be a language recognized by a Tm M.
We can assume wlog that for all strings x not in L, M does not halt.
Such a machine rejects by not halting, and accepts by halting.
Consider the language HALT
TM
={<M,w> Tm M halts on input w}This is called the Halting Problem.
Claim: The Halting Problem is undecidable.
Proof: if it were decidable, we could decide A
TM
Other Undecidable Problems
L be a language recognized by a Tm M.
We can assume wlog that for all strings x not in L, M does not halt.
Such a machine rejects by not halting, and accepts by halting.
Consider the language HALT
TM
={<M,w> Tm M halts on input w}This is called the Halting Problem.
Claim: The Halting Problem is undecidable.
Proof: if it were decidable, we could decide A
TM
Note: this is Theorem 5.1 in Sipser, who offers a slightly different proof.
Other Undecidable Problems
Def. Tms M
1
and M
2
are
equivalent
if for every string x
M
1
halts on x iff M
2
halts on x and
M
1
accepts x iff M
2
accepts x
(note that if we use Tms that reject by not halting, then the first
condition suffices)
EQ
TM
={<M1
,M
2
> M
1
and M
2
are equivalent}
Theorem
: EQ
TM
is undecidable.
Other Undecidable Problems
EQ
TM
={<M1
,M
2
> M
1
and M
2
are equivalent}
Theorem
: EQ
TM
is undecidable.
Proof
: We will show that if it were decidable A
TM
would be decidable.
Given <M,w>, let M
1
be the Tm that on every input x simulates M with
input w. So, for every input x, M
1
halts (and accepts) iff M accepts w.
Let M
2
be the Tm that halts for no input.
Then < M
1
,M
2
> is NOT in EQ
TM
iff M accepts w, iff <M,w> is in A
TM
So, we produced an algorithm that decides A
TM
- a contradiction.
Explore the undecidability of the Acceptance Turing Machine (ATM) and its implications in recognizing languages, including the relationship between decidability and recognizability. Discover the undecidability of the Halting Problem and its significance in computational theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMSC 281 Consequences of the Undecidability of ATM
Other Undecidable Problems I stated that there are zillions of problems that are not decidable. Remember that ATM={<M,w> M accepts w} is not decidable. Note that ATM={<M,w> M accepts w} is trivially recognizable by a Tm: The Universal Turing Machine simulates M running on input w, and accepts iff M accepts w. Lemma: L and co-L are both recognizable iff L is decidable. (co-L is the set of strings not in L)
Other Undecidable Problems Lemma: L and co-L are both recognizable iff L is decidable Proof: A decider for L accepts L. Exchanging qacceptand qreject in this Tm gives us a Tm that accepts co-L. For the other direction, let M1and M2 be Tms that recognize L and co-L respectively. Consider the Tm M that on input x simulates both M1 and M2 (say it simulates one step of M1, then one step of M2, then the next step of M1, ) One of the two processes will terminate. M outputs the correct answer.
Other Undecidable Problems Lemma: L and co-L are both recognizable iff L is decidable We can now exhibit a language that cannot be recognized by any Tm. Claim: co-ATMis not c.e. Proof: if co-ATMwere c.e., since ATMis c.e., by the Lemma ATMwould be decidable.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L M does not halt. Proof: modify M so that all transitions into the state qrejectgo instead to a new state qnew, and all transition from qnewlead back to qnew Such a machine rejects by not halting, and accepts by halting.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem. Claim: The Halting Problem is undecidable. Proof: if it were decidable, we could decide ATM
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem. Claim: The Halting Problem is undecidable. Proof: if it were decidable, we could decide ATM Note: this is Theorem 5.1 in Sipser, who offers a slightly different proof.
Other Undecidable Problems Def. Tms M1and M2are equivalent if for every string x M1 halts on x iff M2halts on x and M1 accepts x iff M2accepts x (note that if we use Tms that reject by not halting, then the first condition suffices) EQTM={<M1,M2> M1and M2are equivalent} Theorem: EQTMis undecidable.
Other Undecidable Problems EQTM={<M1,M2> M1and M2are equivalent} Theorem: EQTMis undecidable. Proof: We will show that if it were decidable ATMwould be decidable. Given <M,w>, let M1be the Tm that on every input x simulates M with input w. So, for every input x, M1 halts (and accepts) iff M accepts w. Let M2 be the Tm that halts for no input. Then < M1,M2> is NOT in EQTMiff M accepts w, iff <M,w> is in ATM So, we produced an algorithm that decides ATM - a contradiction.
