Natürliche Definitionen von Berechenbarkeit und Komplexität numerischer Probleme

• Antragsteller: Professor Dr. Klaus Weihrauch
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2004
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5320346

Bei der algorithmischen Behandlung kontinuierlicher Modelle, die in den Natur- und Ingenieurwissenschaften und in vielen Bereichen der Informatik verwendet werden, treten charakteristische Probleme auf, die sich weder mit den Methoden der Analysis und der Numerik noch mit der Berechenbarkeits- und der Komplexitätstheorie zufriedenstellend behandeln lassen. Die Berechenbare Analysis soll diese Lücke schließen. Zur Zeit besteht sie aus einer schwer überschaubaren Sammlung mehr oder weniger konsistenter Fragmente, in der auf zahlreiche, selbst naheliegende grundlegende Fragen, keine Antworten zu finden sind. Das beantragte Vorhaben ist Teil eines langfristig angelegten Projektes, in welchem die berechenbare Analysis als eigenständige Theorie aufgebaut wird. Es sollen derzeit anstehende wichtige Fragen untersucht werden, so z. B.: Wie definiert man rekursive Teilmengen eines metrischen Raumes? Wie rechnet man auf Distributionen? Für welche Funktionen/Operatoren kann man sinnvoll Komplexität definieren? Wie sehen die Komplexitätshierarchien aus? Welche Komplexität haben aus der Numerik bekannte Funktionen und Operatoren?

• DFG-Verfahren: Sachbeihilfen