Course contentsShow
← Computer Science
Lesson 1878 of 2,87242. Turing Machines and ComputabilityFree lesson

What is the Halting Problem?

Define the halting problem: determining if an arbitrary program halts on a given input.

What is the Halting Problem?

You'll learn: What the halting problem is and why determining whether a program stops running is a fundamental question in computer science.

The Core Question

The halting problem asks: Given an arbitrary program and some input, can we write another program that always correctly determines whether the first program will eventually halt (stop) or run forever?

This might seem like a straightforward question, but it turns out to be one of the most profound discoveries in computer science.

Understanding the Problem

Think of it this way: Imagine you're a teacher grading student programs. Some programs finish quickly and print an answer. Others get stuck in infinite loops. You want to build an automated checker that looks at any submitted program and its input, then tells you "HALTS" or "RUNS FOREVER" before actually running it.

The halting problem asks: Is such a universal checker even possible?

Why Does This Matter?

  • Practical concern: We've all encountered frozen programs. Wouldn't it be useful to know ahead of time if a program will finish?
  • Theoretical significance: This problem defines a fundamental boundary of computation—something even Turing machines (and by the Church-Turing Thesis, all computers) cannot solve in general.

The Setup

  • Input: A description of program P and input data I
  • Question: Does P halt when run on I?
  • Goal: Create a decider that always answers correctly

As you've learned, a decidable problem is one where a Turing machine can always halt with a correct yes/no answer. The halting problem challenges whether this particular question is decidable.

Key Takeaway: The halting problem asks whether we can build a universal program-analyzer that always correctly determines if any given program halts on any given input—a deceptively simple question with profound implications.