Berechenbare Analysis und Grade der Zufälligkeit (CADoR)

• Antragsteller: Privatdozent Dr. Rupert Hölzl; Privatdozent Dr. Wolfgang Merkle
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 556436876

Das Projekt "Computable Analysis and Degrees of Randomness (CADoR)" ist im Grenzgebiet zwischen berechenbarer Analysis und algorithmischer Zufälligkeit angesiedelt. In der berechenbaren Analysis wird insbesondere die effektive Approximierbarkeit reeller Zahlen untersucht. Die beiden wichtigsten Approximationsbegriffe sind der einer berechenbar approximierbaren Zahl, also einer reellen Zahl, die Grenzwert einer berechenbaren Folge von rationalen Zahlen ist, und der einer linksberechenbaren Zahl, für die zusätzlich gefordert wird, dass die approximierende Folge monoton wachsend ist. Beide Approximationsbegriffe lassen sich durch Zusatzbedingungen weiter verfeinern. In der algorithmischen Zufälligkeit werden Zufälligkeitsbegriffe für unendliche Binärfolgen, kurz Folgen, untersucht. Die beiden wichtigsten Ansätze sind dabei, eine Folge als zufällig anzusehen, falls diese nicht komprimierbar beziehungsweise nicht vorhersagbar ist. Nicht vorhersagbar bedeutet formal, dass beim sukzessiven Wetten auf die Bits der Folge mit fairer Auszahlung das erreichbare Kapital beschränkt ist. Die zulässigen Kompressionsmethoden und Wettstrategien werden dabei in geeigneter Weise auf bestimmte effektive Verfahren eingeschränkt. Je nachdem, wie stark die zulässigen Verfahren sind, ergeben sich unterschiedlich starke Zufälligkeitsbegriffe. Neben derartigen absoluten werden auch relative Zufälligkeitsbegriffe wie die Solovay-Reduzierbarkeit untersucht, die es erlauben, den Grad der Zufälligkeit zweier Folgen zu vergleichen. Zwischen algorithmischer Zufälligkeit und berechenbarer Analysis bestehen enge Zusammenhänge, die seit den 1970er Jahren untersucht werden, dabei werden reelle Zahlen über ihre Binärdarstellung mit Folgen identifiziert. Von besonderem Interesse für das Projekt CADoR sind Beziehungen zwischen dem Grad der Zufälligkeit einer reellen Zahl und der Güte und speziell der Konvergenzgeschwindigkeit ihrer effektiven Approximationen. Zwei weitere Schwerpunkte sind Untersuchungen zu den Approximations- sowie den absoluten und relativen Zufälligkeitsbegriffen selbst. Alle drei genannten Schwerpunkte haben gemeinsam, dass die jeweiligen Fragestellungen in der Literatur bisher hauptsächlich im Zusammenhang mit linksberechenbaren Zahlen untersucht wurden und für diesen Fall eine Reihe von zentralen Ergebnissen erzielt wurden. Das Projekt CADoR verfolgt den Ansatz, für die genannten Schwerpunkte zu untersuchen, ob und in welcher Form sich solche Ergebnisse auf umfassendere Klassen wie die die berechenbar approximierbaren oder alle reellen Zahlen übertragen lassen. Dabei ist zunächst zu klären, in welcher Weise Begriffsbildungen wie Beschleunigbarkeit einer reellen Zahl oder Solovay-Reduzierbarkeit erweitert werden sollen: im linksberechenbaren Fall sind diese Begriffe in naheliegender, natürlicher Weise definiert, wohingegen sich für die Erweiterung auf umfassendere Mengen von reellen Zahlen verschiedene nichtäquivalente Varianten anbieten.

• DFG-Verfahren: Sachbeihilfen