An undecidable problem is a decision problem that asks a yes-or-no question for every input in an infinite set where no algorithm exists that always halts with the correct answer. These problems correspond to sets of natural numbers that are not recursive.
Alan Turing proved in 1936 that no general algorithm solves the halting problem using a theoretical device called a Turing machine. His proof demonstrated that any attempt to create a universal solver leads to a logical contradiction regarding whether an arbitrary program finishes running or runs forever on a given input.
Max Dehn posed the word problem for groups in 1911 asking if two words are equivalent within a finitely presented group. Mathematicians showed this was impossible to decide in 1955 establishing its status as an undecidable problem.
The concepts raised by Gödel's incompleteness theorems mirror those found in the halting problem through a weaker form of the First Incompleteness Theorem. This version asserts that no sound and complete effective axiomatization of natural numbers exists because an algorithm enumerating all true first-order logic statements would solve the halting problem which cannot exist.
Hilbert's Tenth Problem appeared in 1900 as a challenge for the next century seeking integer roots of polynomial equations with integer coefficients. Yuri Matiyasevich proved its unsolvability in 1970 showing that restricting solutions to integers makes the task impossible unlike finding them in the complex plane.