Models of hypercomputation

Abstract

Der Darlegung von Grundsätzen der Berechenbarkeitstheorie folgt die Diskussion einiger Versionen und Interpretationen der sogenannten Church-Turing- These. Anschließend wird eine formale Definition der Hyperberechenbarkeit gegeben. Daraufhin werden einige abstrakte und physikalische Hypermaschinenmodelle aus der Literatur präsentiert. Diese sind in erster Linie Turingmaschinen mit unendlicher Zeit, Quantencomputer und relativistische Maschinenmodelle.<br />Grundlegende Prinzipien dieser Modelle und ihre Rechenkraft werden diskutiert.<br />

After presenting preliminary knowledge in Computability Theory, some versions and interpretations of the so called Church-Turing thesis will be discussed.<br />A formal definition of hypercomputation will be given. Some proposed abstract and physical hypermachine models from the literature will be presented. These will be (mainly) innite time Turing machines, quantum computers and relativistic machine models. Basic principles behind these models and their computational power will be discussed.