Decision Problems: Yes-or-No Questions

A decision problem is any problem that can be phrased as a yes-or-no question about its input. "Is n even?" is a decision problem. "Does the value x appear in this list?" is a decision problem. "Is this number prime?" is a decision problem. The answer is always exactly one of two things: yes or no, which in code is True or False. A program that answers a decision problem is often called a decider.

def is_even(n):
    if n % 2 == 0:
        return True
    else:
        return False

print(is_even(6))

PROCEDURE isEven(n)
{
    IF (n MOD 2 = 0)
    {
        RETURN (true)
    }
    ELSE
    {
        RETURN (false)
    }
}
DISPLAY(isEven(6))

The decider above answers "is n even?" for any integer you hand it. Run it in your head with 6: 6 % 2 is 0, so it returns True. Hand it 7 and it returns False. The important thing is that it always finishes and it is always correct, no matter which integer you choose. That property has a name.

Decidable Problems

A decision problem is decidable if an algorithm can be written that produces a correct yes-or-no answer for every possible input, and always finishes running. The words "every" and "always" carry the whole definition. It is not enough for the algorithm to work on the inputs you tried; it must be guaranteed correct on all of them, including inputs no one has tested yet.

def contains(t, x):
    for v in t:
        if v == x:
            return True
    return False

print(contains([3, 8, 5], 8))

PROCEDURE contains(t, x)
{
    FOR EACH v IN t
    {
        IF (v = x)
        {
            RETURN (true)
        }
    }
    RETURN (false)
}
DISPLAY(contains([3, 8, 5], 8))

"Does x appear in list t?" is decidable. The decider walks the list, and because the list is finite it must reach the end, so the loop always stops and the answer is always right. "Is n prime?" is decidable too: test every candidate divisor up to n; there are finitely many, so the check always terminates with a correct verdict. Almost every algorithm you have written this year solves a decidable problem.

Undecidable Problems and the Halting Problem

A decision problem is undecidable if no algorithm can be built that always gives a correct yes-or-no answer for every possible input. This is not a statement about today's computers or about clever people who have not tried hard enough. It is a proven mathematical fact: for an undecidable problem, a correct general algorithm cannot exist, ever, on any computer.

The classic example is the halting problem: given an arbitrary program and an input to it, decide whether that program will eventually stop or will run forever. It sounds answerable, and for many specific programs you can tell at a glance. But there is no single algorithm that answers it correctly for every program and input. Alan Turing proved this in 1936.

# IMAGINED function that CANNOT exist
def halts(program, data):
    # would return True if program stops on data,
    # False if program runs forever
    ...

# The proof of impossibility feeds this idea a copy
# of itself, forcing a contradiction either way.

The proof imagines a perfect halting-checker and then builds a program that asks the checker about itself and does the opposite of whatever the checker predicts. If the checker says "halts," the program loops forever; if it says "runs forever," the program stops. Either answer is wrong, so the perfect checker cannot exist. You are not expected to reproduce the proof, only to know that the halting problem is undecidable and is the standard example.

def is_even(n):
    return n % 2 == 0
print(is_even(7))

Undecidable Is NOT the Same as Slow

This is the single most tested trap in the topic, so read it twice. A problem being slow, even absurdly slow, is completely different from a problem being undecidable.

• Slow / unreasonable time: a correct algorithm exists, but it may take an impractical amount of time (for example, checking every possible password, which grows exponentially). The answer is reachable in principle; you just might wait longer than a lifetime.
• Undecidable: a correct general algorithm does not exist at all. No amount of waiting, faster hardware, or cleverness produces one, because it is impossible.

An exponential-time problem is still decidable. Given unlimited time, its algorithm always finishes with the right answer. The halting problem is in a different league: there is nothing to run to completion because the deciding algorithm cannot be written in the first place.

Writing Deciders You Can Actually Run

You cannot write a program that solves an undecidable problem, but you can and should master the deciders for decidable problems, because those are exactly what the code section drills. A good decider returns or prints True or False, is correct for every input in its domain, and always terminates. Watch out for the most common decider bug: returning an answer too early inside a loop before all the data has been examined.

t = [2, 4, 6]
x = 5
print(x in t)

Key Vocabulary