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.
Copyright Springer Verlag GmbH Deutschland 2017
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.