Complexity Theory & Undecidability: Exploring Turing Machines
Delve into the realm of Complexity Theory, exploring problems solvable through computation, the decidability of languages, self-rejecting Turing machines, and undecidability results. Discover the intriguing concepts of contrived versus natural languages and the infamous halting problem in this fascinating journey.
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 problems Which problems can be solved can be solved through computation? through computation? 2
Which languages are decidable? Which languages are decidable? 3
Is Is every every language decidable? language decidable? 4
The liar paradox Are you selecting option B as your answer to this question? A: Yes B: No C: Yes D: Yes Respond at PollEv.com/whoza or text whoza to 22333 5
Self-rejecting Turing machines Let ? be a TM (with a large enough input alphabet) A strange-but-legal thing we can do: Run ? on ? Three possibilities: ? accepts ? ? rejects ? ? loops on ? Definition: We say that a Turing machine ? is self-rejecting if ? rejects ? 6
Self-rejecting Turing machines Let SELF-REJECTORS = ? ? is a self-rejecting Turing machine Lemma: SELF-REJECTORSis undecidable Proof: Let ?be any TM. We ll show that ? does not decide SELF-REJECTORS Case 1: ? is self-rejecting: ? SELF-REJECTORS, but ? rejects ? Case 2: ?isn t self-rejecting: ? SELF-REJECTORS, but ?doesn t reject ? Either way, ? fails! 7
Contrived vs. natural Admittedly, SELF-REJECTORS is a contrived language, cooked up purely for the sake of proving an undecidability result Are there undecidable languages that are natural/well-motivated/interesting? Yes! Key example: The halting problem 8
Here is an attempt at designing an algorithm that solves the halting problem: The halting problem Given ? and ?: 1. Simulate ? on w. 2. If it halts, accept; if it loops, reject. Problem: Given a Turing machine ? and an input ?, determine whether ? halts on ?. Roughly speaking, this is the problem of identifying bugs in someone else s code! Does the proposed algorithm work? A:No. Step 1 isn t legal, so the algorithm isn t well-defined B:No. Step 2 isn t legal, so the algorithm isn t well-defined D: No. The algorithm behaves incorrectly in some cases C: Yes Respond at PollEv.com/whoza or text whoza to 22333 9
The halting problem is undecidable Let HALT = { ?,? :? is a Turing machine that halts on input ?} Theorem: HALT is undecidable. Proof by contradiction: Assume that ?decides HALT Let s design an algorithm that decides SELF-REJECTORS. Given ? : 1. Construct ? , where ? is a modified version of ? in which the accept state has been replaced with a looping state 2. Simulate ? on ? , ? . If it accepts, accept; if it rejects, reject. 10
The Church-Turing thesis, revisited Let ? be a language Church-Turing Thesis: There exists an algorithm / procedure for figuring out whether a given string is in ? if and only if there exists a Turing machine that decides ?. Computation is an intuitive notion rooted in everyday human experience Could it be possible to solve the halting problem using science and technology? 11
Hypercomputers A hypercomputer is a hypothetical device that can solve some computational problem that cannot be solved by Turing machines, such as the halting problem Could it be possible that there are hypercomputers at the centers of stars? Inside black holes? Could it be possible to build a hypercomputer? 12
The Physical Church-Turing Thesis Let ? be a language Physical Church-Turing Thesis: It is physically possible to build a device that decides ? if and only if there exists a Turing machine that decides ?. 13
The Physical Church-Turing Thesis The standard Church-Turing thesis is a philosophical statement The Physical Church-Turing thesis is a scientific law Conceivably, it could be disproven by future discoveries but that would be very surprising Analogy: Second Law of Thermodynamics Analogy: Cannot travel faster than the speed of light 14
Undecidability First, we proved that SELF-REJECTORS is undecidable Then, we used the fact that SELF-REJECTORS is undecidable to prove that HALT is undecidable Next, let s use the fact that HALT is undecidable to prove that other interesting languages are undecidable 15
Complement of the halting problem Let HALT = { ?,? :? does not halt on ?} Claim: HALT is undecidable Proof by contradiction: Assume that ? decides HALT Let s design an algorithm that decides HALT. Given ?,? : 1. Run ? on ?,? Technicality: The first step of our algorithm should be to confirm that the input is valid, i.e., 2. If it accepts, reject; if it rejects, accept. confirm that the input has the form ?,? for some Turing machine ? and some input ? to ? 16
The acceptance problem Let ATM= { ?,? :? is a Turing machine that accepts input ?} Claim: ATM is undecidable Proof by contradiction: Assume that ?decides ATM Let s design an algorithm that decides HALT. Given ?,? : 1. Construct ? , where ? is a modified version of ? in which all rejecting transitions have been changed into accepting transitions 2. Simulate ? on ? ,? . If it accepts, accept; if it rejects, reject. 17
