Alan Turing entwickelte die Turing-Maschine:

• Dabei beschränkte er sich auf einen kleinen Satz einfacher Funktionen und konnte zeigen, dass sich alle erwarteten komplexeren Funktionen auf diese wenigen einfachen Funktionen zurückführen lassen.

Alonzo Church und Stephen Kleene entwickelten das Lambda-Kalkül:

• Als Formalismus für die Beschreibung von mathematischen Funktionen, der ebenfalls auf wenigen einfachen Grundkonstrukten basiert und mit dem sich alle üblichen mathematischen Funktionen beschreiben lassen.

Church-Turing-These:

• Die intuitiv berechenbaren Funktionen sind genau die Funktionen, die mit einer Turing-Maschine oder dem Lambda-Kalkül berechenbar sind.

• Man bezeichnet eine Funktion als berechenbar, wenn sie mit einer Turing-Maschine (oder alternativ mit dem Lambda-Kalkül) berechenbar ist.

• Ein Berechnungsmodell, beispielsweise eine Programmiersprache, das in der Lage ist, alle berechenbaren Funktionen auch zu beschreiben bezeichnet man als Turing-vollständig.

• Alle üblichen Programmiersprachen sind Turing-vollständig, erfüllen also diese Bedingung.

• Bekannte Beispiele für Sprachen, die nicht Turing-vollständig sind, sind SQL , ebenso HTML ohne Skripte.

SQL ist nicht Turing-vollständig,

• da diese Sprache keine prozeduralen Elemente wie Zuweisungen oder Schleifen enthält.

• Man kann SQL um derartige Elemente erweitern und es gibt auch solche Spracherweiterungen auf dem Markt, aber diese Erweiterungen sind dann nicht Teil von Standard-SQL.

Dass bestimmte Funktinoen grundsätzlich nicht berechenbar sind

• unabhängig von der Größe des vorhandenen Speichers und der erlaubten Laufzeit.

Im Zweiten Weltkrieg arbeitete er als Kryptanalytiker und war führend an der Entschlüsselung des deutschen Funkverkehrs beteiligt, der auf Basis der damals sehr fortschrittlichen Enigma-Maschine verschlüsselt wurde.

Diese Arbeit war bis in die 1970er-Jahre geheim, obwohl – oder weil – sie wesentlichen Einfluss auf den Kriegsverlauf hatte, da sie dazu beitrug, einerseits deutsche U-Boote aufzuspüren und zu bekämpfen, und andererseits Nachschub-Konvois um diese U-Boote herumzuleiten und sicher über den Atlantik zu bringen.

Für diese Aufgabe arbeitete er auch an der Entwicklung des Colossus-Computers mit, einem auf elektronischen Röhren basierenden Computers, mit dem bereits 1943 die Entschlüsselung unterstützt wurde. Allerdings war dieser Computer noch nicht programmierbar, sodass es sich noch nicht um einen elektronischen Computer im heutigen Sinne handelte.

Ab 1948 arbeitete Turing an der Programmierung eines der ersten programmierbaren Computer, dem Manchester Mark I. Dabei beschäftigte er sich auch mit Fragen, die wir heute dem Gebiet der künstlichen Intelligenz zuordnen. So schrieb er das erste Schachprogramm und konzipierte den heute als Turing-Test bekannten Test, wann man einen Computer als „intelligent“ bezeichnen kann.

Aufbau einer Turing-Maschine

Eine Turing-Maschine besteht aus einem Speicherband, das selbst aus individuellen Zellen besteht und in beiden Richtungen unbegrenzt lang ist. In jeder Zelle kann ein Zeichen des verwendeten Alphabets, meist {0,1}, gespeichert werden. Außerdem hat die Turing-Maschine einen Schreib- und Lesekopf, der taktweise jeweils den in einer Zelle gespeicherten Wert einliest und gemäß einem in der Steuereinheit definierten Programm und abhängig vom aktuellen Zustand diesen Wert ggf. ändert. Anschließend kann der Schreib- und Lesekopf sich um eine Zelle nach links oder rechts bewegen und die Maschine geht in einen neuen Zustand über.

Das Band-Alphabet umfasst zusätzliche Steuerzeichen, mindestens ein Symbol für leere Zellen auf dem Speicherband.

Bei diesem Bandinhalt berechnet die Maschine den Wert baba. Allgemein vertauscht sie jeweils die Symbole a und b.

Benötigt werden die Zustände z0 (Startzustand), z1 (eine Eins benötigt), z2 (zwei Einsen benötigt), z3 (keine Eins benötigt) und zH.Folgendes Programm liefert die gewünschte Funktion ("_" steht für eine leere Speicherzelle):

0 

1

_

z0

(z3, 0, R)

(z2, 1, R)

(zH, _)

z1

(z1, 0, R)

(z3, 1, R)

(zH, 1)

z2

(z2, 0, R)

(z1, 1, R)

(z1, 1, R) 

z3

(z3, 0, R)

(z2, 1, R)

(zH, _)

Universelle Turing-Maschinen.

• Turing definierte eine universelle (Turing-)Maschine als eine Turing-Maschine, die jede andere Turing-Maschine simulieren kann.

• Anders formuliert ist eine universelle Turing-Maschine programmierbar. Sie nimmt eine Beschreibung einer andere Turing-Maschine zusammen mit dem Eingabewert entgegen und berechnet das Ergebnis, das diese Turing-Maschine mit diesem Eingabewert geliefert hätte.

Nicht-deterministische Turing-Maschine:

Einfache Erklärung des Textes:

Loop-Programme sind eine Art von Programmen, die Berechnungen ausführen können, ähnlich wie übliche Programmiersprachen (z. B. Python, Java). Sie basieren auf einer einfachen Struktur und bestehen aus:

1. Konstanten und Variablen: Zahlen oder Symbole, die gespeichert werden können, z. B. a, b, x, y.

2. Zuweisungen:

   • Man kann einer Variablen einen Wert zuweisen, z. B. x := a.

   • Es gibt spezielle Funktionen:

     • succ(a) bedeutet „Nächster Wert“, also a + 1.

     • pred(a) bedeutet „Vorheriger Wert“, also a - 1 (aber nicht kleiner als 0).

3. Aneinanderreihen von Befehlen: Man kann mehrere Befehle kombinieren, z. B. „Erst mach dies, dann das“.

4. Schleifen (Wiederholungen):

   • Eine Schleife wird durch Loop x Do P End beschrieben. Das bedeutet, dass der Schleifeninhalt P genau x-mal wiederholt wird.

   • Das ist ähnlich wie eine „For-Schleife“ in anderen Programmiersprachen, aber mit der Einschränkung, dass keine zusätzlichen Zählvariablen im Schleifeninhalt benutzt werden dürfen.

• Sie können keine unendlichen Schleifen erzeugen. Das heißt, die Programme liefern immer ein Ergebnis für jede Eingabe (sie sind „total“).

• Loop-Programme sind nützlich für viele Berechnungen, aber nicht mächtig genug, um alle mathematischen Probleme zu lösen.

• Sie sind nicht „Turing-vollständig“, was bedeutet, dass sie nicht alles können, was eine vollwertige Programmiersprache (wie Python) leisten kann.

While-Programme:

• Statt einer festen Anzahl an Wiederholungen (wie bei Loop-Schleifen) haben While-Programme Bedingungen. Eine Schleife wird so lange wiederholt, bis die Bedingung falsch wird (z. B. „solange x > 0“).

While-Programme:

Sie bestehen aus:

• Konstanten und Variablen (z. B. a, b, x, y).

• Befehlen wie x := a (Zuweisung eines Werts) oder Funktionen wie succ(a) (nächster Wert: a+1) und pred(a) (vorheriger Wert: a-1).

• Schleifen: While Bedingung Do P End, wobei P der Schleifeninhalt ist.

• Mehrere Befehle können hintereinander ausgeführt werden (Kombinationen wie P; Q).

• Sie können alle berechenbaren Funktionen ausdrücken und sind damit Turing-vollständig. Das bedeutet, dass sie genauso mächtig sind wie reale Programmiersprachen.

Goto-Programme arbeiten ohne Schleifen. Stattdessen gibt es bedingte Sprünge:

• Der Befehl If Bedingung Goto Stelle springt zu einer bestimmten Programmzeile, wenn die Bedingung wahr ist.

1. Sie sind ebenfalls Turing-vollständig und können theoretisch alles berechnen, was berechenbar ist.

2. Aber: Goto-Befehle machen Programme unübersichtlich und schwer zu verstehen.

Primitiv-rekursive Funktionen:

• Primitiv-rekursive Funktionen: Können durch Loop-Programme berechnet werden. Sie sind begrenzt, da sie keine Endlosschleifen erzeugen können.

μ-rekursive Funktionen:

• μ-rekursive Funktionen: Können durch While-Programme berechnet werden. Sie sind mächtiger und entsprechen den Turing-berechenbaren Funktionen.

Entscheidbarkeit beschreibt, ob es für ein Problem einen Algorithmus gibt, der immer eine korrekte Antwort liefert.

Ein Problem ist semi-entscheidbar, wenn man bei einem "Ja" sicher sein kann, dass die Antwort korrekt ist, aber bei einem "Nein" nicht immer Bescheid weiß.

Abzählbarkeit: Eine Menge (z. B. eine Sprache) ist abzählbar, wenn man ihre Elemente so durchnummerieren kann, dass jedes Element eine natürliche Zahl erhält.

Rekursiv aufzählbar: Eine abzählbare Menge ist rekursiv aufzählbar, wenn es einen Algorithmus gibt, der die Elemente systematisch aufzählen kann.

• Das Halteproblem ist eine berühmte Frage in der Informatik, die zeigt, dass es Grenzen gibt, was Computer berechnen können.

• Es geht darum, ob man einen Algorithmus schreiben kann, der für jedes beliebige Programm und jede Eingabe herausfindet, ob das Programm irgendwann stoppt (also hält) oder endlos weiterläuft.

Der Satz von Rice sagt, dass es keinen Algorithmus gibt, der allgemeingültig entscheiden kann, ob ein beliebiges Programm eine bestimmte nicht-triviale Eigenschaft besitzt.

Nicht trivial bedeutet, dass die Eigenschaft nicht für alle Programme gilt (immer "Ja") oder für keins der Programme gilt (immer "Nein").

Die Nicht-Entscheidbarkeit des Halteproblems besagt nur, dass es keinen allgemeingültigen Algorithmus für diese Aufgabe gibt. Wenn Programme von vornherein so konstruiert werden, dass sie terminieren, dann tun sie das auch. Dies kann man unter bestimmten Bedingungen sogar beweisen.

• Die Busy-Beaver-Funktion B(n) gibt an, wie viele Einsen die "fleißigste" Turing-Maschine mit nnn Zuständen maximal auf das Band schreiben kann, bevor sie anhält.

• Die Busy-Beaver-Funktion B(n) wächst schneller als jede berechenbare Funktion.

• Insbesondere ist sie selbst nicht berechenbar.