Nachdem wir heute in der theoretischen Informatik wieder mal einen Beweis des Halteproblems gehört haben, wage ich auch mal einen Versuch, das ganze möglichst einfach für jedermann zu erklären, der Programmieren kann, aber ansonsten kein Wissen der theoretischen Informatik hat.

Annahme: Wir haben eine Funktion terminate?(f) welche true zurückgibt, wenn die als Parameter übergebene Funktion f terminiert, also irgendwann mal anhält, und ansonsten false. (Ende der Annahme.)

Nun schreiben wir eine andere Funktion, welche folgendes tut:

def f
  while terminate? f
    # Endlosschlaufe
  end
end

Das wars eigentlich schon. Was erwarten wir nun, wenn wir f aufrufen? Falls die Funktion anhält, würde das ja heissen, dass terminate?(f) false zurückgegeben hat, dass die Funktion also nicht terminiert, obwohl sie das soeben getan hat. Das gleiche haben wir, wenn wir annehmen, dass f nicht anhält: einen Widerspruch! Die Annahme ist also falsch. ∎

Ganz einfach und völlig logisch, oder? Was das ganze für Auswirkungen hat lässt sich sehr ausführlich diskutieren. Aber alle Mathematiker und Informatiker die ihren Job mögen sollten froh sein

(Und ich konnte endlich mal das coole ∎ Symbol benutzen.)