Effektive Berechenbarkeit und die formalen Grundlagen von Maschinen

Der Begriff der effektiven Berechenbarkeit ,^4.1 konnte erst in den 30er Jahren unseres Jahrhunderts präzisiert werden. Das damalige Interesse an diesem Begriff war weniger durch eine Entwicklung heutiger Computer motiviert, sondern vielmehr durch erkenntnistheoretische Fragen zur Grundlegung der Mathematik. Man suchte nach einer Präzisierung dessen, was sich tatsächlich vom menschlichen Geist konstruieren läßt. Durch den Unendlichkeitsbegriff^4.2 in der Mathematik wurde diese Frage wichtig: Welche Elemente von unendlichen Mengen lassen sich konkret erzeugen - d.h. irgendwann, nach Anwendung von einer endlichen Zahl von Konstruktionsschritten ? Insofern expliziert der Begriff der effektiven Berechenbarkeit die Fähigkeit des menschlichen Geistes, konkrete Objekte zu konstruieren, welche hierbei durch syntaktische Ausdrücke beschrieben werden. Da jede endliche Menge sich immer in einer Liste notieren läßt, liegt das Interesse natürlicherweise erst bei der Konstruktion unendlicher Objektmengen.^4.3 Die Bedeutung des Begriffs der effektiven Berechenbarkeit, auch Algorithmus  genannt, geht über den Bereich der reinen Mathematik hinaus. Der Begriff präzisiert nicht nur die Klasse von effektiven Berechnungsverfahren, sondern auch die Mächtigkeit von wissenschaftlichen Beschreibungssprachen, innerhalb derer durch formale Mittel Einzelaussagen abgeleitet werden sollen. Die Problematik, die dabei für die Forschungsmethodologie in der künstlichen Intelligenz und der Kognitionswissenschaft erwächst, wird in Kapitel 6 ausführlich behandelt.

Im folgenden Abschnitt wird die historische Entwicklung des Algorithmenbegriffs dargestellt. Im zweiten Abschnitt werden Aspekte des Algorithmenbegriffs hervorgehoben, die einer allgemeinen Betrachtung von Algorithmen dienlich sein sollen. Im dritten Abschnitt wird der Begriff der universellen Turingmaschine vorgestellt. Im letzten Abschnitt des Kapitels wird auf den vorhergehenden Abschnitten aufbauend der Begriff der algorithmischen Information oder - synonym - der Kolmogoroffkomplexität eingeführt, der für die vorliegende Arbeit von zentraler Bedeutung ist.