Autor	Nachricht
Artur	Verfasst am: 01. Nov 2024 20:59    Titel: (habe gesehen, dass das Latex nicht gerendert wurde, noch ein Versuch:) Angenommen, es gibt eine totale berechenbare Funktion , die für zwei Programme und entscheidet, ob sie semantisch äquivalent ( ) sind: Rekursionssatz von Kleene: Für jede partiell 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	Verfasst am: 01. Nov 2024 15:29    Titel: Semantische Äquivalenz vs. Rekursionssatz 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!)

Powered by phpBB © 2001, 2005 phpBB Group