Les machines alternantes sont une généralisation des machines non déterministes. Ces dernières autorisent par rapport aux machines déterministes, des choix existentiels. Plusieurs calculs sont possibles et Une entrée est acceptée si au moins un de ces calculs est acceptant. Les machines alternantes offrent en plus des choix universels. De surcroît, les choix existentiels et universels peuvent alterner au cours d'un calcul.
On donne ici la définition d'une machine de Turing alternante. De la même manière, on aurait aussi pu définir des automates alternants et on aurait obtenu des automates qui acceptent encore des langages rationnels.
Une machine alternante, est une machine de Turing où l'ensemble Q des états est partitionné en deux ensembles Q∨ et Q∧ appelés respectivement ensembles des états existentiels et des états universels.
Un calcul pour une machine alternante M n'est plus une suite de configurations comme pour une machine non déterministe mais un arbre dont les nœuds sont étiquetés par des configurations de M et qui vérifie les conditions suivantes. Si un nœud x est étiqueté par une configuration C = uqv où q est un état existentiel, alors x doit avoir un seul fils qui est étiqueté par une des configurations C' tel que C ⇒ C'. Si un nœud x est étiqueté par une configuration C = uqv où q est un état universel, alors x doit avoir un fils étiqueté par chaque configuration C' tel que C ⇒ C'. Le nœud x a donc autant de fils que de transitions applicables à la configuration C. Une branche du calcul est dite acceptante si une des configurations le long de la branche est acceptante. Le calcul sur une entrée w est finalement acceptant si la configuration à la racine est la configuration initiale q0w et si toutes ses branches sont acceptantes.
Dans un calcul, les configurations le long d'une branche forment une suite de configurations consécutives. On remarque que si tous les états sont existentiels, un calcul de la machine est un arbre filiforme ou chaque nœud a un seul fils. On retrouve la définition d'un calcul pour une machine non déterministe qui est suite de configurations successives.
Le temps d'un calcul d'une machine de Turing alternante est par définition la profondeur de l'arbre. L'espace du calcul est la taille maximale d'une configuration apparaissant dans le calcul. Pour une fonction t de N dans R+, on définit les classes ATIME(t(n)) et ASPACE(t(n)) des problèmes décidés par des machines de Turing alternantes en temps et en espace t(n). On définit aussi les classes AP et APSPACE pour les problèmes décidés en temps et espace polynomial par des machines de Turing alternantes.
Le théorème suivant relie les classes ATIME et ASPACE des machines alternantes aux classes TIME et SPACE des machines déterministes.
Théorème.
Corollaire. On a les égalités AP = PSPACE et ASPACE = EXPTIME.