Modèle et réalité. La philosophie des sciences Le paradoxe du menteur (III) Au début du XXe siècle, le célèbre mathématicien David Hilbert pensait que le formalisme des mathématiques apportait une preuve irréfutable de la véracité des descriptions quantifiées.
Mais en 1931, Gödel bouscula cette convention. Il démontra qu'un système formel qui pouvait faire l'objet d'une description finie était incomplet et ne pouvait démontrer sa consistance (à la fois sa véracité et sa négation). Prenons par exemple le célèbre "paradoxe du menteur". Gödel s'explique. Si la légitimité des théorèmes ne peut être établie, on peut concevoir qu'ils aient une signification intuitive. Si Aristote avait connu Gödel, il cautionnerait certainement cette conclusion : toute extrapolation à partir d'un système formel qui n'ajoute aucune information est soit indécidable, soit ajoute un nouvel axiome indémontrable. Rassurons-nous, ces "abréviations" existent. L'expression de la réalité Comprendre exp(i*pi) Décidable, indécidable: binaire. En informatique, des mots de la vie courante prennent un sens particulier, précis, peut-être inattendu.
Nous allons expliquer ici « décidable ». En informatique, un problème est décidable s’il est possible d’écrire un algorithme qui résolve ce problème. Certains problèmes sont indécidables. Considérons par exemple le « problème de l’arrêt ». Le problème de l’arrêt consiste à déterminer, étant donné un programme informatique et des données en entrée pour ce programme, si le programme va finir pas s’arrêter ou s’il va continuer pour toujours. Cette notion de décidabilité se retrouve en logique. Cette notion d’indécidabilité a une conséquence plus subjective, dans nos rapports avec la science. Pour aller plus loin : Consulter l’article Binaire de Sylvie Boldo.Interstices nous en dit plus sur ce sujet avec Ganascia.J.P.
Serge Abiteboul, Thierry Viéville. La machine non stop de Turing. Le programme est une machine de Turing, un modèle mathématique 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. Turing, l'expérience des limites. Étrange destin que celui de l’œuvre de Turing (1912-1954) : jaugée à l’aune de la conception et de la réalisation des premiers ordinateurs, elle fut longtemps occultée sur ce terrain par la figure massive de von Neumann.
Ce n’est qu’à la faveur du travail d’historien mené à bien par Andrew Hodges au début des années 1980 que la connaissance de son œuvre quitta le cercle étroit des spécialistes et réoccupa la place capitale qui lui est due dans l’histoire de la notion de calcul, dans celle des machines à calculer et, plus généralement, dans notre société informatique. L’œuvre de Turing est en effet beaucoup plus diverse que ce que l’on en retient généralement. Elle est aussi beaucoup plus romanesque : écrivains et hommes de théâtre ne s’y sont pas trompés, eux qui ont reconnu très vite tout le parti qu’ils pouvaient tirer d’un itinéraire de vie aussi extraordinaire, tant du point de vue intellectuel que du point de vue des actions collectives auxquelles il participa.
Paradoxe de Gödel. Plus de 80 ans après sa découverte en 1930, le premier théorème d’incomplétude de Kurt Gödel (toute théorie formelle non contradictoire des mathématiques contient des propositions indécidables, c’est-à-dire dont on ne pourra démontrer ni qu’elles sont justes ni qu’elles sont fausses) suscite encore des interrogations et fait l’objet de compléments.
De remarquables résultats ont été publiés en 2002 par Leonid Levin, chercheur d’origine ukrainienne, maintenant professeur à l’Université de Boston ; ce logicien est connu pour avoir formulé en 1971, en même temps que Stephen Cook, la plus célèbre conjecture de l’informatique théorique, P fi NP (voir Les problèmes np sont-ils si compliqués ? , par J. -P. Delahaye, page 18). Edgar Morin et l’éloge du mystère.