Ein seltsames Halteanalyseprogramm
Ein neuer Weg zur Bearbeitung des Halteproblems
Zur Erinnerung: 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.
Die Entwicklung einer geeigneten Funktionsdefinition für die Funktion istHaltend
scheint
schwierig - vielleicht sogar unmöglich - zu sein.
Wir schlagen daher hier einen anderen Weg ein.
Wir nehmen an, wir hätten eine geeignete Funktionsdefinition für die Funktion istHaltend
:
def istHaltend(quelltext, daten):
...
return ...
Ziel ist es jetzt, Konsequenzen aus dieser Annahme zu ziehen.
Halteverhalten bei der Verarbeitung des eigenen Quelltextes
Mit der Funktion istHaltend
kann man u.a. testen, wie sich ein Programm
verhält, wenn es den eigenen Quelltext analysiert.
# Funktionsdefinitionen
def istHaltend(quelltext, daten):
...
return ...
# Funktionsaufruf
quelltextEnthaeltWhile = """
def enthaeltWhile ( quelltext ) :
tokenliste = quelltext . split ( )
gefunden = False
for token in tokenliste :
if token == 'while' :
gefunden = True
return gefunden
"""
print(istHaltend(quelltextEnthaeltWhile, quelltextEnthaeltWhile))
Aufgabe 1
(a) Warum müsste hier der Wert True
ausgegeben werden?
(b) Konstruiere ein weiteres Beispiel, bei dem der Wert True
ausgegeben wird.
(c) Konstruiere einen Beispielquelltext, bei dem der Wert False
ausgegeben wird.
Ein Programm zur Umkehr des Halteverhaltens
Die Funktion umkehrHalteverhalten
ist etwas seltsam konzipiert.
def umkehrHalteverhalten (quelltext):
def istHaltend(quelltext, daten):
...
return ...
if istHaltend(quelltext, quelltext) == True:
while True:
pass
else:
return False
Aufgabe 2
(a) Welches Ergebnis erwartest du beim folgenden Beispielaufruf?
# Funktionsdefinitionen
def umkehrHalteverhalten(quelltext):
def istHaltend(quelltext, daten):
...
return ...
if istHaltend(quelltext, quelltext) == True:
while True:
pass
else:
return False
# Funktionsaufruf
quelltextEnthaeltWhile = """
def enthaeltWhile ( quelltext ) :
tokenliste = quelltext . split ( )
gefunden = False
for token in tokenliste :
if token == 'while' :
gefunden = True
return gefunden
"""
print(umkehrHalteverhalten(quelltextEnthaeltWhile))
(b) Welches Ergebnis erwartest du hier?
# Funktionsdefinitionen
def umkehrHalteverhalten(quelltext):
def istHaltend(quelltext, daten):
...
return ...
if istHaltend(quelltext, quelltext) == True:
while True:
pass
else:
return False
# Funktionsaufruf
quelltextLoop = """
def loop (quelltext):
while True:
pass
return True
"""
print(umkehrHalteverhalten(quelltextLoop))
(c) Und welches Ergebnis ergibt sich hier?
# Funktionsdefinitionen
def umkehrHalteverhalten(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))