Almost every collection of numbers is beyond the reach of any computer
There are only countably many possible Turing machines, so only countably many sets of whole numbers can ever be computed. Cantor showed the sets of whole numbers themselves are uncountable. The upshot is startling: nearly all of them lie beyond any program, and computability theory exists to map that vast unreachable territory.
The field took shape in the 1930s, with Alan Turing, Alonzo Church, Kurt Gödel and Rózsa Péter among its founders alongside Stephen Kleene and Emil Post. Their work pinned down what effective calculation means, and in 1952 Kleene named the resulting claims Church's thesis and Turing's thesis, now merged as the Church–Turing thesis: whatever an algorithm can compute, a Turing machine can compute. Gödel was sceptical at first but by 1946 praised the concept for giving an absolute meaning to an idea that did not depend on which formal system you chose.
In 1936 Church and Turing independently proved that no mechanical procedure can decide the truth of arbitrary mathematical statements. More unsolvable problems followed. Andrey Markov and Post showed in 1947 that a word problem for semigroups cannot be decided; Pyotr Novikov and William Boone extended this to groups in the 1950s; and in 1970 Yuri Matiyasevich, drawing on Julia Robinson's results, showed that no method can decide whether every whole-number equation has whole-number solutions, answering Hilbert's tenth problem.
The halting problem, deciding which programs eventually stop, is the standard example of an uncomputable set, yet a machine can still list, one by one forever, every program that does halt. To grade degrees of impossibility, Turing in 1939 imagined an oracle machine that may ask a magic box whether a given number belongs to some set and always gets the right answer instantly. Sets that can answer each other's questions this way share a Turing degree.
In 1944 Post asked whether anything listable sits strictly between the computable sets and the halting problem. Kleene and Post found intermediate degrees in 1954 without settling the question, and soon afterwards Richard Friedberg and Albert Muchnik independently showed such listable sets exist, revealing a strikingly intricate structure.
Source: Computability theory
