Unit 5 Lab 4
Unsolvable and Undecidable Problems
In this lab, you will learn that some problems can't be solved at all.
Proof by Contradiction
In this section, you will solve logic puzzles by finding a contradiction, that is, by showing that one possibility has to be true because the other possibility doesn't make sense.
Vocabulary
Click each word to view the definition.
Proof by Contradiction
A proof by contradiction is a two-step proof that something is false that is done by:
1) assuming that it's true
2) showing how that's impossible (that it creates a contradiction)
Undecidable Statement
An undecidable statement might be true or might be false; we don't know which.
Self-Contradictory Statement
A self-contradictory statement can be neither true nor false.
If There is Time
Need to add If There is Time Slides
Take It Further
Need to add Take It Further Slides
An Undecidable Problem
In this section, you will consider a problem that can't have an answer.
Vocabulary
Click each word to view the definition.
Infinite Loop
An infinite loop is a sequence of computer instructions that repeats forever.
Unsolvable Problem
An unsolvable problem is one for which no algorithm can ever be written to find the solution.
Undecidable Problem
An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value. Undecidable problems are a subcategory of unsolvable problems that include only problems that should have a yes/no answer (such as: does my code have a bug?).