Xè problème de Hilbert
Le 10ème des 23 célèbres problèmes de Hilbert est le suivant : existe-t-il un algorithme général qui, étant donnée une équation diophantienne (équation polynômiale dont les coefficients sont des nombres entiers) sache répondre si cette équation a, ou n'a pas, de solutions parmi les nombres entiers. Yuri Matiasevivh a répondu par la négative à ce problème en 1970, alors qu'il avait à peine 22 ans!
La démarche de Matiasevich est en fait assez générale. En utilisant un argument très astucieux basé sur les nombres de Fibonacci, Matiasevich a prouvé que tout ensemble récursivement énumérable est l'ensemble des solutions d'une équation diophantienne. Et on savait depuis 1930 qu'il existe des ensembles récursivement énumérables pour lesquels trouver un tel algorithme est impossible!