Undecidable Problems: Questions No Program Can Always Answer

Q: What is check your understanding in Python?

Exam topics: 3.18 Undecidable Problems (AAP-4.B)

Intermediate25 min2 exercises25 XP

Prerequisites

Algorithmic Efficiency and Heuristics: Reasonable and Unreasonable Time Python While Loops: When For Loops Aren't Enough Python Functions: Define, Call, and Return Values

0/2 exercises

Some yes-or-no questions can be answered by a program for every possible input, and some cannot be answered by any program at all, no matter how fast the computer or how clever the programmer.

What is a decidable problem?

A decision problem is a question with a yes-or-no answer, like "Is this number even?" or "Is this password longer than 12 characters?". Each specific input, such as the number 41, is an instance of the problem.

A decision problem is decidable when someone can write an algorithm that gives the correct yes-or-no answer for every input. "Is the number even?" is decidable: divide by 2 and look at the remainder. The algorithm always finishes, and it is always right.

Two decidable problems: every input gets a correct answer

def is_even(n):

return n % 2 == 0

def is_prime(n):

if n < 2:

return False

divisor = 2

while divisor * divisor <= n:

if n % divisor == 0:

return False

divisor += 1

return True

for n in [10, 41, 91, 97]:

print(n, "even:", is_even(n), " prime:", is_prime(n))

Output

10 even: True  prime: False
41 even: False  prime: True
91 even: False  prime: False
97 even: False  prime: True

is_prime can be slow for huge numbers, but it always stops with the right answer, and that is all "decidable" asks for. Speed is a separate question, covered by algorithmic efficiency.

What makes a problem undecidable?

An undecidable problem is one for which no algorithm can be built that always gives a correct yes-or-no answer. This is not about computers being too slow today. It has been shown that such an algorithm cannot exist at all.

The most famous example is the halting problem: given any program and its input, will the program eventually stop, or will it run forever? A tool that answered this correctly for every program would be extremely useful. It could warn you about every endless loop before you press Run. No such tool can exist.

Can some instances still be solved?

Yes. Undecidable means no algorithm solves all instances. Many individual instances, and even whole families of them, are easy:

A program with no loops and no function calls always stops.

while True: with no break inside never stops.

A loop that counts i up by 1 until i == 10, starting from 0, stops after 10 passes.

The program below checks one narrow family of loops, i = start then while i != stop: i += step, and always answers correctly for that family. It cannot be stretched to cover every program anyone could write.

A correct checker for one family of loops

def counting_loop_halts(start, step, stop):

"""Does i = start; while i != stop: i += step ever stop?"""

if step == 0:

return start == stop # i never changes

distance = stop - start

# It stops when it lands exactly on stop, moving the right way

return distance % step == 0 and distance / step >= 0

print(counting_loop_halts(0, 1, 10)) # True: 0, 1, ..., 10

print(counting_loop_halts(0, 2, 7)) # False: jumps over 7

print(counting_loop_halts(10, 1, 3)) # False: moves away from 3

print(counting_loop_halts(5, 0, 5)) # True: already at stop

Output

True
False
False
True

Sometimes nobody knows the answer even for a short program. Take a number: if it is even, halve it; if it is odd, triple it and add 1. Repeat until you reach 1. Every number anyone has ever tried reaches 1, but no one has proved that every number does. A program can test as many instances as you like, each with a limit on the number of steps, and still not settle the question for all of them.

Testing instances is not the same as deciding the problem

def collatz_steps(n, limit=10_000):

steps = 0

while n != 1:

n = n // 2 if n % 2 == 0 else 3 * n + 1

steps += 1

if steps > limit:

return None # gave up: no answer for this instance

return steps

for n in [6, 7, 27, 97]:

print(n, "reaches 1 after", collatz_steps(n), "steps")

Output

6 reaches 1 after 8 steps
7 reaches 1 after 16 steps
27 reaches 1 after 111 steps
97 reaches 1 after 118 steps

Practice

Does the counting loop stop?

Write Code

Write loop_stops(start, step, stop) that returns True if this loop eventually stops and False if it runs forever:

i = start
while i != stop:
    i += step

Think about three cases: step is 0, the loop moves away from stop, and the loop jumps over stop without landing on it.

def loop_stops(start, step, stop):

# Your code here

pass

Count the steps, with a limit

Write Code

Write steps_to_one(n, limit) for the halve-or-triple rule: while n is not 1, an even n becomes n // 2 and an odd n becomes 3 * n + 1.

Return the number of steps it took to reach 1. If it has not reached 1 after limit steps, return None instead: your program gives up on that instance rather than running forever.

def steps_to_one(n, limit):

# Your code here

pass

Check your understanding

Which statement describes a decidable problem?

AA problem that a computer can solve in under one secondBA yes-or-no problem for which an algorithm exists that gives a correct answer for every inputCA problem that has been solved for at least one inputDA problem whose answer is always yes

A student says: "The halting problem is undecidable, so no program can ever tell whether any particular program stops." What is wrong with this claim?

ANothing: no program can decide whether any program stopsBThe halting problem becomes decidable on faster computersCMany particular programs can be shown to stop or not; what cannot exist is one algorithm that is correct for every programDThe halting problem only applies to programs without loops

Which of these is a decidable problem?

AGiven any program and its input, will the program eventually stop?BGiven a whole number, is it divisible by 7?CGiven any program, will it ever print the word "error"?DGiven any two programs, do they always print the same output?

Which two statements about undecidable problems are true?

Select 2 answers.

ANo algorithm can always give a correct yes-or-no answer for themBThey become decidable once computers are fast enoughCSome of their instances may still be solved by an algorithmDThey are always optimization problems rather than decision problems

A company advertises a tool that "detects every infinite loop in any program before it runs, with no mistakes." Which response is best?

AThe claim is plausible if the tool runs on a fast serverBThe claim is impossible as stated, because deciding whether every program halts is undecidableCThe claim is impossible because infinite loops cannot be written in most languagesDThe claim is plausible if the tool only reads the code instead of running it

What does this program display?

n ← 6
count ← 0
REPEAT UNTIL (n = 1)
{
   IF (n MOD 2 = 0)
   {
      n ← n / 2
   }
   ELSE
   {
      n ← 3 * n + 1
   }
   count ← count + 1
}
DISPLAY (count)

A6B7C8D9

Run this pseudocode

Exam topics: 3.18 Undecidable Problems (AAP-4.B)

What is a decidable problem?

What makes a problem undecidable?

Can some instances still be solved?

Practice

Check your understanding

Related Tutorials