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
Schreiben Sie uns!