Premium
DURCH SYNTAKTISCHE REKURSION DEFINIERTE KLASSEN
Author(s) -
Büning Hans Kleine
Publication year - 1983
Publication title -
mathematical logic quarterly
Language(s) - German
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19830290306
Subject(s) - citation , library science , computer science
Die syntaktisch beschrankte Rekursion wurde in [I] eingefuhrt, um gewisse Klassen zeitbeschrknkter Turingmaschinen rekursionstheoretisch beschreiben zu konnen. In anschliel3enden Untersuchungen, z. B. [3,4], hat sich diese Operation als sehr geeignek zur Beschreibung der inneren Komplexitat von Funktionsklassen erwiesen. So ist z. B. das klassische Problem PTIME = PTAPE formulierbar in der Rekursionstheorie als Frage nach der Gleichwertigkeit der beschrankten Rekursion und der syntaktisch beschrankten Rekursion mit gewissen Anfangsfunktionen. Ausgehend von der ublichen syntaktisch beschrknkten Rekursion werden wir neue Operationen einfuhren, indem wir die Anzahl der Rekursionsschritte reduzieren. Die daraus resultierenden Funktionsund Priidikatsklassen ergeben dann eine Hierarchie, die jedoch im Grenzfall beschrankte Rekursion versus syntaktisch beschrankte Rekursion in ihren Inklusionsbeziehungen off en bleibt .