Leçon 913 : Machines de Turing. Applications.

Dernier rapport du Jury :

(2017 : 913 - Machines de Turing. Applications.) Il s’agit de présenter un modèle de calcul. Le candidat doit expliquer l’intérêt de disposer d’un modèle formel de calcul et discuter le choix des machines de Turing. La leçon ne peut se réduire à la leçon 914 ou à la leçon 915, même si, bien sûr, la complexité et l’indécidabilité sont des exemples d’applications. Plusieurs développements peuvent être communs avec une des leçons 914, 915, mais il est apprécié qu’un développement spécifique soit proposé, comme le lien avec d’autres modèles de calcul, ou le lien entre diverses variantes des machines de Turing. .

Vous n'êtes pas d'accord avec les recasages ci-dessous ? Connectez-vous pour proposer les vôtres !

Développements :

• Fonctions récursives et Turing calculabilité
• Théorème de Cook
• Théorème de Savitch [pdf]
• Théorèmes de point fixe de Kleene et application [ref] [pdf]
• Implémentation de la beta-réduction dans une machine de Turing [ref]

Plans/remarques :

2018 : Leçon 913 - Machines de Turing. Applications.

2016 : Leçon 913 - Machines de Turing. Applications.

2015 : Leçon 913 - Machines de Turing. Applications.

Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Introduction to the theory of computation , Sipser (utilisée dans 12 versions au total)
Langages formels, Calculabilité et Complexité, Carton (utilisée dans 19 versions au total)
Computational complexity , Papadimitriou (utilisée dans 7 versions au total)
Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak (utilisée dans 4 versions au total)
Le Langage des machines, Floyd, Beigel (utilisée dans 7 versions au total)
Introduction to automata theory, languages and computation, Hopcroft, Ullman (utilisée dans 3 versions au total)
Mathématiques de l'informatique , Dehornoy (utilisée dans 8 versions au total)
Introduction à la calculabilité, Wolper (utilisée dans 3 versions au total)