MENTAL MODEL · M2588

Halting Problem

BusinessHigh supportManagement

Included

Version 1.0.0 · Updated 2026-07-30

CORE DEFINITION

Is there a program that can determine whether any given program (and input) will eventually halt or loop indefinitely? Turing proved that no such program exists. This is the logical boundary of computational capability. -

SCAFFOLDING EFFECT

psychology

Reduce cognitive load

A mathematical proof of unknowability. - It tells us that even the most logically rigorous computer has problems that cannot be predicted. In management and planning, acknowledge that 'some bugs cannot be discovered through pre-checking' and must be exposed through running. A perfect prediction system is logically impossible.

anchor

Anchor fast decisions

Turing proved that there is no general algorithm that can determine whether an arbitrary program halts on a given input. The proof uses contradiction: assume a decider H exists, construct a program that calls H itself, such that it loops on inputs that 'halt' and halts on inputs that 'loop', leading to a contradiction.

MINIMUM ACTION

In progress 0/4

Practice this model in one real situation:

Recognize that there is no general decision procedure for 'whether a program halts'
For specific programs, use termination analysis, static checking, or restricted languages (e.g., loops with guaranteed decreasing) to approximate the judgment
In system design, use timeouts or watchdog timers as a fallback
Accept 'partial undecidability' and rely on running to expose issues rather than prediction.

Check to track your progress (stored locally)

Learning progress0%

account_treeGenealogyexpand_more

menu_bookReferencesexpand_more

Source support: Explicit

link
en.wikipedia.orghttps://en.wikipedia.org/wiki/Halting_problemZH · Explicit
verified

RELATED MODELS