Eine ähnlich prinzipielle Frage stellte der Mathematiker David Hilbert im Jahre 1900 auf einem Kongress in Paris.

Eine positive Lösung des Problems hätte zur Folge gehabt, dass Computer mathematische Aussagen erzeugen und auch gleich noch deren Wahrheit oder Falschheit beweisen könnten.

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.