Completeness in C.E. Languages
Understanding completeness in C.E. languages is key to recognizing the limitations and capabilities of Turing recognizability. This concept delves into the intricacies of mapping reductions, Turing reductions, and the decidability of C.E. languages. Explore the theorems, proofs, and corollaries that characterize the completeness of languages within the C.E. class.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
CMSC 281 Completeness
Completeness Recall: language L is c.e. (Turing recognizable) if ?? ?:? = ? ? = ?:? ?????????? ? Definition: L is hard for a class ? of languages under mapping reductions under Turing reductions ?, ? ?, ?? ?, ? ?, ?? ? is complete for ? if it is hard for ? and ? ?
Completeness Definition: ? is complete for the class of c.e.languages i. c.e.?, ?, ?? ii.L is c.e. Theorem: ???= < ?,? > ? ??????? ? is complete for c.e. languages under mapping reductions.
Completeness Definition: ? is complete for the class of c.e.languages i. c.e.?, ?, ?? ii. L is c.e. Theorem: ???= < ?,? > ? ??????? ? is complete for c.e. languages under mapping reductions. Proof: if L, is c.e. L =L(M) for some Tm M.
Completeness Definition: ? is complete for the class of c.e.languages i. c.e.?, ?, ?? ii. L is c.e. Theorem: ???= < ?,? > ? ??????? ? is complete for c.e. languages under mapping reductions. Proof: if L is c.e. L =L(M) for some Tm M. Let f(x)=<M,x>. Then ? ? ? ? ? ???
Completeness Definition: ? is complete for the class of c.e.languages i. c.e.?, ?, ?? ii. L is c.e. Theorem: ???= < ?,? > ? accepts ? is complete for c.e. languages under mapping reductions. Corollary: ???= < ?,? > ? accepts ? is complete for c.e. languages under Turing reductions.
Completeness Definition: ? is complete for the class of c.e.languages i. c.e.?, ?, ?? ii. L is c.e. Theorem: ???= < ?,? > ? accepts ? is complete for c.e. languages under mapping reductions. Corollary: ???= < ?,? > ? accepts ? is complete for c.e. languages under Turing reductions. Corollary: HALTTM= < ?,? > ? halts on input ? is complete for c.e. languages under mapping (or Turing) reductions.
Completeness ???= < ?,? > ? accepts ? is complete for c.e. languages under Turing reductions. This means that every c.e. language is decidable by an oracle Tm with oracle set ATM.
Completeness ???= < ?,? > ? accepts ? is complete for c.e. languages under Turing reductions. This means that every c.e. language is decidable by an oracle Tm with oracle set ATM. What if we somehow had ATM? Could we decide every language?
Completeness ???= < ?,? > ? accepts ? is complete for c.e. languages under Turing reductions. This means that every c.e. language is decidable by an oracle Tm with oracle set ATM. What if we somehow had ATM? Could we decide every language? NO!
Given ATM, every c.e. language is decidable. But, what about ATMHP ={< ?,? > ??oracle Tm ? with oracle A=ATM accepts?} ??
Given ATM, every c.e. language is decidable. But, what about ATMHP ={< ?,? > ??oracle Tm ? with oracle A=ATM accepts?} ?? Claim: ATMHPis not decidable by oracle Turing machines with oracle ATM
Given ATM, every c.e. language is decidable. But, what about ATMHP ={< ?,? > ??oracle Tm ? with oracle A=ATM accepts?} ?? Claim: ATMHPis not decidable by oracle Turing machines with oracle ATM Proof: Do Exercise!
Given ATM, every c.e. language is decidable. But, what about ATMHP ={< ?,? > ??oracle Tm ? with oracle A=ATM accepts?} ?? Claim: ATMHPis not decidable by oracle Turing machines with oracle ATM Proof: Do Exercise! Just reproduce the problem of undecidability of ATM Replace every occurrence of Tm M by oracle Tm M with oracle ATM
This goes on .. Given ATM, every c.e. language is decidable --- equivalent to: Every language recognizable by oracle Tms with the empty oracle ,is decidable by an oracle Tm with oracle A1=ATM Every language recognizable by oracle Tm with oracle ATM is decidable by an oracle Tm with oracle A2= {< ?,? > oracle Tm ? with oracle ATM accepts w}
This goes on .. Given ATM, every c.e. language is decidable --- equivalent to: Every language recognizable by oracle Tms with the empty oracle ,is decidable by an oracle Tm with oracle A1=ATM Every language recognizable by oracle Tm with oracle A1 is decidable by an oracle Tm with oracle A2= {< ?,? > oracle Tm ? with oracle A1 accepts w} Every language recognizable by oracle Tm with oracle A2 is decidable by an oracle Tm with oracle A3= {< ?,? > oracle Tm ? with oracle A2 accepts w} .
This goes on .. Given ATM, every c.e. language is decidable --- equivalent to: Every language recognizable by oracle Tms with the empty oracle ,is decidable by an oracle Tm with oracle A1=ATM Every language recognizable by oracle Tm with oracle ATM is decidable by an oracle Tm with oracle A2= {< ?,? > oracle Tm ? with oracle A1 accepts w} Every language recognizable by oracle Tm with oracle A2 is decidable by an oracle Tm with oracle A3= {< ?,? > oracle Tm ? with oracle A2 accepts w}
