le 27 octobre 2017 à 14:00
La thèse de Church-Turing affirme que des notions mathématiques particulières sont adéquates pour représenter les notions informelles de calculabilité effective ou de décidabilité mécanique. J’ai commencé par les contextes qui nécessitaient de telles notions mathématiques adéquates, à savoir les problèmes mathématiques (par exemple le 10e problème de Hilbert), les problèmes de décision en logique (par exemple le problème d’Entscheidungs pour la logique du premier ordre), et la caractérisation précise de la formalité (pour la formulation générale des théorèmes d’incomplétude de Göde).
L’approche classique de la calculabilité effective des fonctions de la théorie des nombres a conduit, par l’intermédiaire de Gödel et de Church, à une notion de calculabilité dans les calculs logiques et à des théorèmes d’absoluité métamathématiques. L’approche classique de la décidabilité mécanique des problèmes concernant les configurations syntaxiques a conduit, par l’intermédiaire de Turing et Post, à une notion de calculabilité dans les calculs formels (systèmes canoniques) et à des théorèmes de représentation métamathématiques.
Des caractéristiques particulières des calculs formels motivent la formulation d’un concept abstrait de système dynamique calculable. Ce concept articule des conditions de finitude et de localité qui sont satisfaites par les notions concertées standard de calcul. Un théorème de représentation peut être établi : Les machine de Turing peuvent simuler les calculs de tout système concret relevant de l’abstrait. J’esquisse une généralisation de cette approche pour obtenir des systèmes dynamiques parallèles calculables. Quelques applications concluront ma discussion.
En savoir plus...Bât M5 - Amphi Bacchus - Cité Scientifique - Villeneuve d'Ascq
français
English