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

Exercice 9.1 Prouvez que tout langage accepté par une machine de Turing peut être accepté par une machine RAM (théorème 5.4.1)!

Exercice 9.2 Prouvez que tout langage accepté par une machine RAM peut être accepté par une machine de Turing (théorème 5.4.2)!

Exercice 9.3 Montrez informellement que la fonction suivante est récursive totale:

premier(n) = \{ \begin{matrix}0 si n est premier \\ 1 sinon \end{matrix}

Exercice 9.4 Montrez que l’union de deux langages récursivement énumérables est un langage récursivement énumérable (théorème 5.5.3)!