computability
The equation with no algorithm
It is a challenge posed in 1900 and answered only in 1970: is there a single mechanical procedure that, given any polynomial equation in several unknowns, decides whether it has whole-number solutions? Diophantine equations are as old as number theory, and the hope was that they, at least, would yield to an algorithm. Settle it — by showing that the solution sets of such equations are exactly the computably enumerable sets, so that a decision procedure for them would decide the halting problem, which cannot be. The construction bridges number theory and computability unexpectedly. Get it wrong and mathematicians hunt forever for a decision method that cannot exist, or fail to see undecidability reaching the most classical corner of their subject.
Who this problem belongs to
The two figures whose methods fit it best, out of 42 in contention.
Turing's 1936 definition of computability and his proof that the halting problem is undecidable supply the exact conceptual tool this problem's 1970 resolution depends on: showing that the set of Diophantine equations with integer solutions coincides with the computably enumerable sets, so that a decision procedure for them would decide the halting problem, which cannot exist. Every later contributor to Hilbert's tenth problem — Davis, Putnam, Robinson, and finally Matiyasevich — built directly on Turing's framework for what 'no algorithm exists' even means. Turing died in 1954, sixteen years before Matiyasevich's construction, so he did not work the number-theoretic side of the proof himself, but the entire undecidability half of the argument is his invention, applied here to a problem he did not live to see solved.
Tao is a working analytic number theorist whose own research, including his Fields Medal-winning work with Emmanuel Candes on compressed sensing, sits genuinely close to the deep number-theoretic and combinatorial machinery that Hilbert's tenth problem's resolution required, and he has written extensively and expertly on Diophantine equations, exponential sums, and related classical number theory throughout his career. His command of both rigorous formal proof and the specific mathematical objects — polynomial equations, integer solutions, exponential growth encodings — this problem centers on is unusually direct for a modern figure. He works decades after Matiyasevich's 1970 completion as an heir rather than a participant, but no contemporary mathematician on this roster combines number-theoretic depth and formal rigor as completely.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
42 figures are scored on this problem. Draw it in a battle to see where you land.