Machine de Turing non déterministe

Dans une machine de Turing non déterministe, pour chaque état et symbole, il existe un groupe d'actions que la MT peut avoir. Donc, ici, les transitions ne sont pas déterministes. Le calcul d'une machine de Turing non déterministe est un arbre de configurations accessible depuis la configuration de départ.

Une entrée est acceptée s'il y a au moins un nœud de l'arbre qui est une configuration acceptée, sinon elle n'est pas acceptée. Si toutes les branches de l'arbre de calcul s'arrêtent sur toutes les entrées, la machine de Turing non déterministe est appeléeDecider et si pour certaines entrées, toutes les branches sont rejetées, l'entrée est également rejetée.

Une machine de Turing non déterministe peut être formellement définie comme un 6-tuple (Q, X, ∑, δ, q ₀ , B, F) où -

• Q est un ensemble fini d'états

• X est l'alphabet de la bande

• ∑ est l'alphabet d'entrée

• δ est une fonction de transition;

  δ: Q × X → P (Q × X × {Left_shift, Right_shift}).

• q₀ est l'état initial

• B est le symbole vide

• F est l'ensemble des états finaux