Quelques liens utiles pour des démos sur les Machines de Turing
:
Un automate à pile pour
les palindromes. À adapter pour en faire une Machine de Tuting.
Pour les fonctions primitives récursives,
le Chapitre
8 poly de Patrick Dehornoy est une bonne référence, avec énormément
d'exemples à l'intérieur. Attention, les notations ne sont pas
tout à fait les mêmes que celles du cours. On notera le résultat
très intéressant donné par le Corollaire 1.22 page 232. Un examen
qui montre des résultats très intéressants sur les fonctions
primitives récursives
Modèles de calcul.
Le poly
de cours d'Eugène Asarin fait une bonne référence. Lire
notamment l'introduction (Chapitre 0) et la partie sur les modèles
de calcul plus simples que les MT : automates à deux piles et
automates à compteur (Chapitre 3). Sur les machines à compteur le
td de Victor Poupet décrit les étapes pour simuler une machine de
Turing avec une Machine à 3 compteurs.
Sur l'indécidabilité et les réductions on pourra lire les
transparents
d'Emmanuel Filiot, où sont décrits les 3 problèmes indécidables les
plus courants que sont l'arrêt d'une MT, le problème de
correspondance de Post (PCP) et le dixième problème de Hilbert. On
pourra aussi se reporter aux pages Wikipedia qui correspondent. Le
Chapitre 3
du poly
de Serge Haddad fournit quelques rédactions. Les transparents d'Anca
Muscholl sont aussi très intéressants.
La notion de réduction (polynomiale) est par exemple
décrite sur
les transparents
de Marie-Pierre Béal (avec
quelques exemples).