Antwort schreiben

Registrieren

FAQ

Suchen

Foren-Übersicht -> Sonstiges

Antwort schreiben

Benutzername

(du bist nicht eingeloggt!)

Titel

Nachrichtentext

Smilies





Weitere Smilies ansehen

Schriftfarbe: Schriftgröße:

Tags schließen

Schreibt eure Formeln hier im Board am besten mit Latex!
So gehts: Latex-Kurzbeschreibung | Formeleditor

[quote="Artur"][b]Meine Frage:[/b]
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!)

[b]Meine Ideen:[/b]
Angenommen, es gibt eine totale berechenbare Funktion [latex]f[/latex] , die für zwei Programme [latex]p[/latex] und [latex]q[/latex]  entscheidet, ob sie semantisch äquivalent ( [latex]\equiv[/latex] ) sind:
[latex]f(p, q) = \begin{cases} 1, & \text{wenn } p \equiv q
   0, & \text{wenn } p \not\equiv q
   \end{cases}
[/latex]

Kann man das so machen oder ist das zu einfach?

Danke!

Rekursionssatz von Kleene: Für jede berechenbare Funktion [latex]g[/latex] existiert ein Programm [latex]e[/latex], welches die Funktion [latex]\varphi_e[/latex] berechnet, mit:
   [latex]
   \varphi_e(x) = g(e, x)
   [/latex]

Sei [latex] g [/latex] definiert durch:

[latex]g(p, q) = \begin{cases} \varphi_q(q) + 1, & \text{falls } f(p, q) = 1 \\\varphi_q(q), & \text{falls } f(p, q) = 0
   \end{cases}[/latex]

Gem. dem obigen Rekursionssatz existiert ein Programm [latex] e [/latex], so dass:
   [latex]
   \varphi_e(q) = g(e, q)
   [/latex]

Offenbar gilt [latex] f(e,e) = 1 [/latex]. Dann gilt aber mit Rekursionssatz und Definition von [latex] g [/latex]:

[latex] \varphi_e(e) = g(e,e) = \varphi_e(e) + 1[/latex] (Widerspruch!)[/quote]

Optionen
HTML ist aus
BBCode ist an
Smilies sind an

	BBCode in diesem Beitrag deaktivieren
	Smilies in diesem Beitrag deaktivieren

Spamschutz
Text aus Bild eingeben

Alle Zeiten sind GMT + 1 Stunde

Thema-Überblick