Exploring Undecidability in Complexity Theory
Delve into the concept of undecidability in complexity theory, examining decidable and undecidable languages, as well as the Post's Correspondence Problem with illustrative examples and visual aids. Understand the boundaries of analysis in Turing machines and different types of undecidable problems beyond traditional analysis approaches.
Uploaded on | 0 Views
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 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
Which languages are decidable? Which languages are decidable? 2
Undecidability We have seen several examples of undecidable languages SELF-REJECTORS, HALT, HALT, ATM, ETM 3
Undecidability beyond analysis of TMs So far, every undecidable problem we have seen has been a problem about analyzing the behavior of a given Turing machine Does it halt on such-and-such input? Is there any input it accepts? Etc. What else is undecidable? 4
Posts Correspondence Problem Given: An alphabet and two sequences of strings ?1, ,??,?1, ,?? Goal: Determine whether there exists a sequence of indices ?1, ,?? such that ??1??2 ???= ??1??2 ??? 5
Posts Correspondence Problem Helpful picture: We are given a set of dominos ?3 ?3 ?? ?? ?1 ?1 ?2 ?2 Goal: Determine whether it is possible to generate a match ??5 ??5 ??? ??? ??3 ??3 ??1 ??1 ??2 ??2 ??4 ??4 in which the sequence of symbols on top equals the sequence of symbols on the bottom Using the same domino multiple times is permitted 6
Posts Correspondence Problem: Example 1 Suppose we are given 1 0 11 0 1 00 This is a YES case. Match: 1100 1100 11 0 1 0 1 00 7
Posts Correspondence Problem: Example 2 Suppose we are given MP OM N UT PU CO C IO T AT TA ION This is a YES case because there is a match: COMPUTATION COMPUTATION UT PU N MP OM CO C AT TA IO T ION and another match: UT PU N MP OM CO C IO T COMPUTION COMPUTION ION 8
Posts Correspondence Problem: Example 3 Suppose we are given 0 010 10 1 01 01 0 This is a NO case. Proof: A match would have to start with , 01 and consequently, we will always have more ones on the bottom than on the top 9
Posts Correspondence Problem is undecidable Define PCP = { ,?1, ,??,?1, ,?? ?1, ,?? such that ??1 ???= ??1 ???} Theorem: PCP is undecidable Proof outline: Step 1: Show that a modified version ( MPCP ) is undecidable by reduction from HALT Step 2: Show that PCP is undecidable by reduction from MPCP 10
Modified PCP MPCP = { ,?1, ,??,?1, ,?? ?1, ,?? such that ?1??1 ???= ?1??1 ???} The difference between PCP and MPCP: In MPCP, matches must start with the first domino 11
Reduction from HALT to MPCP To show that MPCP is undecidable, we will design a mapping reduction ? ?,? = ,?1, ,??,?1, ,?? We will ensure that: If ? halts on ?, then there is a match ( YES maps to YES ) If ? loops on ?, then there is no match ( NO maps to NO ) The function ? is computable 12
Reduction from HALT to MPCP For the reduction, we are given ?,? , where ? = ?, , , , ,?,?0,?accept,?reject Our job is to produce a sequence of dominos Plan: Produce dominos such that constructing a match is equivalent to constructing a halting computation history 13
Given ?,?, how would we compute ? ?,? ? Reduction from HALT to MPCP A: Simulate ? on ?. If it accepts, accept; if it rejects, reject B: Simulate ? on ? and copy whatever dominos it produces We produce the following dominos: C: There does not exist an algorithm that computes ? D: Inspect the transition function of ? to figure out the dominos Respond at PollEv.com/whoza or text whoza to 22333 ? ?accept# ? ?reject# ? # # # , ?0? # , , , and # Reduction is computable ?? ? ? for every ?,?,? ,? such that ? ?,? = (? ,? ,R) and ? ?accept,?reject ??? for every ?,?,? ,? ,? such that ? ?,? = (? ,? ,L) and ? ?accept,?reject ? ?? ?? ? ?? ? ? ? for every ? and ? ?accept,?reject , , and 14
Domino feature 1 Let ? = ??? be a configuration where ? ? and ?? starts with Fact: There is a sequence of dominos such that the top string is ? and bottom string is NEXT ? ? Think of this sequence as one super-domino NEXT ? 15
YES maps to YES Let ?0, ,?? be the halting computation history of ? on ? = ?? ?, and note that NEXT ?? = ??+1 Let ?? Partial match: ? ?? 1 ?? ?0 ?1 ?1 ?2 # # # # # ?0? # # # # # on the bottom At this point, we have an extra ?? 16
Domino feature 2 Fact: For every halting configuration ? with ? > 1, there is a sequence of dominos such that the top string is ? and the bottom string is a halting configuration ? with ? = ? 1 ? ? ?? ?? ? ? Proof: Use the , , and ? ? dominos to effectively delete one symbol from ? 17
YES maps to YES , we construct a sequence of shorter and shorter Starting with ?0= ?? ?? 1 ?? halting configurations ?1, ,?? such that we have a super-domino for every ?, until eventually we reach ?? ?accept,?reject Full match: ? ?? 1 ?? ?0 ?1 ?? 1 ?? ?0 ?1 ?1 ?2 ?1 ?2 ??# ? # # # # # # # # # # # # # ?0? # # # # 18
NO maps to NO Suppose ? loops on ?. Let ?0,?1,?2, be the computation history of ? on ? (an infinite sequence of configurations) Assume, for the sake of contradiction, that there is a match 19
