Cette machine de Turing doit fonctionner éternellement sauf si les maths sont fausses

150 ans de mathématiques deviendront faux si un nouveau programme informatique cesse de fonctionner, mais cela ne se produira pas. Mais le code de ce programme pousse les limites du monde des mathématiques.


Une machine de Turing doit fonctionner éternellement pour éviter de contredire certaines modèles mathématiques célèbres.

Le programme est une machine de Turing, un modèle crée par Alan Turing. En 1936, il a montré que les actions de n’importe quel algorithme informatique peuvent être imitées par une simple machine qui lit et écrit des 1 et des 0 dans une séquence infinie en passant à travers différents états ou instructions. La quantité des états est proportionnelle à la complexité de l’algorithme.

Désormais, Scott Aaronson et Adam Yedidia du MIT ont créé 3 machines de Turing avec des comportements qui concernent des questions profondes de mathématique. Cela inclut la preuve de l’hypothèse de Riemann datant de 150 ans qui régit le pattern des nombres premiers. Depuis longtemps, on utilise les machines de Turing pour analyser de telles questions. Leurs origines se basent sur des révélations qui ont bouleversé les mathématiques dans les années 1930. En premier lieu, Kurt Gödel a prouvé que certaines déclarations mathématiques ne sont jamais vraies ou fausses, car elles sont indécidables. Il a créé une phrase célèbre qui illustre ce modèle mathématique avec : Cette phrase est fausse. Un casse-tête logique qui se contredit lui-même.

Toutes les choses sont impossibles à prouver

La déclaration de Gödel avait une clause de sortie. Si vous changez les suppositions de base à partir desquelles les preuves sont construites, à savoir, les axiomes, alors vous pouvez rendre un problème comme décidable. Mais c’est au prix de rendre les autres problèmes comme étant indécidables. Cela signifie qu’il n’y a pas d’axiomes qui vous permettent de prouver chaque chose.

Suivant les arguments de Gödel, Turing a prouvé qu’il doit exister certaines machines de Turing dont les comportements ne peuvent pas être prédits avec des axiomes standards, connus comme la Théorie des ensembles de Zermelo-Fraenkel avec l’axiome de choix C ou ZFC, qui est sous-jacent à la plupart des mathématiques. Mais on ignorait la complexité que ces machines pouvaient atteindre.

Désormais, Yedidia et Aaronson ont créé une machine de Turing avec 7 918 états qui possèdent cette propriété et ils l’ont nommé Z. On voulait savoir le nombre d’états possibles avant que vous plongiez dans les abysses de l’improbabilité selon Aaronson.

L’équipe a simulé le programme Z sur un ordinateur, mais il est suffisamment petit pour qu’on en fasse une machine selon Terence Tao de l’université de Californie. Et si on peut créer ce type de machine, alors en théorie, elle pourrait fonctionner indéfiniment du moment qu’on ignore les besoins physiques et énergétiques.

Aucune fin à l’horizon

Z est conçu pour lancer indéfiniment ses 7 918 instructions en boucle, mais s’il s’arrête, alors cela infirmerait la théorie ZFC. Les mathématiques ne s’effondreraient pas, car on passerait simplement à des ensembles d’axiomes plus longs. On connait déjà ce type d’axiomes et on peut les utiliser pour prouver le comportement de Z, mais il y aura toujours une machine de Turing qui pourra dépasser n’importe quel axiome.

On peut comparer le système d’axiomes à un ordinateur avec une mémoire et un calcul limité selon Tao. Vous pouvez augmenter le stockage, mais il y aura toujours des tâches qui nécessiteront plus de stockage. Mais Aaronson et Yedidia ont créé 2 autres machines de Turing pour donner plus de temps aux mathématiciens. Ces machines vont s’arrêter seulement, si 2 problèmes mathématiques célèbres considérés comme vrais, sont faux. C’est la conjoncture de Goldbach qui stipule que chaque nombre entier supérieur à 2 est la somme de 2 nombres premiers et l’hypothèse de Riemann qui stipule que tous les nombres premiers suivent un certain pattern. Et ce pattern forme la base de la théorie moderne des nombres. Si cette théorie est fausse, alors les mathématiciens devront commencer à s’inquiéter.

Des avantages pratiques

L’équipe n’a pas l’intention de faire fonctionner indéfiniment leurs machines de Turing. Ce n’est pas une manière efficace de s’attaquer au problème selon Lance Fortnow du Georgia Institute of Technology à Atlanta. L’expression des problèmes mathématiques avec des machines de Turing possède d’autres avantages pratiques. Elles permettent de déterminer la complexité. La machine de Goldbach possède 4 888 états tandis que celle de Riemann en possède 5 372 et Z en a 7 918. Et donc, le problème de Z est le plus complexe.

Yedidia a publié son code en ligne et les mathématiciens peuvent l’utiliser pour réduire la taille de ces machines de Turing en les poussant jusqu’à la limite. Un commentateur sur le blog d’Aaronson prétend qu’il a réussi à créer une machine de Goldbach de 31 états, mais il faudra le vérifier. Fortnow a déclaré que la taille des machines n’est pas pertinente, car on peut déjà avoir des états compressés qui vont au-delà de la puissance du ZFC. Mais Aaronson estime que la compression de Z va permettre de pousser les limites des fondations des mathématiques et c’était l’ambition de Turing et Gödel. Ils auraient pu dire : C’est bien, mais est-ce qu’on peut descendre à 800 états ? Quid d’une machine à 80 états ? Aaron conclut : Je voudrais savoir s’il y a une machine à 10 états dont le comportement est indépendant du ZFC.

Source : Scott Aaronson (PDF)

N'oubliez pas de voter pour cet article !
1 étoile2 étoiles3 étoiles4 étoiles5 étoiles (No Ratings Yet)
Loading...
mm

Jacqueline Charpentier

Ayant fait une formation en chimie, il est normal que je me sois retrouvée dans une entreprise d'emballage. Désormais, je publie sur des médias, des blogs et des magazines pour vulgariser l'actualité scientifique et celle de la santé.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *