blanketglossary

Halting problem

Definition

In computability theory, the halting problem is the decision problem of determining, from a description of an arbitrary computer program and an input, whether the program will eventually halt or continue to run forever. Alan Turing proved in 1936 that the halting problem is undecidable, meaning that no general algorithm exists that can correctly solve the problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.

Related concepts

"Hello, World!" program Abstract logic Ackermann set theory Alan Turing Aleph number Alfred North Whitehead Algebraic logic Algorithm Alonzo Church Alphabet Alphabet (formal languages)Andrew Hodges Argument Arithmetical hierarchy Arity Atomic formula Atomic model (mathematical logic)Atomic sentence Automata theory Automated theorem proving Axiom Axiom of choice Axiom schema Axiomatic system Axiomatization Axiomatization of Boolean algebras Banach–Tarski paradox Bertrand Russell Beta normal form Bijection Binary operation Boolean algebra Boolean algebras canonically defined Boolean function Brainfuck Brouwer–Hilbert controversy Busy Beaver Busy beaver Cantor's diagonal argument Cantor's paradox Cantor's theorem Cardinality Cartesian product Categorical theory Category (mathematics)Category of sets Category theory Chaitin Chaitin's constant Character (computing)Christopher Strachey Church encoding Church–Turing thesis Class (set theory)Classical logic Codomain Compactness theorem Complement (set theory)Complete theory Computability Computability theory Computability theory (computer science)Computable function Computable number Computable set Computably enumerable set Computation Computer program Computer scientist Concrete category Conservative extension Consistency Consistency proof Constance Reid Constructible universe Construction of the real numbers Constructive set theory Continuum hypothesis Corollary Correctness (computer science)Countable set Cristian Calude Cristopher Moore Data type David Bolter David Hilbert Decidability (logic)Decision problem Deductive system Definable number Definable set Degree of unsolvability Diagram (mathematical logic)Domain of a function Edward Beltrami Effective method Element (mathematics)Elementary diagram Elementary equivalence Elementary function arithmetic Emil Post Empty set Entscheidungsproblem Enumeration Equiconsistency Equivalence relation Ernest Nagel Euclid's Elements Euclidean geometry Event loop Existential quantification Expression (mathematics)Extension by definitions Extension by new constant and function names Extensionality Finitary relation Finite-valued logic Finite model theory Finite set First-order logic Fixed-point logic Forcing (mathematics)Formal grammar Formal language Formal proof Formal semantics (logic)Formal system Formalism (mathematics)Formation rule Foundations of geometry Foundations of mathematics Free logic Free variables and bound variables Function (mathematics)Functional predicate Fuzzy set General recursive function General set theory Gentzen Gregory Chaitin Grothendieck universe Ground expression Ground formula Gödel's completeness theorem Gödel's incompleteness theorem Gödel's incompleteness theorems Gödel numbering Halting probability Hereditary set Heuristic (computer science)Higher-order logic Hilbert's axioms Hilbert's problems Hilbert system History of logic History of mathematical logic Human brain Hypercomputer Image (mathematics)Inaccessible cardinal Independence (mathematical logic)Inference Infinite-valued logic Infinite loop Infinite set Information theory Inhabited set Injective function International Congress of Mathematicians Interpretation (logic)Interpretation (model theory)Interpretation function Interpreter (computing)Intersection (set theory)Isomorphism Iterate J. Barkley Rosser James R. Newman Jeffrey Ullman John Hopcroft Julia Robinson Kolmogorov complexity Kripke's theory of truth Kripke–Platek set theory Kurt Gödel Lambda calculus Large cardinal Lemma (mathematics)Lindström's theorem Linear bounded automaton List of Hilbert systems List of axioms List of first-order theories List of formal systems List of mathematical theories List of set identities and relations List of statements independent of ZFC Logic Logical biconditional Logical conjunction Logical connective Logical consequence Logical constant Logical disjunction Logical equality Logical equivalence Logical truth Logicism Löwenheim–Skolem theorem MISRA C Machine that always halts Many-valued logic Map (mathematics)Markov algorithm Martin Davis (mathematician)Marvin Minsky Material conditional Mathematical logic Mathematical object Mathematical proof Metalanguage Michael Sipser Minimal axioms for Boolean algebra Model complete theory Model of computation Model theory Monadic predicate calculus Monadic second-order logic Morse–Kelley set theory NP (complexity)Naive set theory Natural deduction Natural density Natural number Negation New Foundations Non-Euclidean geometry Non-logical symbol Non-standard model Non-standard model of arithmetic Normal number Numeral system Open formula Operation (mathematics)Oracle machine Ordinal analysis Ordinal number P (complexity)P versus NP problem Paradoxes of set theory Partial function Partition of a set Peano Axioms Peano axioms Philosophy of mathematics Physical process Post system Power set Predicate (mathematical logic)Predicate logic Predicate variable Prime model Primitive recursive Primitive recursive arithmetic Primitive recursive function Principia Mathematica Probability Programming language Programming system Proof by contradiction Proof of impossibility Proof theory Proposition Propositional calculus Propositional formula Propositional variable Pseudocode Quantifier (logic)Quantifier rank RE-complete Real-time computing Recursion Recursion theory Recursive set Recursively enumerable Reduction (complexity)Reduction (recursion theory)Register machine Relation (mathematics)Reverse mathematics Rice's theorem Robinson arithmetic Rocq Roger Penrose Rule of inference Rule of least power Russell's paradox SPARK (programming language)Satisfiability Saturated model Schröder–Bernstein theorem Second-order arithmetic Second-order logic Self-referential Self-verifying theories Semantic theory of truth Semantics of logic Sentence (mathematical logic)Sequent calculus Set (mathematics)Set theory Signature (logic)Singleton (mathematics)Skolem arithmetic Soundness Spectrum of a sentence Spectrum of a theory Springer Nature Square of opposition Stephen Kleene Strength (mathematical logic)String (formal languages)Structure (mathematical logic)Studia Logica Substitution (logic)Substructure (mathematics)Supertask Surjective function Syllogism Symbol (formal)Syntax (logic)T-schema Tag system Tarski's axiomatization of the reals Tarski's axioms Tarski's theory of truth Tarski's undefinability theorem Tarski–Grothendieck set theory Tautology (logic)Taylor Booth (mathematician)Term (logic)Term logic Termination analysis Themistocles M. Rassias Theorem Theories of truth Theory (mathematical logic)Three-valued logic Timeline of mathematical logic Total function Transcendental number Transfer principle Transitive set True arithmetic Truth predicate Truth table Truth value Turing's proof Turing-complete Turing Machine Turing degree Turing jump Turing machine Turing reduction Type (model theory)Type theory Ultrafilter (set theory)Ultraproduct Uncountable set Undecidable problem Uninterpreted function Union (set theory)Uniqueness quantification Universal Turing machine Universal quantification Universal set Universe (mathematics)Urelement Validity (logic)Variable (mathematics)Venn diagram Von Neumann universe Von Neumann–Bernays–Gödel set theory Well-formed formula Worst-case execution time Zermelo–Fraenkel set theory

143 concepts already in your glossary