HEINZ NIXDORF INSTITUT
University of Paderborn
Theoretical Computer Science
Group of Meyer auf der Heide


Hypercomputation

WS 04/05

 

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

 

Einführung

Für die heutzutage als `Turingmaschine' bekannte Abstraktion eines Digitalcomputers hat Alan Turing 1936 bewiesen, daß zahlreiche praktisch relevante Problemstellungen durch sie prinzipiell algorithmisch nicht lösbar sind. In den letzten Jahren mehren sich jedoch Hinweise und Ansätze, denenzufolge andere Rechenprozesse realisiert werden könnten, die zumindest manche dieser Probleme behandelbar machen. Solche sogenannten Hypercomputer besitzen also Fähigkeiten, die grundsätzlich über die einer Turingmaschine hinausgehen.

 

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:

Literatur


Martin Ziegler