« L'incomplétude mathématique/Le théorème fondamental de l’indécidabilité et le problème de Turing » : différence entre les versions

|titre=Le théorème fondamental de l’indécidabilité et le problème de TüringTuring

La présente section expose la preuve de TüringTuring du théorème fondamental de l’indécidabilité. Cette preuve sera informelle. Pour une preuve complète, il faudrait préciser la notion de machine idéale de TüringTuring, et prouver l’existence d’une machine de TüringTuring universelle, ou ordinateur. Cette partie de la preuve n’est pas exposée ici parce que l’existence des ordinateurs est désormais couramment acceptée.

Il est possible de définir un ensemble énumérable Enum, et même décidable, de tous les noms des ensembles énumérables. On veut dire par là que l’on peut définir un formalisme dont le domaine d’objets est un ensemble EF d’expressions formelles, que Enum est une partie de EF, que toutes les parties énumérables de EF sont nommées par un élément de Enum, et que EF est suffisamment riche pour que tout ensemble énumérable concevable puisse être identifié à une partie énumérable de EF, par un processus simple de traduction. Il y a plusieurs façons de définir Enum. Nous présenterons celle de TüringTuring.

Nous montrerons plus loin que ce théorème est équivalent à celui de l’existence d’une machine de TüringTuring universelle. Dans le chapitre suivant, nous donnerons une preuve de ce théorème à partir d’une autre définition de l’énumérabilité, équivalente à celle de TüringTuring.

Nous allons d’abord présenter la méthode de TüringTuring pour définir Enum. De cette méthode il résulte immédiatement que la vérité du théorème fondamental est équivalente à l’indécidabilité du problème de l’arrêt, ou problème de TüringTuring. Il s’agit du problème de savoir par avance si oui ou non un ordinateur va s’arrêter et fournir un résultat. TüringTuring a prouvé qu’on ne peut pas programmer un ordinateur pour savoir dans tous les cas si oui ou non un ordinateur va s’arrêter.

La méthode de TüringTuring est facile à comprendre pour tous ceux qui savent programmer un ordinateur. Si on ignore les différences de capacité de mémoire et de temps de calcul, tous les ordinateurs sont équivalents, au sens où tout ce qui peut être fait par l’un peut aussi être fait par n’importe quel autre. En ce sens, les ordinateurs sont des calculateurs universels. On peut ignorer les différences de mémoire parce que celle-ci peut toujours être rallongée en connectant la machine à une banque de données. On peut ignorer les différences de temps de calcul dans la mesure où on s’intéresse seulement aux limites théoriques de la puissance des ordinateurs, comme si le fait d’attendre un résultat pendant des milliards d’années n’était pas un problème. Les ordinateurs sont équivalents parce qu’ils peuvent se représenter les uns les autres. On dit qu’une machine émule ou simule une autre machine. TüringTuring a inventé la première technique de simulation d’une machine par une autre, avant même que les ordinateurs existent réellement.

Pour représenter une machine de TüringTuring, il suffit de représenter son programme, c’est-à-dire la liste finie de toutes les règles qu’elle exécutera mécaniquement dès qu’elle aura été lancée.

Une machine de TüringTuring peut être considéré comme une fonction qui à chaque état initial de la mémoire associe son état final, après que la machine se soit arrêtée. Le domaine de définition de cette fonction est l’ensemble de tous les états initiaux pour lesquels la machine s’arrête. Nous dirons que c’est aussi le domaine de définition de la machine. Un ensemble énumérable peut être représenté par une machine de TüringTuring dont il est le domaine de définition. L’ensemble Enum est alors identifié à l’ensemble de tous les programmes, c’est-à-dire l’ensemble infini des listes finies d’instructions. Comme par définition de l’énumérabilité, un ensemble énumérable peut toujours être représenté par une machine de TüringTuring, Enum ainsi défini est bien un ensemble de noms de tous les ensembles énumérables.

Dans une machine de TüringTuring universelle U, la mémoire peut être divisée en deux parties, P et I . P sert à représenter le programme de la machine que l’on simule. Comme c’est une liste finie, P n’occupe qu’une partie finie de la mémoire totale. Le reste I sert à représenter l’état initial de la machine simulée. Après que U soit lancée, U s’arrête si et seulement si la machine représentée dans P s’arrête lorsque son état initial est celui représenté dans I. (Si U s’arrête le résultat que U fournit dans la partie I de sa mémoire représente le résultat fourni par la machine simulée par U .)

Si VAEnum était décidable, la machine NegU qui représente FAEnum existerait. On pourrait alors s’en servir pour construire une autre machine AT qui aurait la propriété suivante. AT s’arrête si et seulement si (l’ état initial de la mémoire de AT représente une machine M, par son programme, et M ne s’arrête pas lorsque son état initial représente la machine M elle-même). AT serait représentée par un programme PrAT. TüringTuring a montré qu’il serait très facile d’écrire le programme PrAT si on avait le programme PrNegU de l’hypothétique NegU.