TRI* sur l'indécidabilité

T.R.I. ? : De la semi-décidabilité incalculable à l'indépendance Tarik Kaced 17 février 2009 Table des matières 1 Résumé 1 2 Travail 2 2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.1 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.2 Calculabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.3 La hiérarchie arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Conjecture de Goldbach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2.1 Du point de vue logique . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2.2 Du point de vue calculabilité .

• système de programmation acceptable


• machine universelle


• interpréteur


• approximation de ?


• hiérarchie arithmétique


• équation diophantienne


• chaitin