Schon Alan Turing hat sich darüber Gedanken gemacht, welche Problem sich automatisiert lösen lassen, und ob man für jedes Problem eine Maschine bauen könnte. Dabei hat er die Turingmaschine entwickelt.
Viel zu viele Entscheidungen.
Automaten basieren auf der grundlegenden Funktionsweise von Entscheidungsfragen. Ein Automat kann in seiner Quintessenz ein Wort akzeptieren oder es nicht akzeptieren. Er kann also entscheiden, ob die Eingabe valide oder nicht valide ist. Zum Beispiel kann ein Automat einfach entscheiden, ob eine Zahl gerade oder ungerade ist (Er prüft einfach die letzte Ziffer). Solche Probleme, welche ein Automat ganz einfach lösen kann heißen Entscheidbar.
Als Gegenbeispiel wäre dagegen die Frage, ob eine bestimmte Mathematische Funktion eine Lösung besitzt. Dabei müsste dann der Automat jede Zahl testen, bis er eine Lösung gefunden hat. Sobald der Computer eine Lösung findet, ist die Frage einfach mit Ja zu beantworten. Jedoch können wir solange wir keine Lösung haben nicht sagen, dass es keine gibt. Vielleicht ist ja schon die übernächste Zahl eine Lösung. In so einem Fall können wir also nur in einem Teil der Fälle eindeutig eintscheiden, ob die Aussage wahr oder falsch ist. Solche Probleme sind dann Semi-Entscheidbar.
Und als dritte Klasse gibt es dann noch die Nicht-Entscheidbaren Probleme, für welche es keinen weg gibt in polynomischer Laufzeit, (also nicht exponentiell) eine Lösung zu finden. Also kann ein Computer keine schlaue Berechnung zum Lösen anstellen, sonder muss jede Möglichkeit einzeln durchprobieren. Ein prominentes Problem dabei ist dann das Halteproblem.
Halteproblem
Das Halteproblem versucht zu bestimmen, ob ein Program existiert, welches eindeutig feststellen kann, ob ein anderes Program Terminiert, also hält, oder unendlich lange weiterläuft. Turing stellt sich nun vor, dass es eine Maschine H gibt, welche bei einem Halten des Eingabeprogrammes ja ausgibt und bei unendlichem weiterlaufen Nein.
Nun wird H+ als Erweiterung von H definiert, welche bei einem Ja von H unendlich weiter läuft und bei einem Nein stoppt. Weil unsere Maschine H+ genauso wie H jedes Maschine als Eingabe nehmen kann, kann man ihr auch sich selber mit einem anderen Eingabeprogram geben.
Nun füttert man also H1+ mit H2+ und einer Eingabe E für H2+ Dies würde bedeuten, dass, wenn E terminiert, dann H2+ Ja ausgibt, nicht terminiert und unendlich weiter läuft. Damit gibt dann H1+ ebenfalls Nein aus, da H2+ ja nicht terminiert. Somit kommt es zu einem Widerspruch und die These ist widerlegt.
