Understanding Computability Theory: Exploring Algorithm Solvability
Delve into Computability Theory to uncover the limitations of algorithmic solutions, focusing on decision problems and the concept of solvability through algorithms. Discover the intriguing Halting Problem and why some problems are inherently unsolvable by algorithms, regardless of time and space constraints.
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
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 40: Computability theory and course review
Computability Theory So far, we have been concerned with the complexity of solving problems. If we ignore complexity, can we develop algorithms to solve any given problem?
Computability Theory So far, we have been concerned with the complexity of solving problems. If we ignore complexity, can we develop algorithms to solve any given problem? Answer. NO. there are problems that cannot be solved by algorithms, no matter how much time and space you spend.
Computability Theory So far, we have been concerned with the complexity of solving problems. If we ignore complexity, can we develop algorithms to solve any given problem? Answer. NO. there are problems that cannot be solved by algorithms, no matter how much time and space you spend. Let us focus on decision problems. Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no).
Computability Theory So far, we have been concerned with the complexity of solving problems. If we ignore complexity, can we develop algorithms to solve any given problem? Answer. NO. there are problems that cannot be solved by algorithms, no matter how much time and space you spend. Let us focus on decision problems. Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A decision problem is solvable/computable/recursive if it is solved by an algorithm.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Theorem. Problem Halting is not solvable.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise A1(P, x) =
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P?
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Let the new algorithm be A3. 1. A3(P) does not halt if A2(P) = yes ; 2. A3(P) halts if A2(P) = no ; Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Let the new algorithm be A3. 1. A3(P) does not halt if A2(P) = yes ; 2. A3(P) halts if A2(P) = no ; Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise Question: Does A3 halt on A3? A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Let the new algorithm be A3. 1. A3(P) does not halt if A2(P) = yes ; 2. A3(P) halts if A2(P) = no ; Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise Question: Does A3 halt on A3? If yes (i.e., A3 halts on A3: A3(A3) halts): A2(A3) returns no A1(A3 ,A3) returns no A3 does not halt on A3. A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Let the new algorithm be A3. 1. A3(P) does not halt if A2(P) = yes ; 2. A3(P) halts if A2(P) = no ; Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise Question: Does A3 halt on A3? If yes (i.e., A3 halts on A3: A3(A3) halts): A2(A3) returns no A1(A3 ,A3) returns no A3 does not halt on A3. If no (i.e., A3 not halts on A3: A3(A3) not halts): A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? A2(A3) returns yes A1(A3 ,A3) returns yes A3 halts on A3. Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Now modify the algorithm A2: 1. replace each return(yes) in A2 by a dead looping; 2. replace each return(no) in A2by stop . Consider the following problem: Halting Problem. Input: (P, x), P is a program, x is input to P. Question: does P halt on input x? Let the new algorithm be A3. 1. A3(P) does not halt if A2(P) = yes ; 2. A3(P) halts if A2(P) = no ; Theorem. Problem Halting is not solvable. Proof. Assume the contrary, Halting is solved by an always-halt algorithm A1: yes if P halts on x no otherwise Question: Does A3 halt on A3? If yes (i.e., A3 halts on A3: A3(A3) halts): A2(A3) returns no A1(A3 ,A3) returns no A3 does not halt on A3. If no (i.e., A3 not halts on A3: A3(A3) not halts: A1(P, x) = Define a new problem: Halt-on-Self Problem. Input: a program P Question: does P halt on P? A2(A3) returns yes A1(A3 ,A3) returns yes A3 halts on A3. We always get a contradiction. The contradiction shows that Halting is not solvable. Problem Halt-on-Self is solved by this always-halt algorithm: A2(P) return A1(P, P).
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable. This means that there is no algorithm that can solve Halting, no matter how much power (time, space) we give to the computer.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable. This means that there is no algorithm that can solve Halting, no matter how much power (time, space) we give to the computer. Using the ideas very similar to poly- time reductions in NP-completeness theory, we can identify other unsolvable problems.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Definition. Let Q1 and Q2 be decision problems. We say that Q1 is reducible to Q2, Q1 Q2, if there is an always-halt algorithm T such that x is yes for Q1 if and only if T(x) is yes for Q2. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable. Q1 Q2 x T T(x) This means that there is no algorithm that can solve Halting, no matter how much power (time, space) we give to the computer. Using the ideas very similar to poly- time reductions in NP-completeness theory, we can identify other unsolvable problems.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Definition. Let Q1 and Q2 be decision problems. We say that Q1 is reducible to Q2, Q1 Q2, if there is an always-halt algorithm T such that x is yes for Q1 if and only if T(x) is yes for Q2. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable. Q1 Q2 x T T(x) This means that there is no algorithm that can solve Halting, no matter how much power (time, space) we give to the computer. Lemma. If Q1 Q2, then (1) If Q2 is solvable then so is Q1. (2) If Q1 is unsolvable then so is Q2. Using the ideas very similar to poly- time reductions in NP-completeness theory, we can identify other unsolvable problems.
Computability Theory Definition. An algorithm A solves a (decision) problem Q if on every input x, the algorithm A(x) halts (with an answer yes/no). Definition. A (decision) problem is solvable/computable/recursive if it is solved by an algorithm. Definition. Let Q1 and Q2 be decision problems. We say that Q1 is reducible to Q2, Q1 Q2, if there is an always-halt algorithm T such that x is yes for Q1 if and only if T(x) is yes for Q2. Halting Problem. Input: (P, x), P: a program, x: input to P. Question: does P halt on input x? Theorem. The Halting problem is not solvable. Q1 Q2 x T T(x) This means that there is no algorithm that can solve Halting, no matter how much power (time, space) we give to the computer. Lemma. If Q1 Q2, then (1) If Q2 is solvable then so is Q1. (2) If Q1 is unsolvable then so is Q2. Using the ideas very similar to poly- time reductions in NP-completeness theory, we can identify other unsolvable problems. Using this theorem, people have identified many unsolvable problems. In particular, most problems for testing program correctness are unsolvable.
Review for Final Exam (May 6, 10:30am12:30pm) Comprehensive, cover all materials we studied this semester.
Review for Final Exam (May 6, 10:30am12:30pm) Comprehensive, cover all materials we studied this semester. O-notation, recursive algorithms, recurrence relations. Heapsort, applications of heap structure. Lower bound for sorting, linear-time sorting algorithms. BFS and DFS: algorithms, analysis, and complexity Applications of BFS/DFS: topological sorting, SCC, and others. Shortest-path problem: Dijkstra, Bellman-Ford, Floyd-Warshall. Algorithms for minimum spanning trees and graph matching. The classes P, NP and their relation, poly-time reductions. NP-hardness and NP-completeness. NP-complete problems: SAT, IS, VC, Subset-Sum, Partition Simple poly-time reductions to prove NP-hardness. Computability theory, reductions, unsolvable problem. directed graph
Review for Final Exam (May 6, 10:30am12:30pm) Comprehensive, cover all materials we studied this semester. O-notation, recursive algorithms, recurrence relations. Heapsort, applications of heap structure. Lower bound for sorting, linear-time sorting algorithms. BFS and DFS: algorithms, analysis, and complexity Applications of BFS/DFS: topological sorting, SCC, and others. Shortest-path problem: Dijkstra, Bellman-Ford, Floyd-Warshall. Algorithms for minimum spanning trees and graph matching. The classes P, NP and their relation, poly-time reductions. NP-hardness and NP-completeness. NP-complete problems: SAT, IS, VC, Subset-Sum, Partition Simple poly-time reductions to prove NP-hardness. Computability theory, reductions, unsolvable problem. directed graph Additional Office Hours: April 30-May 1: 2:00 pm 3:00 pm
