Lösbarkeit und Komplexität im Turingmaschinenmodell von numerischen Problemen über Funktionenräumen

• Applicant: Professor Dr. Peter Hertling
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 22442428

Numerische Verfahren werden oft nur in abstrakter Form beschrieben. Bei der Implementierung auf digitalen Computern können dann noch erhebliche Probleme auftreten. Es ist das Ziel dieses Projekts, numerische Probleme auf ihre Lösbarkeit und 2 Komplexität im Turingmaschinenmodell hin zu untersuchen, dem in der Berechenbarkeitstheorie und Komplexitätstheorie vorwiegend benutzten theoretischen Modell für digitale Computer. Dabei soll in diesem Projekt der Schwerpunkt auf Problemen liegen, die in der Information-Based Complexity untersucht werden, einer Teildisziplin der numerischen Mathematik, die mit einem real number-Modell arbeitet. Es soll überprüft werden, ob und inwieweit sich Ergebnisse der Information-Based Complexity zur Komplexität von numerischen Problemen in real number-Modell sauf das Turingmaschinenmodell übertragen lassen Hierzu sind zuerst einmal grundlegende berechenbarkeitstheoretische Fragen zur numerischen Mathematik, zur Maßtheorie und zur Funktionalanalysis zu klären. Anschließend sollen auch komplexitätstheoretische Fragen beantwortet werden.

• DFG Programme: Research Grants