blanketglossary

Undecidable problem

Definition

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

Related concepts

Abstract logic Abstract machine Ackermann set theory Alan Turing Aleph number Algebraic logic Algorithm Algorithmic information theory Alphabet (formal languages)Argument 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 Berry's paradox Bijection Binary operation Boolean algebra Boolean algebras canonically defined Boolean function Cantor's diagonal argument Cantor's paradox Cantor's theorem Cardinality Cartesian product Categorical theory Category (mathematics)Category of sets Category theory Church encoding Church–Turing thesis Class (set theory)Classical logic Codomain Collatz problem Compactness theorem Complement (set theory)Complete theory Complex plane Computability theory Computable function Computable set Computably enumerable set Computational complexity theory Computer program Concrete category Conservative extension Consistency Consistency proof Constructible universe Construction of the real numbers Constructive set theory Continuum hypothesis Corollary Countable set Countably infinite Decidability (logic)Decision problem Deductive system Diagram (mathematical logic)Diophantine equation Doklady Akademii Nauk SSSR Domain of a function Element (mathematics)Elementary diagram Elementary equivalence Elementary function arithmetic Empty set Entscheidungsproblem Enumeration Equiconsistency Equivalence relation Euclid's Elements Euclidean geometry Existential quantification Expression (mathematics)Extension by definitions Extension by new constant and function names Extensionality Fermat's Last Theorem 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 Formation rule Foundations of geometry Foundations of mathematics Free logic Free variables and bound variables Function (mathematics)Functional predicate Fuzzy set General set theory Goodstein's theorem Gregory Chaitin Grothendieck universe Ground expression Ground formula Group (mathematics)Group theory Gödel's completeness theorem Gödel's incompleteness theorem Gödel's incompleteness theorems Gödel numbering Halting problem Hereditary set Higher-order logic Hilbert's axioms Hilbert's tenth problem Hilbert system History of logic History of mathematical logic Image (mathematics)Inaccessible cardinal Independence (mathematical logic)Inference Infinite-valued logic Infinite set Information theory Inhabited set Injective function Integer number Interpretation (logic)Interpretation (model theory)Interpretation function Intersection (set theory)Isomorphism Israel Journal of Mathematics Iterate John Horton Conway Kolmogorov complexity Kripke's theory of truth Kripke–Platek set theory Kruskal's tree theorem Lambda calculus Large cardinal Lemma (mathematics)Liar paradox Lindström's theorem 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 List of undecidable problems Logic Logical biconditional Logical conjunction Logical connective Logical consequence Logical constant Logical disjunction Logical equality Logical equivalence Logical truth Logicism Löwenheim–Skolem theorem Many-valued logic Map (mathematics)Material conditional Mathematical logic Mathematical object Mathematical proof Max Dehn Metalanguage Minimal axioms for Boolean algebra Model complete theory Model theory Monadic predicate calculus Monadic second-order logic Morse–Kelley set theory NP (complexity)Naive set theory Natural deduction Natural number Natural numbers Negation New Foundations Non-Euclidean geometry Non-logical symbol Non-standard model Non-standard model of arithmetic Open formula Operation (mathematics)Ordinal analysis Ordinal number P (complexity)P versus NP problem Paradoxes of set theory Paris-Harrington theorem Partition of a set Paul Cohen (mathematician)Peano axioms Philosophy of mathematics Polynomial Power set Predicate (mathematical logic)Predicate logic Predicate variable Prime model Prime number Primitive recursive arithmetic Primitive recursive function Principia Mathematica Proceedings of the Steklov Institute of Mathematics Proof of impossibility Proof theory Proposition Propositional calculus Propositional formula Propositional variable Pyotr Novikov Quantifier (logic)Quantifier rank Ramsey theorem Ramsey theory Recursion Recursive set Recursively enumerable set Relation (mathematics)Reverse mathematics Rice's theorem Robinson arithmetic Rule of inference Russell's paradox Saharon Shelah Satisfiability Saturated model Schröder–Bernstein theorem Second-order arithmetic Second-order logic 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 Square of opposition Strength (mathematical logic)String (computer science)String (formal languages)Structure (mathematical logic)Substitution (logic)Substructure (mathematics)Supertask Surjective function Syllogism Symbol (formal)Syntax (logic)T-schema Tarski's axiomatization of the reals Tarski's axioms Tarski's theory of truth Tarski's undefinability theorem Tarski–Grothendieck set theory Tautology (logic)Term (logic)Term logic Theorem Theories of truth Theory (mathematical logic)Three-valued logic Timeline of mathematical logic Topology Transfer principle Transitive set True arithmetic Truth predicate Truth table Truth value Turing machine Type (model theory)Type theory Ultrafilter (set theory)Ultraproduct Uncountable set Uninterpreted function Union (set theory)Uniqueness quantification Universal quantification Universal set Universe (mathematics)Unknowability Urelement Validity (logic)Variable (mathematics)Venn diagram Von Neumann universe Von Neumann–Bernays–Gödel set theory Well-formed formula Whitehead problem Wicked problem Word problem for groups Yuri Matiyasevich ZFC Zermelo–Fraenkel set theory

142 concepts already in your glossary