KnowraUndecidable problemUndecidable problemA decision problem for which no algorithm always halts and answers correctly on every input.BriefConnectHalting problem: The decision problem of determining whether a program halts on a given input. Turing proved that no algorithm decides this particular problem for every program and input.Decision problem: A computational problem whose answer for each input is yes or no. Undecidability is a property of decision problems, not of arbitrary questions as phrased.Decidable problem: A decision problem for which an algorithm always halts and answers correctly on every input. It is the direct opposite: a total decision procedure exists.Post correspondence problem: The problem of deciding whether a sequence of paired strings can yield identical concatenations. This undecidable problem is a standard source for reductions in formal language theory.Entscheidungsproblem: Hilbert's challenge to find a procedure deciding the validity of every statement in first-order logic. The negative solution established a prominent form of undecidability.Many-one reduction: A computable transformation that maps instances of one decision problem to instances of another while preserving yes-or-no answers. A reduction transfers undecidability from a known problem to a new one.Algorithm: A finite, specified procedure for producing an output from an input. A problem is decidable only if an algorithm returns its correct answer on every input.Undecidability: The property of a problem having no algorithm that decides it on every input. The term names the property that an undecidable problem has.Hilbert's tenth problem: The problem of deciding whether a polynomial equation with integer coefficients has an integer solution. Its undecidability shows that a natural arithmetic question has no universal algorithm.Alonzo Church: An American mathematician and logician who developed lambda calculus and proved the Entscheidungsproblem unsolvable. Church gave one of the first proofs that no general decision procedure exists.Show all 26Linked from 10 pagesFormal proofRelated: Some questions about formal derivability cannot be settled by a universal algorithm.Julia RobinsonNarrower topic: Hilbert’s tenth problem became a prominent example of a mathematically natural undecidable question.DecidabilityCompared with: It is the direct opposite of decidability.Turing's proofNarrower topic: Turing’s proof establishes the halting problem as a canonical undecidable problem.Independence (mathematical logic)Compared with: Algorithmic undecidability concerns a whole problem, not a single sentence’s provability from axioms.Mathematical problemCompared with: Undecidability means no general procedure exists, not merely that a solution is difficult to find.Theory of computationCompared with: It marks the boundary between computational difficulty and impossibility.Show all 10