Martin Ziegler

Veranstaltung Nr.175724

Vorlesung (V2)

Fr 14.15  - 15.45    P1408.1

Übung (Ü1)

Fr 16.00  - 16.45    P1408.1

Die Vorbesprechung findet am 15.10. statt!
 

Voraussetzungen

• Interesse
• Theoretische Informatik (Turingmaschinen etc.)
• Mathematik (Analysis, Algebra, Topologie etc.)
• Vorlesung "Advanced Computability" (WS03/04)
• für den dritten Studienabschnitt MuA, Modul  "2.3 Berechenbarkeit und Komplexität"
  und für PaSCo-Kollegiaten

Einführung

Inhaltsübersicht

1. Turing's Barrier
   1. Turing-Berechenbarkeit und Halteproblem
   2. Church-Turing Hypothese
   3. Klassifikation von Hypercomputern
   4. Physikalischer Hintergrund
      1. Einsteins Relativitätstheorie
      2. Quantenmechanik
      3. Analogcomputer
      4. zeitkontinuierliche Prozesse
      5. vorinitialisierte Systeme
2. Arithmetische Typ2-Hierarchie
   1. Erinnerung: diskrete Arithmetische Hierarchie
   2. Posts Problem über den reellen Zahlen
   3. Hyperberechenbare reelle Zahlen
   4. Hyperberechenbare reelle Funktionen
3. Unendlicher Parallelismus
   1. Zellulare Automaten (mit endl. Startkonfiguration)
   2. Unendlicher Nichtdeterminismus
   3. Unendlicher Turing-Parallelismus
   4. Typ2-Nichtdeterminismus
   5. Infinite-Time Maschinen
4. Dynamische Systeme
   1. Turingmaschine als dynamisches System
   2. Unentscheidbare Probleme dynamischer Systeme
   3. Matyasevitch, Tarski & Co.
   4. Semi-Entscheidbarkeit: Typ2 versus BCSS

Weiteres Material:

• Turings originale Motivierung `seiner' Maschine
• Turingmaschine bei Wikipedia
• Über Varianten/Präzisierungen `der' Church-Turing Hypothese: Seiten 10-13 von
  [T. Ord: «Hypercomputation: computing more than the Turing machine», Honours Thesis 2002]
• LIFE als Beispiel von unendlichem Parallelismus äquivalent zur Turingmaschine
• Übungsaufgaben: Blatt 2, Blatt 3

Literatur

• K. Weihrauch: «Computable Analysis», Springer 2000.
• L. Blum, F. Cucker, M. Shub, S. Smale: «Complexity and real computation», Springer 1998.
• T. Ord: «Hypercomputation: computing more than the Turing machine», Honours Thesis, University of Melbourne (2002).
• C. Moore: «Recursion theory on the reals and continuous-time computation», pp.23--44 in Theoretical Computer Science vol.162 (1996).
• C.E. Shannon: «Mathematical Theory of the Differential Analyzer», pp.337--354 in Journal of Mathematical Physics vol.20 (1941).
• P. Boldi, S. Vigna: «Equality Is a Jump», pp.49--64 in Theoretical Computer Science219 (1999).
• O. Bournez, M. Garzon, P. Koiran: «Computability properties of low-dimensional dynamical systems», pp.113--128 in Theoretical Computer Science vol.132 (1994).
• L. Blum, M. Shub, S. Smale: «On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions, and Universal Machines», pp.1-46 in Bulletin of the American Mathematical Society (AMS Bulletin) vol.21 (1989).
• M. Burgin, A. Klinger (Eds.): «Super-Recursive Algorithms and Hypercomputation», vol.317 von Theoretical Computer Science (2004).
• F. Cucker: «The arithmetical hierarchy over the reals», pp.375-395 in Journal of Logic and Computation vol.2(3) (1992).
• E. Eberbach, P. Wegner: «Beyond Turing Machines», pp.279-304 in Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin) vol.81 (2003).
• M. Gardner: «Wheels, Life and Other Mathematical Amusements», Freeman (1983).
• J.D. Hamkins: «Infinite Time Turing machines» (2002).
• M.L. Hogarth: «Does General Relativity Allow an Observer to View an Eternity in a Finite Time?», pp.173-181 in Foundations of Physics Letters vol.5(2) (1992).
• T. Kieu: «Hypercomputation with Quantum Adiabatic Processes», pp.93-104 in Theoretical Computer Science 317 (2004).
• T. Kieu: «Quantum Algorithm for Hilbert's Tenth Problem», pp.1461-1478 in International Journal of Theoretical Physics 42, Springer (2003).
• V.A. Adamyan, C.S. Calude, B.S. Pavlov: «Transcending the limits of Turing computability», to appear in International Journal of Theoretical Physics.
• C.S. Calude, B. Pavlov: «Coins, Quantum Measurements, and Turing's Barrier», pp.107--127 in Quantum Information Processing, vol.1, Plenum (2002).
• M. Ziegler: «Does Quantum Mechanics allow for Infinite Parallelism?», submitted (2004).
• K. Meer: «Real Number Models under Various Sets of Operations», pp.366-372 in Journal of Complexity vol.9 (1993).
• P. Orponen: «A Survey of Continuous-Time Computation Theory», pp.209-224 in Advances in Algorithms, Languages, and Complexity, Kluwer (1997).
• E. Spaan, L. Torenvliet, P. van Emde Boas: «Nondeterminism, Fairness and a Fundamental Analogy», pp.186-193 in The Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin) vol.37 (1989).
• A. C.-C. Yao: «Classical Physics and the Church-Turing Thesis», pp.100-105 in Journal of the Association for Computing Machinery vol.50(1) (2003).
• M. Stannett: «Computation and Hypercomputation», pp.115-153 in Minds and Machines, vol.13(1) (2003).
• Akitoshi Kawamura: «Type-2 Computability and Moore's Recursive Functions», pp.79-89 in Proc. 6th International Workshop on Computability and Complexity in Analysis (CCA'04), Informatik Berichte FernUniversität in Hagen vol.320 (Aug. 2004).
• R. Geroch, J.B. Hartle: «Computability and Physical Theories», pp.533-550 in Foundations of Physics vol.16(6) (1986).
• J. Copeland: «The Broad Conception of Computation», pp.690-716 in American Behavioural Scientist vol.40 (1997).
• J. Copeland: «Hypercomputation», pp.461-502 in Minds and Machines vol.12, Kluwer (2002).
• A.M. Turing: «On Computable Numbers, with an Application to the Entscheidungsproblem», pp.230-265 in Proc. London Math. Soc. vol.42(2) (1936).
• A.M. Turing: «On Computable Numbers, with an Application to the Entscheidungsproblem. A correction'', pp.544-546 in Proc. London Math. Soc. vol.43(2) (1937).
• K. Weihrauch, X. Zheng: «The Arithmetical Hierarchy of Real Numbers», pp.51-65 in Mathematical Logic Quarterly vol.47> (2001).
• V. Brattka, P. Hertling: «Topological Properties of Real Number Representations», pp.241--257 in Theoretical Computer Science vol.284 (2002).
• D. Moore: «Generalized shifts: Unpredictability and Undecidability in Dynamical Systems», pp.199--230 in Nonlinearity vol.4 (1991).
• V. Blondel, O. Bournez, P. Koiran, J.N. Tsitsiklis: «The Stability of Saturated Linear Dynamical Systems is Undecidable», pp.479--490 in Proc. 17th Symposium on Theoretical Aspects of Computer Science (STACS'2000), Springer LNCS vol.1770.
• E.D. Sonntag: «Mathematical Control Theory: Deterministic Finite Dimensional Systems», Springer, zweite Auflage (1998).