ABSTRAKTE TEMPOMASZE UND SPEED-UP-THEOREMEA FÜR ENUMERATIONEN REKURSIV-AUFZÄHLBARER MENGEN
✍ Scribed by Hans-Dietrich Hecker
- Book ID
- 102939472
- Publisher
- John Wiley and Sons
- Year
- 1984
- Tongue
- English
- Weight
- 859 KB
- Volume
- 30
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
ABSTRAKTE TEMPOMASZE UND SPEED-UP-THEOREME m R ENUMERATIONEN REKURSIV-AUFZAHLBARER MENGEN von HANS-DIETRICH HECKER in Greifswald (DDR) I ) Einleitung Lassen sich berechenbare Funktionen durch ihre Berechnungskompliziertheit bezuglich eines KomplexitatsmaBes von BLUM charakterisieren? Lassen sich analog rekursivaufziihlbare Mengen durch die Kompliziertheit ihrer einfa,clisten Enumerationen beziiglich der Enumerationsgeschwindigkeit charakterisieren? Die erste Frage wurde 1967 in dem beriihmten Artikel [I] von M. BLUM mit seinem speed-up-Theorem negativ beantmortet. ErwartungsgemaB fallt auch die Antwort auf die zweite Frage negativ aus. P. YOUNG zeigte 1969 ([14]) ein sehr tiefliegendes Resultat, indem er nachwies, daB es fiir Enumerationstechniken aller rekursiv-aufziihlbaren Mengen stets solche Mengen gibt, fur die ein , ,speed-up" durch Anderung der Enumerationsreihenfolge erreichbar ist (der Begriff wird hier genau definiert werden). Schon damals wurde auf die Mog-Iichkeit eines anderen speed-up-Theorems hingewiesen. Wir werden hier einen Beweis dafiir vorstellen. I n den bis jetzt geschriebenen Arbeiten uber Enumerationen spielt ausschlieBlich ein ganz bestimmtes konkretes ,,EnumerationstempomaG" eine Rolle, bezuglich dessen Kompliziertheitsaussagen uber enumerierte Mengen erhalten werden. In dieser Arbeit losen wir uns von einem solchen MaB und fordern analog zum Ansatz V O : ~ M. BLUM sehr schwnche Axiome fur ein ,,Enumerationstempo". Neben grund-* ) Die vorliegende Arbejt enthflt einen Teil der Resultate dcr Dissertation B (Qreifswald 1983) des Verfassers. Ich danke Herrn Prof. Dr. G. ASSER fur die anregenden Diskiissionen und zahlreiche wertvolle Hinweise. ? I , .