Semantische Äquivalenz vs. Rekursionssatz

Artur · Gast

Meine Frage:
Hi zusammen.

Ich habe im Wikipedia Artikel zum Rekursionssatz einen recht überschaubaren Beweis zur Unentscheidbarkeit des Halteproblems gefunden (https://de.wikipedia.org/wiki/Rekursionssatz#Anwendungen).

Habe nun einen analogen Beweis zur Unentscheidbarkeit der Semantischen Äquivalenz zweier Programme versucht und würde nun gern hier eine Meinung einholen, ob der korrekt ist.

(Ich weiß, das ist ein Physikforum, aber hier wurde mir mal kompetent geholfen. Danke!)

Meine Ideen:
Angenommen, es gibt eine totale berechenbare Funktion

, die für zwei Programme

und

entscheidet, ob sie semantisch äquivalent (

) sind:

Kann man das so machen oder ist das zu einfach?

Danke!

Rekursionssatz von Kleene: Für jede berechenbare Funktion

existiert ein Programm

, welches die Funktion

berechnet, mit:

Sei

definiert durch:

Gem. dem obigen Rekursionssatz existiert ein Programm

, so dass:

Offenbar gilt

. Dann gilt aber mit Rekursionssatz und Definition von

:

(Widerspruch!)

Artur · Gast

(habe gesehen, dass das Latex nicht gerendert wurde, noch ein Versuch:)

Angenommen, es gibt eine totale berechenbare Funktion