Eléments d’ informatique théorique Série 10

Exercice 10.1 Montrer que l’ensemble des machines de Turing est dénombrable.

Exercice 10.2 Montrez que le langage \overline{L_{d}} = \{w | w = w_{i} et M_{i} accepte w_{i}\} est récursivement énumérable !

Exercice 10.3 Montrez que la réduction “many-one” est une relation réflexive et transitive !

Exercice 10.4 Halting problem Montrez que le langage L_{h} = {⟨M, w⟩ | M s’arrête sur w} n’est pas récursif (L_{u} ≤_{M} L_{h}) !

Exercice 10.5 Montrez que déterminer qu’un programme ‘C’ (quelconque) s’arrête pour toutes les valeurs de ses paramètres est indécidable !

Exercice 10.6 Montrez que le problème de déterminer si une machine de Turing s’arrête lorsque son mot d’entrée est le mot vide est indécidable !

Exercice 10.7 Montrez que le problème de déterminer si une machine de Turing s’arrête sur au moins un mot d’entrée est indécidable !