Halting Problem

← Encyclopedia

External reading guide · Undergraduate

There is no algorithm deciding whether every encoded machine halts on its supplied input. Follow the diagonal construction carefully: a machine's own description becomes the input that defeats the proposed decision procedure.

Before opening the references

function between sets · Countable Set · Proof by Contradiction

Where to read

  1. Start here: Sets, Logic, Computation: An Open Introduction to Metalogic

    Richard Zach; based on the Open Logic Text by the Open Logic Project · Open textbook · English · Free full text

    §15.3 The Halting Problem, Definition 15.5 and Theorem 15.8 (Unsolvability of the Halting Problem)

    Source page · Checked 2026-10-16

Continue from here

Mathematical Logic & Computability in the library · Preparation and skip guidance

Suggest an edit · Report a correction

Original orientation: CC BY-SA 4.0. Linked texts retain their own licences.