Machine de Turing alternante

En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. La définition de la classe NP utilise un mode « existentiel » pour les calculs : un calcul est acceptant s'il existe un choix qui amène en un état d'acceptation. La définition de co-NP en revanche utilise un mode « universel » de calcul : c'est seulement quand tous les choix possibles amènent à un état d'acceptation qu'un calcul est acceptant. Dans une machine de Turing alternante, le mode de calcul alterne entre ces deux modes. La notion de machine de Turing alternante étend celle de machine de Turing non déterministe. Les états sont de deux types : les états existentiels (notés pour "ou") et les états universels (notés pour "et"). Ainsi, une configuration (c'est-à-dire un état, un mot sur le ruban et une position de la tête) existentielle est acceptante s'il existe une configuration successeur acceptante ; une configuration universelle est acceptante si toutes les configurations successeurs sont acceptantes. Une machine accepte une entrée si la configuration initiale sur cette entrée est acceptante. Une machine de Turing alternante (à une bande) est une structure , où : est un ensemble fini d'états ; est lalphabet fini de la bande ; est la relation de transition ( et pour le déplacement à gauche respectivement à droite de la tête) ; est l'état initial ; spécifie le type de chaque état (existentiel ou universel).