layout: post title: Undecidable Problems description: Lesson for Undecidable Problems courses: {‘csp’: {‘week:1’: None}} menu: nav/lessons.html permalink: /lesson/3-3 comments: True —
Teaching Undecidable Problems
Undecidable Problems:
As college board explained it, Undecidable Problems is one for which no algorithm can be constructed that is always capable of providing a correct yes or no answer. This means that an algorithm cannot provide an outputs for given inputs. In the CSP curriculum, a undecideabl problems has some key features:
- Most importantly, an algorithm becomes undecidable even if some instances have a solution, but not all solutions have one
- Conceptually, undecidability demonstrates the inherent limits of what algorithms can achieve.
A decidable problem is a decision problem for wich an algorithm can be writen to produce a correct output for all inputs(eg.”Is the number even?”) This is different from an undecidable problem which may have an algorithim that works, but it can never fully work, and there are always instances in wich that is the case to make a problem undecidable.
The Halting Problem College Board exemplified undecidable problems through the Halting Problem. This program takes an input and will either eventually stop (halt) or run forever. This program cannot exist beacuse it would create an impossible scenario. This was proven by Alan Turing, and it shows that some problems can never be solved by an algorithm, no matter how powerful computers become. There is no way to test for the ending, if there is no ending.
Analogy Real-Life Analogy: The Halting Problem Imagine trying to predict if a friend will ever stop talking during a conversation.
You know that sometimes they talk a lot… but what if they never stop?
- You can’t interrupt.
- You can’t fast forward.
- You can only listen and hope they eventually stop.
Now imagine you’re given a recording of your friend talking, and you’re asked before hitting play: “Will this person stop talking at some point, or will they talk forever?”
There’s no way to know for sure without actually listening all the way through, which defeats the purpose of predicting it beforehand. You’ll never have a yes/no answer.
Another example of this problem is shown here:
num = 10
while num != 0:
print(num)
num -= 1
Cell In[5], line 1
num ← 10
^
SyntaxError: invalid character '←' (U+2190)
num = 1
while num != 0:
print(num)
num += 1
Popcorn Hack #1: Explain why there is an undecidable problem above.
Pilot City We can potentially find undecidable problems in our Pilot City project where we would find our website or program taking too long to load. It may never load or even just take a long time, but your computer would eventually just stop running the program.
Decidable example
def divisibleByThree(num):
if num MOD 3 == 0:
return True
else:
return False
This determines if a number is divisible by 3. This example is decidable because we know that the algorithm would always provide a corrcet output.
Complexity
- Undecidable problems have been proven to have no algorithm that works for all cases using current models of computation.
- However we are always developing new technology and discovering what was once believed to be impossible
- The internet: Seemed like science fiction a century ago.
- Computation models could evolve from classical logic and machines
Popcorn Hack #2: Practice from College Board (Answer these in your blog)
#1. An algorithm can be used to solve an undecidable problem (True or False)
#2. If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time. (True or False)
HOMEWORK Part 1: Identify the Problem Type Read the following problems and decide whether they are decidable or undecidable. Write your answer and a short reason why.
“Is this number divisible by 2?”
“Will this program stop or run forever?”
“Does this sentence contain the word ‘banana’?”
“Will this AI ever become sentient?”
Part 2: Algorithm Detective (2 minutes) Look at the two mystery “algorithms” below. Figure out which one is decidable and which one is undecidable, then explain your reasoning in one sentence each.
Step 1: Input a number
Step 2: If the number is even, say "Yes." If not, say "No."
Step 1: Input any program
Step 2: Predict if it will ever stop running
Step 3: Output "Yes" if it will stop, "No" if it will run forever
Part 3: Real-Life Connection
Think of something in real life where you can’t be sure what will happen unless you go through the entire experience.
Teaching Undeciedable Problems
Undeciedable Problems:
As college board explained it, Undeciedable Problems is one for which no algorithm can be constructed that is always capable of providing a correct yes or no answer. This means that an algorithm cannot provide an outputs for given inputs. In the CSP curriculum, a undecideabl problems has some key features:
- Most importantly, an algorithm becomes undecidable even if some instances have a solution, but not all solutions have one
- Conceptually, undecidability demonstrates the inherent limits of what algorithms can achieve.
The Halting Problem College Board exemplified this through the Halting Problem. This program takes an input and will either eventually stop (halt) or run forever. This program cannot exist beacuse it would create an impossible scenario. This was proven by Alan Turing, and it shows that some problems can never be solved by an algorithm, no matter how powerful computers become.
A decidable problem is a decision problem for wich an algorithm can be writen to produce a correct output for all inputs(eg.”Is the number even?”) An undecidable problem is a problem that has no algorithim that can provide a yes or no answer, An undecidable problem may have an algorithim that works, but it can never fully work, and there are always instances in wich that is the case to make a problem undecidable.
from IPython.display import Image, display
# Display the image
display(Image(filename='und.png'))
