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

• Applicant: Professor Dr. Klaus Weihrauch
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants