Beweismethode, die im Beweis des Satzes von Immerman-Szelepcényi (Immerman-Szelepcényi, Satz von) benutzt wird.

Ziel ist es, die Anzahl der (bei einer gegebenen Anzahl von Zellen auf dem Arbeitsband) erreichbaren Konfigurationen einer nichtdeterministischen Turing-Maschine so nichtdeterministisch zu berechnen, daß die Turing-Maschine entweder die Rechnung abbricht oder aber (und das auf mindestens einem Rechenweg) die gesuchte Anzahl berechnet. Dabei werden induktiv die in t Schritten erreichbaren Konfigurationen gezählt. Im Induktionsschritt t → t + 1 wird das Ergebnis für t verwendet, um sicherzustellen, daß alle in t Schritten erreichbaren Konfigurationen nichtdeterministisch erzeugt werden. Eine Konfiguration ist in t + 1 Schritten genau dann erreichbar, wenn sie in t Schritten erreichbar oder eine direkte Nachfolgekonfiguration <?PageNum _485einer in t Schritten erreichbaren Konfiguration ist.