---
title: "The Halting Problem: A Task No Program Can Do"
description: "There is no program that can take any program and its input and always say correctly whether it will finish. The proof feeds the checker its own description, and the contradiction is where computabili"
canonical: https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr
source: https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# The Halting Problem: A Task No Program Can Do

There is no program that can take any program and its input and always say correctly whether it will finish. The proof feeds the checker its own description, and the contradiction is where computability stops.

Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18
Page: https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr

## Ready when they can

- State the halting problem precisely, including what the checker is given
- Follow the self-reference step and say where the contradiction appears
- Tell an undecidable problem apart from one that is merely slow

## Lesson: The question no program can answer

An algorithm is a precise recipe: finite steps, clear instructions, and a guaranteed finish for every allowed input. The halting problem asks for a checker that receives any program plus its input and answers whether that program finishes. It must be right for every possible pair, with no exceptions.

**Example.** Suppose the perfect checker existed. Build a trickster program that feeds its own description to the checker, then does the opposite of the verdict. Told it stops, the trickster loops forever. Told it loops, the trickster stops at once. The contradiction lands exactly at that self-asking step, so no verdict the checker gives can be right.

This strict standard is what lets the argument bite. A checker that works on most programs is not enough, because the proof builds its trap on the very case the checker claims to handle. One wrong answer breaks the guarantee, and the trickster finds it.

**Tip.** Keep undecidable apart from merely slow. A slow problem has a correct program that needs more time than the universe allows. An undecidable problem has no correct program at all, on any machine that will ever be built. When a task smells impossible, try the self-reference move before blaming your own skill.

**Recap.** No checker can call every halt, because the trickster always answers back wrong.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Big-O Notation and Orders of Growth](https://lightmysky.com/learn/computing/big-o-notation-and-orders-of-growth-mt_mkqgxhJ509)
- [Recursion and the Call Stack](https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e)
- [Turing Machines and the Universal Machine](https://lightmysky.com/learn/computing/turing-machines-and-the-universal-machine-mt_vS_QC1tCSM)

## Opens up

- [Reductions: Solving One Problem by Turning It into Another](https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr)
- [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB)