Direkt zum Inhalt

Lexikon der Mathematik: induktives Zählen

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 tt + 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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.