Nature UE
Crédits ECTS 3
Volume horaire total 30
Volume horaire CM 16
Volume horaire TD 14

Pré-requis

Algorithmique, langage de programmation, logique et arithmétique

Objectifs

Connaissance épistémologique, énoncé et preuve de théorème de logique

Contenu

Chapitre 1: Machine de Turing, Problème de décision, Langage, Hypothèse I.A. Test de Turing, Chambre de Searle, Processus privés, Problème de Hilbert, Indécidabilité de Gödel, Quelques problèmes indécidables.
Chapitre 2 : Infinis, Paradoxe, Cardinal, Ensembles dénombrables et non dénombrables, Hiérarchie de Cantor. Hypothèse du continu, Théorème de Cantor-Berstein, Paradoxe de Berry, Antinomie de Russel, Axiomatique ZFC, Axiome du choix et au delà…
Chapitre 3 : Fonctions récursives primitives, Existence de fonction non récursive primitives, Fonction d’Ackermann-Péter, Fonctions récursives, partielles et totales, Modèle des machines à registres, Notations, Séquentialité, Théorème d’équivalence.
Chapitre 4 : Machine de Turing, Équivalence entre machine, Problème de l’arrêt.
Chapitre 5 : Processus contrôlé et point d’attention, Système de codages, Théorèmes de Kleene, Théorème d’itération et de récursion de Kleene. Théorème du point fixe. Ensemble sémantique, Décidabilité.

Appartient à

Informations complémentaires

Connaissance épistémologique, énoncé et preuve de théorème de logique