===== 1.5 Machines de Turing non-déterministes =====

{{page>c_et_c_def_8}}

=== Exemple ===

FIXME faut faire un dessin

=== déf : semi-décidabilité ===

{{page>c_et_c_def_9}}

=== déf : décision ===

{{page>c_et_c_def_a}}

=== déf : calcule ===

{{page>c_et_c_def_b}}

=== Remarque ===

Toute MT est un MTND. Est-ce qu'on peut avoir une MT équivalente à une MTND?

==== Théorème d'équivalence ====

Si une MTND décide (resp. semi-décide) un langage L, alors il existe une MT standard qui décide (resp. semi-décide) L.

=== Preuve ===