Jedes Mal, wenn ich denke, ich verstehe, was der Satz von Rice bedeutet, finde ich ein Gegenbeispiel, um mich selbst zu verwirren. Vielleicht kann mir jemand sagen, wo ich falsch denke.
Nehmen wir eine nicht triviale Eigenschaft der Menge berechenbarer Funktionen, zum Beispiel. Offensichtlich, ist zählbar unendlich und es gibt auch eine zählbar unendliche Anzahl berechenbarer Funktionen, die nicht vorhanden sind .
Betrachten wir nun eine vollständige Programmiersprache über einen endlichen Satz von Anweisungen und die Menge der syntaktisch korrekten Programme mit . Wenn ich die Semantik meiner Sprache nach Belieben auswählen kann, kann ich die Programme auch nach Belieben nummerieren. Daher sollte es möglich sein, eine Programmiersprache zu entwerfen, in der eine Teilmenge der Programme genau eine beliebige Teilmenge der berechenbaren Funktionen berechnet solange die Kardinalität übereinstimmt. Zum Beispiel lassenund jedes Programm Berechnen Sie eine Gesamtfunktion. Schon seitsollte eine solche Sprache existieren.
Jedoch, ist offensichtlich turing-berechenbar und seitdem Wir hätten also ein Programm, das über die nicht triviale Eigenschaft entscheidet , was nach dem Satz von Rice nicht möglich ist.
Wo ist der Fehler in meinem Abzug? Bedeutet dies, dass es keine Programmiersprache gibt, in der jedes palindromische Programm (oder vielmehr eine berechenbare Struktur) genau die Gesamtfunktionen (oder vielmehr einen Satz berechenbarer Funktionen) berechnet ? Das verwirrt mich wirklich.
quelle
Antworten:
Was Sie vergessen, ist, dass alle Zuordnungen, die Sie verwenden, berechenbar sein müssen. Wenn Sie angeben, dass übereinstimmende Kardinalitäten die Existenz einer Zuordnung sicherstellen, kann dies zutreffen, aber es ist unwahrscheinlich, dass die Zuordnung berechenbar ist, gerade weil dies zu einem Widerspruch zum Rice-Theorem führen würde. In der Berechenbarkeit (zumindest soweit ich weiß) ist alles entweder endlich oder zählbar unendlich. Das Vorhandensein von Zuordnungen ist also normalerweise kein Problem. Das Problem ist, ob es sich um eine berechenbare handelt.
Anders ausgedrückt, es gibt sicherlich eine Zuordnung (tatsächlich unzählige), die genau palindromische Wörter mit insgesamt berechenbaren Funktionen verknüpft. Aber angesichts eines solchen Palindromsw , die das Mapping einer Funktion zuordnet fw Es gibt keine Möglichkeit, eine solche Zuordnung tatsächlich zu verwenden, um das Ergebnis der Anwendung zu erhalten fw zu einem Argument. Durch die Zuordnung können Sie die Funktion nicht identifizieren oder damit rechnen. Ihre Sprache hat eine nicht berechenbare Semantik.
quelle
Für einige Funktionssätze funktioniert das; nicht für andere . Aber eine neue Programmiersprache ist eine neue Nummerierung einiger Programme, und darüber spricht der Satz von Rice nicht.
Für den Zweck des Satzes von Rice betrachten wir nur Gödel- Aufzählungen aller partiellen rekursiven Funktionen und geben dann nur etwas über Indexmengen an, dh Mengen aller Indizes in dieser Aufzählung von Funktionen in der gegebenen Menge.
Dies gilt nicht für alle Indexsätze. und das ist gut so, denn es gibt sicherlich viele entscheidbare Eigenschaften von Programmen. Siehe auch hier .
quelle
Nicht jede Aufzählung von Programmen ist "akzeptabel", da nicht jede Aufzählung es Ihnen ermöglichen würde, die dem Programm zugeordnete Funktion effektiv aus dem Index des Programms zu berechnen. Mit anderen Worten, Sie hätten keine universellen Maschinen (utm-Eigenschaft). Die zweite Eigenschaft, die normalerweise erforderlich ist, um die Aufzählung zu "akzeptieren", ist die Eigenschaft smn: Sie müssen in der Lage sein, den Index von Programminstanzen auf einheitliche und effektive Weise zu berechnen .
Es ist möglich zu beweisen (Rogers Äquivalenzsatz), dass jedes Aufzählungspaar, das utm und smn genießt, rekursiv isomorph ist, dh, Sie haben eine effektive Möglichkeit, Programme zwischen den beiden Aufzählungen zu übersetzen. Dies macht Ihre Theorie von der Aufzählung unabhängig.
Dies reicht bereits aus, um die Relevanz von utm und smn, den beiden Grundsätzen des "abstrakten" Ansatzes zur Berechenbarkeit, hervorzuheben.
Rogers Theorem wird in seinem Buch Theorie der rekursiven Funktionen und der effektiven Berechenbarkeit (Übung 2-10, Seite 41) als Übung (sic!) Dargestellt . Aber der Beweis ist in der Tat nicht sehr schwer.
quelle
Ich fand dieses interessante Papier von Udi Boker und Nachum Dershowitz, das unter anderem das Problem anspricht, das ich hatte. In der Einleitung heißt es, dass (Hervorhebung von mir)
und weiter
das erklärt, was babou als "berechenbare Semantik" bezeichnet. Das Papier enthält auch dieses Zitat von Michael Rescorla:
Den Autoren zufolge beruht die gemeinsame formale Definition einer berechenbaren Funktion auf der informellen Intuition darüber, was Berechenbarkeit bedeutet, was erklärt, was mich an Gödel-Nummerierungen verwirrt hat.
quelle