Vergleich unstetiger Funktionen: "Principle of Omniscience" und Vollständigkeit in der C-Hierarchie
Comparison of discontinuous functions: "Principle of Omniscience" and Completeness in the C-Hierarchy
- Es wird der Grad unstetiger Funktionen durch Vergleich mit zwei Funktionen, dem Principle of Omniscience und der Funktion C, festgelegt. Beim Vergleich wird eine bestimmte Reduzierbarkeitsrelation, die 2-Reduzierbarkeit, verwendet. Im ersten Teil wird gezeigt, dass es verschiedene Funktionenmengen und mehrwertige Funktionen gibt, die noch einfacher als das Principle of Omnicscience sind. Ferner wird ein Algorithmus entwickelt, mit dem berechnet werden kann, ob Funktionen aufeinander reduzierbar sind. Im zweiten Teil werden Funktionen definiert, die vollständig für die Klassen der C-Hierarchie sind. Für bestimmte Funktionen wird gezeigt, dass sie nicht vollständig sind.
- The dedree of discontinuity of functions is determined by comparison with two functions, the Principle of Omniscience and C. For the comparison a special reducibility relation, 2-reducibility, is used. In the first part it is shown that there are sets of functions and multi-valued functions, which are less difficult than the Principle of Omniscience. Further an algorithm is developed, which computes the answer, wether a function is reducible to another or not. In the second part functions are defined, which are complete for the different classes in the C-Hierarchy. For some functions it is shown, that they are not complete.
Author: | Uwe Mylatz |
---|---|
URN: | urn:nbn:de:hbz:708-27651 |
URL: | https://pub-data.leuphana.de/frontdoor/index/index/docId/517 |
Advisor: | Klaus Weihrauch (Prof. Dr.) |
Document Type: | Doctoral Thesis |
Language: | German |
Year of Completion: | 2006 |
Date of Publication (online): | 2007/08/21 |
Publishing Institution: | Leuphana Universität Lüneburg, Universitätsbibliothek der Leuphana Universität Lüneburg |
Granting Institution: | Leuphana Universität Lüneburg |
Date of final exam: | 2007/05/21 |
Release Date: | 2007/08/21 |
Tag: | Berechenbarkeit; Effektive Analysis; Unstetige Funktionen computability; discontinuous functions; effective analysis |
GND Keyword: | Unstetige Funktion; Analysis; Berechenbare Funktion; Berechenbarkeit; Reelle Funktion |
Institutes: | Universität / Frühere Fachbereiche |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |