Direkt zum Inhalt

Lexikon der Mathematik: LOOP-Hierarchie

Schleifenhierarchie, unendliche Hierarchie innerhalb der LOOP-berechenbaren Funktionen.

Die i-te Stufe dieser Hierarchie, LOOPi, ist dadurch charakterisiert, daß die zugrundeliegenden LOOP-Programme höchstens i ineinander verschachtelte LOOP-Schleifen enthalten dürfen.

Das Äquivalenzproblem für LOOP1-Programme ist zwar entscheidbar (Entscheidbarkeit), aber NP-vollständig. Das Äquivalenzproblem für LOOPi-Programme, i ≥ 2, ist nicht entscheidbar.

  • 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.