Rekursionssatz und Semantische Äquivalenz

01.11.2024, 19:23	artur	Auf diesen Beitrag antworten »
Rekursionssatz und Semantische Äquivalenz 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. (verzeiht die Ungenauigkeiten, bin kein ausgebildeter Mathematiker o.ä., nur Interessierter) Meine Ideen: Angenommen, es gibt eine totale berechenbare Funktion $\begin{eqnarray} f \end{eqnarray}$ , die für zwei Programme $\begin{eqnarray} p \end{eqnarray}$ und $\begin{eqnarray} q \end{eqnarray}$ entscheidet, ob sie semantisch äquivalent ( $\begin{eqnarray} \equiv \end{eqnarray}$ ) sind: $\begin{eqnarray} f(p,q) = \begin{cases} 1, & \text{wenn } p \equiv q \\ 0, & \text{wenn } p \not\equiv q \end{cases} \end{eqnarray}$ Rekursionssatz von Kleene: Für jede partiell berechenbare Funktion $\begin{eqnarray} g \end{eqnarray}$ existiert ein Programm $\begin{eqnarray} e \end{eqnarray}$ , welches die Funktion $\begin{eqnarray} \varphi_e \end{eqnarray}$ berechnet, mit: $\begin{eqnarray} \varphi_e(x) = g(e, x) \end{eqnarray}$ Sei $\begin{eqnarray} g \end{eqnarray}$ definiert durch: $\begin{eqnarray} 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} \end{eqnarray}$ Gemäß dem obigen Rekursionssatz existiert ein Programm $\begin{eqnarray} e \end{eqnarray}$ , so dass: $\begin{eqnarray} \varphi_e(q) = g(e, q) \end{eqnarray}$ Offenbar gilt $\begin{eqnarray} f(e, e) = 1 \end{eqnarray}$ . Dann gilt aber mit Rekursionssatz und Definition von $\begin{eqnarray} g \end{eqnarray}$ : $\begin{eqnarray} \varphi_e(e) = g(e,e) = \varphi_e(e) + 1 \end{eqnarray}$ (Widerspruch!)
01.11.2024, 19:47	Elvis	Auf diesen Beitrag antworten »
Ich finde keinen Fehler, also akzeptiere ich den Beweis.
01.11.2024, 19:51	Artur	Auf diesen Beitrag antworten »
Danke dir! Habe mich grade nur gefragt, was wäre, wenn f etwas triviales entscheiden würde (z.B. ob 2 Programme die gleiche Länge hätten). Was wäre dann am Beweis falsch? Das würde doch nicht ernsthaft beweisen, dass so ein f nicht existiert...
02.11.2024, 09:23	Elvis	Auf diesen Beitrag antworten »
Kann es sein, dass du in deinen "Beweis" die Voraussetzung hinein geschummelt hast, dass g berechenbar ist? Weil g von f abhängt, ist g genau dann berechenbar, wenn f berechenbar ist. Dein Beweisversuch wird daher abgelehnt. Korrektur. Das führt auf den Widerspruch, dass f für berechenbare f nicht berechenbar ist.
02.11.2024, 09:40	Artur	Auf diesen Beitrag antworten »
Hi. Nein, das ist nicht der Grund. Der Rekusionssatz ist bereits für partiell berechenbare Funktionen definiert. Das Problem an dem "Beweis" ist, dass er keinen Widerspruch ableitet, sondern lediglich ableitet, dass der Fixpunkt e auf sich selbst nicht definiert ist (du kannst ein ähnliches g ganz ohne Bezug auf f definieren). Wie auch immer... Schade (sah hübsch aus) Danke!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »