Dans la préface du Philosophiae naturalis principia mathematica de Newton, Voltaire écrivait "[qu']il a fallut que les modernes créassent de nouveaux mots pour rendre ces nouvelles idées." Aussi, sait-on depuis longtemps que le langage, quel qu’en soit la forme, influence la pensée et réciproquement. L'informatique n'est pas pour rien dans la compréhension que nous avons aujourd'hui des langues, et c'est une de ses résultats majeurs que nous nous proposons d'explorer ici.
Le modèle de calcul à la base de l'informatique est la machine de Turing, imaginée par le mathématicien éponyme dans la première moitié du vingtième siècle. Dans sa version la plus simple, elle se modélise comme une tête de lecture pouvant écrire des uns ou des zéros dans les cases d'un long ruban -- infini des deux côtés -- en suivant un ensemble de règles ; on peut assimiler ces dernières à ce que nous appellerions aujourd'hui le programme. Sans rentrer dans les détails du fonctionnement de cette machine, nous nous contenterons des remarques suivantes : une machine de Turing s'arrête quand un règle le lui dit ou lorsque plus aucune règle ne s'applique. Ainsi, une telle machine ne s'arrête pas forcément. On peut imagine par exemple une machine qui avance toujours vers la droite sans condition d'arrêt. Si cependant elle s'arrête, elle s'arrête sur un 0 ou un 1 ce qui nous donne l'intuition qu'elle permet de modéliser efficacement les problèmes de décision, 1 représentant "oui" et 0 "non".
C'est sur cette catégorie de problèmes que nous allons nous pencher maintenant. Un problème de décision est une question dont la réponse est soit "oui" soit "non", par exemple "cette formule arithmétique est-elle correcte ?". Au début du vingtième siècle le mathématicien allemand David Hilbert se demandait s'il existait des procédés systématiques, des algorithmes, pour résoudre des problèmes mathématiques. La réponse vint d'un autre mathématicien allemand, quelques années plus tard, qui montra que quel que soit le langage dans lequel on s'exprime, on peut toujours trouver un problème indécidable.
Une manière de voir les problèmes de décisions qui nous sera plus commode est de nous demander si un mot fait partie d'un langage -- et on remarquera que cette question est elle-même un problème de décision. Un langage en informatique est un ensemble de mots sur un alphabet, c'est-à-dire un ensemble de séquences de caractères parmi ceux que nous avons défini, ici 0 et 1. Il est important de comprendre qu'un problème de décision peut toujours être réduit à l'ensemble de mots -- un sous-langage -- pour lesquels la décision est "oui" ; un mot est accepté s'il appartient à cet ensemble -- à ce sous-langage.
On qualifiera alors un problème de décidable s'il existe une machine qui accepte tous les mots du langage défini par le problème et refuse tous les autres. Un langage décidable est tel qu'il existe une machine de Turing qui répondra toujours "oui" ou "non". C'est là que les ennuis commencent, tous les langages ne sont pas décidables : dès lors que toute machine qui implémente le langage n'est plus absolument sûre de terminer, on dit alors, en toute sobriété, qu'il est indécidable. Une manière intuitive d'exprimer ce que serait un problème indécidable, serait de se dire que dans certains cas il faudrait un temps infini pour le résoudre.
La suite et l'achèvement de notre périple a lieux en 1931 lorsque Kurt Godël publie un article intitulé Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme qui reste encore aujourd'hui un article de référence. Dans cet article il énonce puis démontre le théorème suivant "Dans n'importe qu'elle théorie [...] cohérente et capable de formaliser l'arithmétique, on peut construire un énoncé arithmétique qui ne peut être ni démontré, ni réfuté dans cette théorie." Ce, qui en subtance, signifie que le problème de décision pris en exemple plus haut "cette formule arithmétique est-elle correcte ?" est indécidable quelle que soit la manière qu'on aurait de l'exprimer. Néanmoins si un problème est indécidable dans les limites d'un langage, il n'est pas nécessairement indécidable dans un autre langage.
Ce théorème mis d'une part fin au rêve de Hilbert et d'autre part nous montra les limites de nos langages, les langages mathématiques ne sont qu'une version extrêmement minimaliste des langages naturels que nous utilisons tous les jours. Aussi intelligent pourrions-nous être, il existera toujours des problèmes que nous ne pourrons pas résoudre si nous ne changeons pas de manière de les exprimer. Peut-être qu'au-delà de ce que disait Voltaire, il aurait fallu que nous créassions de nouvelles langues pour rendre des nouvelles idées.