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
<p>def istHaltend(quelltext, daten):<br />
...<br />
return ...</p>
<h1>Funktionsaufruf</h1>
<p>quelltextEnthaeltWhile = """<br />
def enthaeltWhile ( quelltext ) :<br />
tokenliste = quelltext . split ( )<br />
gefunden = False<br />
for token in tokenliste :<br />
if token == 'while' :<br />
gefunden = True<br />
return gefunden<br />
"""<br />
print(istHaltend(quelltextEnthaeltWhile, quelltextEnthaeltWhile))<br />

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):
<pre><code>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
<p>def umkehrHalteverhalten(quelltext):</p>
<pre><code>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
<p>def umkehrHalteverhalten(quelltext):</p>
<pre><code>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
<p>def umkehrHalteverhalten(quelltext):</p>
<pre><code>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))