Lösbarkeit des Halteproblems

Annahme: Das Halteproblem ist lösbar

Das Halteproblem besteht darin, eine Funktion (mit Funktionsdefinition) zu entwickeln, mit der man testen kann, ob eine übergebene Funktion bei der Verarbeitung übergebener Daten hält oder nicht.

Wir zeigen jetzt, dass es keine Funktionsdefinition (in Python) für die Funktion istHaltend geben kann. Hierzu nehmen wir an, dass es eine solche Funktiondefinition gibt:

def istHaltend(quelltext, daten):
    ...
    return ...

Umkehrung des Halteverhaltens

Wenn es eine Funktionsdefinition (in Python) für die Funktion istHaltend gibt, dann lässt sich die etwas seltsame Funktion umkehrHalteverhalten erstellen:

def umkehrHalteverhalten (quelltext):

    def istHaltend(quelltext, daten):
        ...
        return ...

    if istHaltend(quelltext, quelltext) == True:
        while True:
            pass
    else:
        return False

Diese Funktion hat das folgende Verhalten:

Verarbeitung des eigenen Quelltextes

Wir lassen jetzt die Funktion umkehrHalteverhalten ihren eigenen Quelltext verarbeiten.

# Funktionsdefinitionen

def umkehrHalteerhalten(quelltext):

    def istHaltend(quelltext, daten):
        ...
        return ...

    if istHaltend(quelltext, quelltext) == True:
        while True:
            pass
    else:
        return False

# Funktionsaufruf

quelltextUmkehrHalteverhalten = """
def umkehrHalteverhalten(quelltext):

    def istHaltend(quelltext, daten):
        ...
        return ...

    if istHaltend(quelltext, quelltext) == True:
        while True:
            pass
    else:
        return False
"""
print(umkehrHalteverhalten(quelltextUmkehrHalteverhalten))

Welches Ergebnis liefert die Funktion umkehrHalteverhalten in diesem speziellen Fall? Die Antwort hierauf ist höchst seltsam.

Fall 1: Wir nehmen an, dass die Funktion umkehrHalteverhalten bei der Verarbeitung des eigenen Quelltextes hält. Dann liefert istHaltend(quelltextUmkehrHalteverhalten, quelltextUmkehrHalteverhalten) den Wert True. Die Funktion umkehrHalteverhalten gerät dann aber in eine Endlosschleife - und hält folglich nicht.

Fall 2: Wir nehmen an, dass die Funktion umkehrHalteverhalten bei der Verarbeitung des eigenen Quelltextes nicht hält. Dann liefert istHaltend(quelltextUmkehrHalteverhalten, quelltextUmkehrHalteverhalten) den Wert False. Die Funktion umkehrHalteverhalten liefert dann ebenfalls das Ergebnis False. Das bedeutet aber, dass die Funktion hält - im Gegensatz zur gemachten Annahme.

In beiden Fällen verwickelt man sich in Widersprüche.

Auflösung des Widerspruchs

Wir sind von der Annahme ausgegangen, dass es eine Funktionsdefinition für die Funktion istHaltend gibt. Aufbauend auf diese Annahme haben wir eine etwas merkwürdige Funktion umkehrHalteverhalten entwickelt. Bei der Analyse des Verhaltens dieser merkwürdigen Funktion verwickelt man sich in Widersprüche. Die Ursache der Widersprüche kann nur in der getroffen Annahme liegen. Die Annahme, dass es eine Funktionsdefinition für die Funktion istHaltend gibt, muss daher falsch sein.