Real Hypercomputation: Berechenbarkeitstheorie reeller Funktionen jenseits der Church-Turing Hypothese

• Antragsteller: Professor Dr. Martin Ziegler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5453346

Die Turingmaschine ist heutzutage allgemein akzeptiert zur Modellierung der grundsätzlichen Möglichkeiten jeglichen Rechnens. Beispielsweise das Halteproblem ist durch sie beweisbar nicht entscheidbar [Turing 1936]; und damit, der Church-Turing Hypothese zufolge, auch durch kein anderes Verfahren. Die Gültigkeit dieser (Interpretation der) Hypothese wird in letzter Zeit jedoch stark in Frage gestellt; es gibt sogar konkrete Ansätze, wie unter Ausnutzung der Relativitäts- oder Quantentheorie das Halteproblem zumindest prinzipiell gelöst werden könnte. Darauf basierende sogenannte Hypercomputer besitzen also Fähigkeiten, die grundsätzlich über die der Turingmaschine hinausgehen. Diese Fähigkeiten sind für verschiedene Modelle von Hypercomputern (unter anderem, aber nicht nur, den Orakel-Turingmaschinen) bereits präzise charakterisiert worden, was diskrete Probleme d.h. solche über ganzen und rationalen Zahlen betrifft. In der Praxis ergeben sich jedoch Problemstellungen über den reellen Zahlen. Zur Untersuchung der grundsätzlichen Möglichkeiten reellen Rechnens sind aus der (diskreten) Turingmaschine verschiedene Varianten hervorgegangen, wie zum Beispiel das BCSS-Modell (von Blum, Cucker, Shub und Smale) oder die Typ2-Maschine (u.a. Turing, Grzegorczyk und Weihrauch). Diese spiegeln jeweils gewisse Aspekte realer Computer im Umgang mit reellen Zahlen wider, sind aber grundsätzlich inäquivalent. Auch für sie impliziert Turings Ergebnis von 1936 harte prinzipielle Grenzen in Form der algorithmischen Unlösbarkeit wichtiger reeller Probleme wie beispielsweise die Entscheidbarkeit der Konvergenz des Newton-Verfahrens für gegebenen Startwert (BCSS) oder die Berechnung unstetiger Funktionen (Typ2). Und auch hier bieten Hypercomputer das Potential, solche Grenzen zu überschreiten. Ob und wie weit, wollen wir im Projekt Real Hypercomputation untersuchen, d.h. in einer Kombination der Gebiete Hypercomputation und Reelle Berechenbarkeitstheorie. Genauer ergeben sich aus den verschiedenen reellen Rechenmodellen und den verschiedenen diskreten Hypercomputern (u.a. Orakel-Maschinen, aber auch anderen) eine große Zahl potentieller reeller Hypercomputer, deren grundsätzliche Fähigkeiten untersucht und verglichen werden sollen. Dies beinhaltet einerseits die Entwicklung von Simulations-Algorithmen, um beispielsweise zu zeigen, daß Modell A mindestens so mächtig ist wie Modell B; andererseits die Identifizierung separierender Beispielprobleme, um beispielsweise zu zeigen, daß A sogar echt mächtiger ist als B. Zugrunde liegt die Aussicht, die unvergleichbaren bisherigen reellen Modelle als untere Stufen in eine Hierarchie reeller Hypercomputer einzubetten und so systematisch einordnen zu können. Weiterhin bieten der reellen Berechenbarkeit eigene zusätzliche mathematische Aspekte wie Algebra und Topologie die Aussicht, jeweils Modell-charakteristische (Gegen-)Beispiele ohne Diagonalisierung explizit angeben und so leichter der Intuition zugänglich machen zu können.

• DFG-Verfahren: Sachbeihilfen