Erst 1936 wurde das Problem gelöst
Nicht-Existenz ist oft schwer zu beweisen
|
Erst im Jahr 1936 konnten sowohl Alonzo Church als auch Alan Turing beweisen, dass obiges Entscheidungsproblem nicht lösbar ist.
Warum hat es 36 Jahre gedauert, bis das Problem gelöst wurde?
- Wenn man beweisen will, dass ein Verfahren zur Lösung eines Problems existiert, dann ist es das Einfachste, man gibt das Verfahren an.
- Wenn man aber nachweisen möchte, dass kein Verfahren zur Lösung eines Problems existiert, dann muss man beschreiben, was ein Verfahren überhaupt ist! D.h. man muss klären, aus welchen elementaren Anweisungen ein Verfahren aufgebaut ist und wie sich ein Mensch oder eine Maschine verhalten, wenn sie diese Anweisungen ausführen.
Genau diese Überlegungen haben Alan Turing 1936 zu der Idee der Turingmaschine geführt.
|
