Machine de Turing non ambigüe

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.

En informatique théorique, une machine de Turing non ambigüe est une machine de Turing non déterministe qui admet au plus une exécution acceptante[1].

Notes et références[modifier | modifier le code]

  1. ↑ L. Hemaspaandra et J. Rothe, « Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets », SIAM Journal on Computing, vol. 26, no 3,‎ , p. 634–653 (ISSN 0097-5397, DOI 10.1137/S0097539794261970, lire en ligne, consulté le )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Machine_de_Turing_non_ambigüe&oldid=160971983 ».