Les notions de calculabilité et de décidabilité sont liées. En 1900, David Hilbert adresse au congrès international de mathématiques à Paris une liste de 23 problèmes irrésolus qui, espérait-il, devaient marquer le XXe siècle.

Lors du congrès, il commence son discours par :

Qui parmi nous ne serait pas heureux de soulever le voile qui masque le futur, d'observer les futurs développements de notre science ainsi que ses secrets pendant les siècles à venir ? Quels seront les fins vers lesquelles tenderont l'esprit des futures générations de mathématiciens ? Quelles méthodes, quels faits nouveaux, le siècle nouveau révèlera dans le riche et vaste champ de la pensée mathématique ?

Le dixième problème de Hilbert demande s'il est possible de trouver un algorithme permettant de décider si une équation diophantienne possède des solutions. Ce problème sera résolu bien plus tard par une réponse négative. 

Pour y répondre, il est essentiel de définir clairement la notion de calculabilité. Afin de montrer qu'il n'y a pas de méthode de calcul pour résoudre les  équations diophantiennes, il est nécessaire d'avoir une caractérisation de ce qu'est une procédure de calcul. Montrer que quelque chose est calculable est plus facile : une fonction calculable sera une fonction qui peut-être définie par un algorithme, c'est-à-dire par un ensemble fini d'instructions qui décrivent explicitement le déroulement de toutes les opérations. Ces opérations doivent de plus se terminer en temps fini. Le premier chapitre du premier tome de The Art of Computer Programming de Donald Knuth décrit la notion d'algorithme. Il suffit alors de décrire un algorithme, et supposer qu'il sera bien reconnu comme tel. Cependant montrer que quelque chose n'est pas calculable demande beaucoup plus de concepts. 

Si la notion de calculs apparaît tôt pour les mathématiques, sa formalisation n'a commencé qu'à partir de 1930. Alan Turing a fourni une première notion de la calculabilité, Kurt Gödel et Jacques Herbrand ont caractérisé la calculabilité en termes de fonctions récursives, Alonzo Church a introduit la notion de lambda-calcul, puis Emil Post a donné une autre notion de la calculabilité. La "thèse de Church" énonce que la définition intuitive d'un calcul et sa définition mathématique rigoureuse coïncident. Par conséquent, toutes les définitions mathématiques (fonctions récursives, machine de Turing, lambda-calcul,...) sont équivalentes.

La théorie de calcul est ainsi antérieure d'environ une décennie à l'invention de l'informatique moderne. En 1879, dans Begriffsschrift (traduit en français par idéographie, c'est-à-dire l'écriture ou la notation des concepts), Gottlob Frege a présenté un système formel de la logique qui serait une langue de la pensée pure calquée sur celle de l'arithmétique, . Il y définit les quantificateurs et les relations d'une manière assez proche de leur définition actuelle. L'objectif de Frege était de réduire les mathématiques à la logique, ce qu'on appelle le logicisme. Sa motivation pour développer son approche formelle de la logique ressemblait à la tentative de Leibniz avec ce que celui-ci appelait calculus ratiocinator correspondant à un calcul logique universel. Selon Leibniz, en 1684, dans son article fondateur du nouveau calcul différentiel Nova methodus pro maximis et minimis, itemque tangentibus (Nouvelle méthode pour chercher les maxima et les minima, ainsi que les tangentes) publié dans le périodique Les Acta Eruditorum de Leipzig :

Alors, il ne sera plus besoin entre deux philosophes de discussions plus longues qu'entre deux mathématiciens, puisqu'il suffira qu'ils saisissent leur plume, qu'ils s'asseyent à leur table de calcul (en faisant appel, s'ils le souhaitent, à un ami) et qu'ils se disent l'un à l'autre : "Calculons !" .

Dans la recherche de la langue parfaite, Umberto Eco retrace l'histoire de cette utopie. Après le Déluge, selon la Bible, toute la terre avait une seule langue et des mots identiques, mais l'orgueil conduisit les hommes à vouloir construire une Tour qui montât jusqu'au Ciel. Pour les punir et de sorte qu'ils ne se comprennent plus, Dieu introduisit la diversité des langues et dispersa les hommes sur toute la surface de la terre. Avec la recherche de la langue unique pour Dalgarno, Wilkins ou Leibniz, il ne s'agit nullement de retrouver une langue perdue mais d'inventer une nouvelle langue universelle, facile à apprendre et à utiliser. Calculer et raisonner devenant une seule et même chose, les ambiguïtés et les obscurités des langues naturelles se trouveraient du même coup éliminées et la voie serait ainsi ouverte tant au progrès des sciences qu'à la concorde entre les hommes.

Vers la fin du XIXe siècle, des mathématiciens comme Georg Cantor et Richard Dedekind utilisèrent de nouvelles méthodes abstraites pour raisonner sur les objets mathématiques qui furent à l'époque très controversées. Ils ont conduit à une multiplication des travaux sur les fondations, visant à trouver à la fois des descriptions précises, des nouvelles méthodes et des justifications rigoureuses. En 1902, Bertrand Russell a montré que le système formel de Frege était incohérent, c'est à dire qu'il conduit à des contradictions. Ces problèmes ont abouti à ce qu'on appelle aujourd'hui la «crise des fondements».

Hilbert, tout en étant un défenseur des méthodes de Dedekind et de Cantor, était aussi sensible aux préoccupations plus fondamentales. Au début des années 1920, il a développé un programme détaillé pour résoudre la crise :

Si l’on ne veut plus souffrir des ravages de la crise économique actuelle, nous devrons changer les règles du capitalisme mondial. Si nous voulons écarter la menace du réchauffement climatique qui pèse sur notre avenir et celui de nos enfants, nous devrons changer radicalement nos habitudes. Si nous voulons que les exploités d’aujourd’hui se libèrent demain de leurs chaînes, nous devrons construire un monde juste.

Pardon, il y a erreur sur la personne. Hibert déclare en 1930 : Wir müssen wissen. Wir werden wissen (Nous devons savoir. Nous saurons). L'idée était de représenter le raisonnement mathématique abstrait en utilisant des systèmes formels de déduction, et ensuite de prouver que ces systèmes formels sont cohérents.

La cohérence n'est cependant pas le seul point important pour Hilbert. Ses écrits datant du début du siècle, donnent à penser qu'un système d'axiomes, comme par exemple celui des nombres naturels, est inadéquate tant qu'il ne permet pas de déduire tout un ensemble de déclarations vraies. Combinée avec l'intérêt pour les systèmes formels de déduction, cette suggestion voulait tenter de garantir que le système formel des nombres naturels est non seulement cohérent, mais aussi complet, c'est à dire tout énoncé est soit démontrable ou réfutable.

C'est exactement ces deux objectifs que Gödel a détruit en 1931. Il a prouvé d'abord en 1930 la complétude de la logique classique du premier ordre, c'est-à-dire que toute formule valide exprimée dans cette logique est démontrable. En 1931 avec le théorème d'incomplétude, il montre qu'il n'y a pas de système formel axiomatisé qui soit à la fois complet et cohérent. Puis, il montre qu'il n'existe aucun système formel qui soit capable de prouver sa propre cohérence. Par conséquent, la cohérence des «mathématiques abstraites» ne peut même pas être prouvée en utilisant toutes les mathématiques abstraites.