Implikationen des Satzes von Rice

8

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 BeispielL={f:NN|f is a computable and total function}. Offensichtlich,L ist zählbar unendlich und es gibt auch eine zählbar unendliche Anzahl berechenbarer Funktionen, die nicht vorhanden sind L.

Betrachten wir nun eine vollständige Programmiersprache über einen endlichen Satz von Anweisungen Σ und die Menge der syntaktisch korrekten Programme PΣmit |P|=|N|. 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 lassenPpal={wΣ|w is a palindrome}und jedes Programm pPpalBerechnen Sie eine Gesamtfunktion. Schon seit|Ppal|=|L|sollte eine solche Sprache existieren.

Jedoch, isPalindrome(w) ist offensichtlich turing-berechenbar und seitdem isPalindrome(w)isTotal(w)Wir hätten also ein Programm, das über die nicht triviale Eigenschaft entscheidet L, 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.

Stefan Lutz
quelle
2
Aus all Ihren Kommentaren geht hervor, dass Sie nicht wirklich verstehen, was Berechenbarkeit ist. Überprüfen Sie die Definition der Berechenbarkeit. Stellen Sie sicher, dass Sie verstehen, was eine universelle Turing-Maschine ist und wie sie funktioniert. Stellen Sie sicher, dass Sie die Feinheiten von Aufzählungen verstehen, insbesondere Gödel-Aufzählungen (mit smn-Eigenschaft!). Der Satz von Rice ist sehr einfach, sobald die Grundlagen verstanden sind, aber er hat wenig Auswirkungen ... was auch immer Sie versuchen zu tun, ist mein Bauchgefühl.
Raphael

Antworten:

6

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 fwzu einem Argument. Durch die Zuordnung können Sie die Funktion nicht identifizieren oder damit rechnen. Ihre Sprache hat eine nicht berechenbare Semantik.

babou
quelle
Das macht Sinn. Bedeutet dies, dass der Satz von Rice nicht auf Sprachen mit nicht berechenbarer Semantik anwendbar ist, oder sind Sprachen mit nicht berechenbarer Semantik ein allgemein "verbotenes" Konzept (in dem Sinne, dass Ergebnisse aus der Berechenbarkeitstheorie im Allgemeinen nicht auf sie anwendbar sind)?
Stefan Lutz
1
Nicht berechenbare Semantik ist ein Ausdruck, den ich für die Intuition erfunden habe. Die Semantik wird normalerweise als Zuordnung von der Syntax (Gödel-Nummer lesen) zu einem Wertebereich (berechenbare Funktion lesen) definiert. Mein Ausdruck ist ein bisschen wie ein Oxymoron, weil eine Gödel-Nummerierung definiert werden soll, damit die zugehörigen Funktionen berechnet werden können. Ich habe versucht, eine Intuition für das zu geben, was Sie getan haben, was eigentlich falsch war. Sie sollten jedoch auf ein solches "Konzept" verzichten. Ja, nehmen Sie es als verbotenes Konzept, aus dem Grund, den Sie angeben.
Babou
Vielleicht gibt es hier ein anderes Missverständnis von meiner Seite, aber wenn ich die Semantik als eine Zusammensetzung von zwei Funktionen betrachte, das erste Mapping-Programm -> Gödel-Nummer und die zweite Gödel-Nummer -> berechenbare Funktion, wie Sie es beschrieben haben, dann die Gödel-Nummerierung könnte leicht seiner Definition folgen, aber das erste Mapping wäre berechenbar, wenn wir "berechenbare Semantik" hätten. Es mag immer noch ein nutzloses Konzept sein, aber es gibt kein Problem, es zu definieren, oder?
Stefan Lutz
Ich bin mir nicht sicher, wie ich dir antworten soll. Ihre Konstruktion macht mich unruhig. Für mich ist die Syntax des Programms in einer Sprache die Gödel-Nummer. Ich habe den Text nur als große Zahl in einem Zahlensystem gelesen, in dem alle meine Zeichen als Ziffern betrachtet werden. Ich betrachte also eine einzelne Zuordnung. Umgekehrt, wenn Sie mir eine Aufzählung der Funktionen geben, lese ich die Zahl als eine Art syntaktische Darstellung. Ich versuche nur zu vermeiden, einen Unterschied zu machen. Jetzt können Sie (berechenbare) intermediäre bijektive Zuordnungen von N nach N einführen, und es wird die Dinge nicht sehr ändern.
Babou
"Ich habe den Text nur als große Zahl in einem Zahlensystem gelesen, in dem alle meine Zeichen als Ziffern betrachtet werden." - Sie nehmen das Programm als Zeichenfolge als Eingabe und in eine Zahl, wobei jedes Programm genau einer Zahl entspricht ( = Bijektion). Außerdem geben Sie "ein Zahlenschema" an, sodass es nicht wirklich wichtig ist, wie genau diese Codierung funktioniert, solange sie berechenbar ist, nicht wahr? Tut mir leid, dass ich so hartnäckig bin, aber ich möchte das wirklich verstehen.
Stefan Lutz
2

Ich kann die Programme auch nach Belieben nummerieren, und so 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.

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 .

Raphael
quelle
1
"Eine neue Programmiersprache ist eine neue Nummerierung einiger Programme." - Wenn ich eine turing-vollständige Sprache betrachte, bedeutet das nicht, dass sie alle berechenbaren Funktionen nummeriert? Ich glaube jedenfalls, mein Missverständnis war, dass Gödel-Nummerierungen nicht selbst berechenbar sein müssen.
Stefan Lutz
@Skrjiban Jede richtige Programmiersprache ist eine Gödel-Aufzählung. (Um es klar, Gödel Nummerierungen sind notwendigerweise teilweise berechenbar.)
Raphael
2

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.

Andrea Asperti
quelle
1

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)

Was bedeutet es, wenn man sagt: „fist berechenbar “? Eine bedeutet höchstwahrscheinlich, dass es eine Turing-Maschine gibtM, so dass M berechnet funter Verwendung einer Zeichenfolgendarstellung der Domäne D. Aber was sind die erlaubten String-Darstellungen? Offensichtlich erlaubt eine beliebige Darstellung (jede Injektion vonD zu Σ) ist problematisch - es macht jede Entscheidungsfunktion „berechenbar“. Zum Beispiel kann sich die Stoppfunktion durch Permutieren der Domäne von Maschinencodes in die einfache Paritätsfunktion verwandeln [...]

und weiter

Ein anderer Ansatz besteht darin, nur "natürliche" oder "effektive" Darstellungen zuzulassen. Im Zusammenhang mit der Definition der Berechenbarkeit muss man jedoch auf einen vagen und undefinierten Begriff von „Natürlichkeit“ oder „Effektivität“ zurückgreifen, wodurch der eigentliche Zweck der Charakterisierung der Berechenbarkeit zunichte gemacht wird.

das erklärt, was babou als "berechenbare Semantik" bezeichnet. Das Papier enthält auch dieses Zitat von Michael Rescorla:

Ich werde vorschlagen, dass angebliche konzeptuelle Analysen, die die These der Kirche betreffen, eine subtile, aber unauslöschliche Zirkularität erzeugen: Sie charakterisieren den intuitiven Begriff der Berechenbarkeit, indem sie den intuitiven Begriff der Berechenbarkeit aufrufen. [...] Wir verleihen der Syntax eine primitive Semantik. Ich gehe davon aus, dass [...] wir verlangen müssen, dass die semantische Korrelation zwischen syntaktischen Entitäten und nicht-syntaktischen Entitäten selbst berechenbar ist. Dann beleuchtet die vorgeschlagene Analyse die Berechenbarkeit jedoch nicht kreisförmig.

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.

Stefan Lutz
quelle
1
Ist das nicht nah an dem, was ich in den letzten beiden Kommentaren erklärt habe, die ich dir geschickt habe? Ich habe festgestellt, dass es die CT-These ist, die die Definition der Berechenbarkeit liefert und somit der Grundstein für den Rest ist, obwohl sie nicht beweisbar ist. Ich hatte erwartet, dass Sie auf diese Kommentare antworten. - - - - - - Ein weiterer Punkt ist, dass ich nicht sehe, wie dies eine Antwort auf Ihre Frage sein kann. Bei Ihrer Frage ging es um einen Fehler in Ihrer Argumentation, und Sie waren nicht die Person, die diesen Fehler gefunden hat.
Babou
Es tut mir leid, wenn ich Sie beleidigt habe, Ihre Kommentare waren eindeutig hilfreich! Ich wollte darauf antworten, dass es einen berechenbaren Compiler aus der Sprache gibtL zu L sollte gleichbedeutend sein mit der Existenz eines berechenbaren Dolmetschers für L, was mich dazu brachte, darüber nachzudenken, was ein "berechenbarer" Interpreter sein würde, was mich dazu brachte, darüber nachzudenken, wie eine Gödel-Nummerierung "berechenbar" sein könnte, was mich zu dem obigen Artikel führte. Wenn Sie das schon gemeint haben, konnte ich es anscheinend nicht sehen.
Stefan Lutz
Aber Sie haben Recht, es hat es für mich klar verständlich gemacht, aber es beantwortet nicht die ursprüngliche Frage. Ich werde Ihre Antwort stattdessen als akzeptiert markieren.
Stefan Lutz
Nun, Sie haben sowohl Raphael als auch mir gedankt. Der Weg, den Menschen hier zu danken, besteht darin, für sie zu stimmen oder ihre Antwort zu akzeptieren. Sofern Sie nicht eine viel bessere Antwort auf die ursprüngliche Frage finden, sollten Sie positive Beiträge wertschätzen. Zumindest ist das mein Verständnis. Persönlich stimme ich niemals Menschen aus Protest gegen die vielen inkompetenten Menschen ab, die nachlässig ablehnen. Wissenschaft ist Dialog, nicht Abstimmung. Schauen Sie sich bezüglich der Definition von berechenbar die Kommentare an, die ich Ihnen gesendet habe. Das Konzept ist umständlich, weil es durch die Church-Turing-These definiert wird. Viel Glück.
Babou