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 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 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))