Au début du XXème siècle s'est produit ce qu'on appelle "la crise des fondements": une révolution mathématique au cours de laquelle les chercheurs ont voulu construire toutes les mathématiques sur des bases solides. Les mathématiciens de l'époque se demandent alors si, en utilisant des algorithmes, une théorie universelle pourrait démontrer toutes les mathématiques: c'est la naissance de la logique.
C'est ici qu'intervient un des logiciens les plus célèbres de l'histoire de l'informatique, Alan Turing. Il imagine alors une machine capable de lire les caractères imprimés sur un ruban de taille infinie, à raison d'un caractère à la fois, de remplacer ce caractère en suivant des règles définies -- qui correspondraient au programme --, et de déplacer le ruban vers la droite ou la gauche. Il avance la thèse qu'il existe un programme sur sa machine pour chaque algorithme. Dès lors, on dira que quelque chose est "calculable" si une machine de Turing est capable de la calculer. L'informatique moderne était née.
Turing se rend compte assez vite que tout ne peux pas être calculé avec une machine de Turing. L'idée étant que le ruban de la machine, bien qu'il soit infini, n'est pas assez grand pour ne serait-ce que prétendre pourvoir résoudre tous les problèmes imaginables.
Tous nos ordinateurs modernes se basent sur ces machines de Turing, leur ruban étant un disque dur. Vous aurez donc compris, lecteur attentif, que votre ordinateur n'est pas tout puissant ! Celà étant dit, la puissance des machines modernes est telle que le nombre de calculs qu'elles effectuent a considérablement élargi le champ des possibles. L'informatique ne se résume plus à de la théorie ou à du calcul mais s'étend à des applications bien concrètes et très variées dans notre vie au quotidien. La prochaine étape viendra peut être de l'ordinateur quantique qui rendrait la machine de Turing obsolète.