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.