Essential Question: What is an undecidable problem?
Mastery Objectives:
SWBAT tell whether a problem is undecidable or not.
Imagine an island somewhere with two large families. One family (unlike normal people) can tell only the truth, even when they'd rather lie. This Truth-teller family can't ever make false statements, even by mistake. The other family, the False-Teller family, is just as reliable but in the opposite way: they can't make true statements ever.
You are visiting the island and meet two of its people, Diego and Zoey. Diego says, "Zoey and I are from the same family."
Can you say for sure which family Zoey is from? If so, which family?
Can you say for sure which family Diego is from? If so, which family?
Many problems can be solved in reasonable or polynomial time.
Reasonable time means the number of steps
Resources: https://app.nearpod.com/?pin=FXHPG
https://www.youtube.com/watch?v=oO9nFOo8q_c - video on polynomial time
Directions: Using Snap, program the code in the following link and see if you can replicate the halting problem:
Exercise 1: These discussions aren't meant to be handed in; instead, you might have a whole-class discussion after the partners have a chance for their small-group discussions.
In a proof by contradiction, you start by assuming the opposite of what you're trying to prove, and from there you derive a contradiction. You prove that the opposite can't be true, which means the original goal must be true. (By the way, although it's an unusual position today, around 1900 there was a strong group of mathematicians who rejected proof by contradiction. So if your students have trouble with the idea, they're in good company!)
The halts? function takes a reporter (that is, a function; for example, f) and an input value (an argument; for example, x) and reports true if and only if the computation of f(x) will report a value in finite time. In other words, halts? is (supposedly) able to detect an infinite loop in any program. (Note that this proof would be impossible in a programming language in which procedures can't be used as data, that is, in which a function couldn't be used as input to another function, such as inputting f into halts?. The Halting Theorem would still be true, but proving it would be a lot harder—as it was for Turing.)
We construct a procedure tester so that it reports a value if and only if halts? says that f(f) loops forever for some given function f but also so that tester loops forever if halts? says that f(f) reports a value. So, whatever f does, tester does the opposite. Then we call tester on itself: tester(tester). Whatever halts? says that tester will do, tester will be forced to actually do the opposite. That's a contradiction, and so an infallible halts? can't exist.