Das Halteproblem

Halten als Problem

Das Halteproblem ist ein zentrales Problem bei der Entwicklung von Algorithmen / Programmen: Wenn der Algorithmus / Quelltext des Programms gegeben ist, dann möchte man vorab wissen, ob der Algorithmus / das Programm bei gegebenen zu verarbeitenden Daten hält oder nicht.

def primzahl(n):
    if n == 1:
        prim = False
    else:
        prim = True
        i = 2
        while i < n:
            if n % i == 0:
                prim = False
    return prim

# Test
print(primzahl(71))

Im vorliegenden Beispiel sind der Quelltext einer Python-Funktionsdefinition (hier primzahl(n)) und ein von der Funktion zu verarbeitendes Datum (hier 71) gegeben. Das Problem besteht darin, aufgrund dieser Informationen - also ohne einen Testlauf durchzuführen - zu entscheiden, ob die gegebene Funktion bei der Verarbeitung der gegebenen Daten hält oder nicht.

Das Halteproblem

Gibt es ein Python-Programm (dargestellt als Python-Funktion), mit dessen Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann?

Die folgende Black-Box-Modellierung verdeutlicht die Problemsituation anhand eines konkreten Beispiels.

Übergeben werden eine Python-Funktionsdefinition sowie passende Daten. Die Funktion istHaltend soll dann überprüfen, ob die übergebene Funktion bei der Verarbeitung der übergebenen Daten hält oder nicht und das Ergebnis mit den Werten True oder False darstellen.

Wenn eine geeignete Funktionsdefinition für die Funktion istHaltend entwickelt ist, dann kann man mit dieser Funktion künftig Endlosschleifen verhindern.