« 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
Contenu supprimé Contenu ajouté
m Retrait des catégories en double |
m Robot : Remplacement de texte automatisé (-\b([Qq])ue ([AEIOUaeéèêiou]) +\1u'\2) |
||
Ligne 12 :
À partir de l’existence d’un ensemble indécidable on ne peut pas conclure qu’il y a des problèmes mathématiques bien définis et néanmoins insolubles, mais seulement qu’il n’existe pas de méthode unique et bien définie pour répondre à toutes les questions, en nombre infini, qui portent sur certains ensembles bien définis.
Tous les théorèmes sur l’incomplétude de la prouvabilité axiomatique peuvent être considérés comme des corollaires des théorèmes d’existence d’ensembles indécidables. Le raisonnement est le suivant. Une théorie axiomatique T est toujours énumérable. Si elle est suffisamment riche, elle permet de définir un ensemble indécidable Indécid et son complémentaire C-Indécid. Si T était complète, elle contiendrait toutes les vérités sur C-Indécid. Comme T est énumérable, C-Indécid serait alors lui aussi énumérable. Mais C-Indécid n’est pas énumérable, parce
La présente section expose la preuve de Turing 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 Turing, et prouver l’existence d’une machine de Turing 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,
Il est également possible de définir un ensemble VAEnum de toutes les vérités atomiques d’appartenance aux les ensembles énumérables. Le théorème fondamental de l’énumérabilité dit que VAEnum est énumérable. Autrement dit, l’ensemble de toutes les vérités atomiques d’appartenance aux ensembles énumérables est énumérable. Une vérité atomique d’appartenance sur les ensembles énumérables est une formule atomique vraie qui dit qu’une expression formelle appartient à l’ensemble énumérable nommé par une autre expression formelle.
Ligne 31 :
Une machine de Turing 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 Turing 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 Turing, Enum ainsi défini est bien un ensemble de noms de tous les ensembles énumérables.
Dans une machine de Turing 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
L’existence d’une machine universelle U montre que VAEnum est énumérable. Les énoncés atomiques sont représentés par les états initiaux de la mémoire de U. Un état initial représente l’énoncé que l’expression formelle représentée dans I appartient à l’ensemble énumérable représenté dans P. Les énoncés sont vrais lorsque U s’arrête, faux sinon.
Ligne 43 :
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. Turing a montré qu’il serait très facile d’écrire le programme PrAT si on avait le programme PrNegU de l’hypothétique NegU.
Supposons que l’état initial de la mémoire de AT soit chargée avec PrAT. Est-ce
En s’arrêtant après avoir été initialisé avec PrAT, la machine AT, conçue comme un diseur de vérités, dirait d’elle-même qu’elle ne s’arrête pas après avoir été initialisé avec PrAT. Il s’agit donc bien du paradoxe du menteur.
| |||