On Computable Numbers, with an Application to the Entscheidungsproblem

Résumé

Introduit une machine abstraite qui lit et écrit des symboles sur un ruban selon une table finie de règles, et s’en sert pour montrer qu’aucune procédure générale ne peut décider si un programme quelconque s’arrête.

Pourquoi c’est important

Il a établi ce qu’est le calcul, sous une forme assez précise pour qu’on puisse en démontrer des propriétés, et lui a simultanément fixé une limite dure. La machine universelle capable de simuler toute autre est l’ancêtre conceptuel de l’ordinateur à programme enregistré, et le résultat d’indécidabilité reste la raison pour laquelle certaines questions sur les programmes ne peuvent jamais recevoir de réponse générale.