Berechenbarkeit und Berechnungskomplexität physikalischer Theorien

• Applicant: Professor Dr. Martin Ziegler
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 106495341

• Final Report Year: 2010

Final Report Abstract

Bei Real Hypercomputation handelt es sich um die Synthese zweier aktueller Forschungsgebiete: der Theorie des Rechnens über und mit reellen Zahlen einerseits, andererseits der Entwicklung und Analyse von (diskreten) Rechenmodellen jenseits der Church-Turing Hypothese, sogenannten Hypercomputern. Hierzu haben wir Konzepte der diskreten Rekursionstheorie auf reelle Rechenmodelle übertragen (am nahe liegendsten das der Orakelmaschine) und zu vielen klassischen Resultaten und Charakterisierungen entsprechende Gegenstücke für den reellen Fall bewiesen - oftmals allerdings mit völlig neuen Beweisen: zusätzlich zu den typischerweise stark logisch geprägten Argumenten im Diskreten (Diagonalisierung und Turing-Grade, Richard-Berry Paradoxon, Königs Lemma) müssen hier algebraische (z.B. Transzendenzgrad) und/oder topologische Eigenschaften (z.B. Grad der Borel-Messbarkeit) der Informationsverarbeitung reeller Größen in Anschlag kommen. So konnten wir durch den systematischen Vergleich dieser drei Grad-Begriffe verschiedenste reelle Hypercomputer klassifizieren hinsichtlich ihrer Mächtigkeiten - und Chancen für die Realisierbarkeit.

Publications

• “An Explicit Solution to Post’s Problem over the Reals”, Journal of Complexity Bd.24.2008, pp. 3-15. (DOI: 10.1016/j.jco.2006.09.004) Lecture Notes in Computer Science, Vol. 3623. 2005, pp 467-478.
  K. Meer, M. Ziegler
  
• Kolmogorov Complexity Theory over the Reals. Electronic Notes in Theoretical Computer Science, Vol. 221. 2008, pp. 153–169.
  W.M. Koolen, M. Ziegler
  
• “Physically-relativized Church-Turing Hypotheses: Physical Foundations of Computing and Complexity Theory of Computational Physics”. Applied Mathematics and Computation, Vol. 215. 2009, Issue 4, pp. 1431–1447.
  M. Ziegler
  
• “Planar Visibility Counting”, pp.203–206 in Proc. 25th European Workshop on Computational Geometry (2009)
  M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, M. Ziegler
  
• “Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability”, pp.291–302 in Proc. 6th Int. Conf. on Computability and Complexity in Analysis (CCA2009)
  M. Ziegler
  
• “Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation”. Foundations of Computational Mathematics, vol.9.2009, Issue 5, pp.599–609.
  K. Meer, M. Ziegler
  
• “Skew Church-Turing Hypothesis”, 8th Int. Conf. on Unconventional Computation (UC2009)
  M. Ziegler
  
• “Variations of the Turing Test in the Age of Internet and Virtual Reality”, pp.355–362 in Proc. 32nd Annual Conference on Artificial Intelligence (KI2009), Springer LNCS/LNAI vol.5803
  F. Neumann, A. Reichenberger, M. Ziegler
  
• Expressiveness and Computational Complexity of Geometric Quantum Logic. Computing Research Repository (CoRR), 2010.
  C. Herrmann, M. Ziegler
  
• Real Analytic Machines and Degrees. Logical Methods in Computer Science, vol.7. 2011, Issue 3, pp.1–20, arXiv:1006.0398v3
  T. Gärtner, M. Ziegler
  
• Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability. Annals of Pure and Applied Logic, Vol. 163. 2012, Issue 8, , pp. 1108–1139.
  M. Ziegler