Menge der berechenbaren Funktionen rekursiv aufzählbar?
-
Hallo!
Ist die Menge der berechenbaren Funktionen (R) rekursiv aufzählbar?
Ich meine ja, denn:
Zu jeder berechenbaren Funktion gibt es ja eine Turing-Maschine, die diese berechnet. Eine Turing-Maschine kann man bekanntlich durch eine Zahl kodieren. Meine aufzählende Funktion bekommt nun eine Nummer als Eingabe, interpretiert diese Nummer als Kodierung einer Turing-Maschine (falls es keine gültige Kodierung ist, liefern wir einfach eine Turing-Maschine, die niemals anhält) und liefert deren berechnete Funktion zurück.
Stimmt das so?
-
Ja, das sollte so stimmen.
-
Ich habe da so meine Zweifel. Was heißt das, eine Funktion zurückliefern?
Rekursive Aufzählbarkeit heißt m.W. auch semi-entscheidbarkeit, aber mir fällt kein Algorithmus ein, der anhält, wenn er eine berechenbare Funktion als Eingabe vorliegen hat.
-
Bashar schrieb:
Ich habe da so meine Zweifel. Was heißt das, eine Funktion zurückliefern?
Naja, die Turing-Maschine zurückliefern, welche diese Funktion berechnet.
Bashar schrieb:
Rekursive Aufzählbarkeit heißt m.W. auch semi-entscheidbarkeit, aber mir fällt kein Algorithmus ein, der anhält, wenn er eine berechenbare Funktion als Eingabe vorliegen hat.
Wenn die Eingabe in Form einer Turing-Maschine erfolgt, muss man einfach nur immer "Ja" sagen.
-
Kuwe schrieb:
Bashar schrieb:
Ich habe da so meine Zweifel. Was heißt das, eine Funktion zurückliefern?
Naja, die Turing-Maschine zurückliefern, welche diese Funktion berechnet.
Eine Turing-Maschine ist aber nicht dasselbe wie eine berechenbare Funktion. Es gibt nichtmal eine Bijektion dazwischen.
-
Aber zu jeder berechenbaren Funktion gibt es eine Turing-Maschine.
Und jede Turing-Maschine berechnet eine berechenbare Funktion!
-
edit: war blödsinn
-
an welche Art, die Eingabe (berechenbare Fkt.) zu codieren, wird hier denn gedacht?
Wertetabellen berechenbarer Fkt. sind ja i.a. unendlich, taugen also Eingabe nur bedingt, und die Entscheidung bei Repräsentation berechenbarer Fkt. durch Turing-Programme oder Gödelnummern wäre trivial, da ein Turing-Programm immer eine berechenbare Fkt. darstellt. - ?
-
Ja, das ist die Frage ...
Eigentlich kann man doch berechenbare Funktionen und Turing-Maschinen als "gleich" betrachten. Dann wäre es in der Tat trivial.
-
angenommen, Funktionen der Sorte N --> N wären in Form ihrer Wertetabelle dargestellt (jede Funktion N x N x ... x N --> N läßt sich ja codieren als N --> N, z.B. durch eine vorgeschaltete Bijektion N <--> N x N x ... x N)
Man könnte mit dieser Codierung alle berechenbaren Funktionen aufzählen, indem man erst von der 1. Funktion den 1. Funktionswert angibt, dann von der 2. Fkt. den 1. Funktionswert, dann von der 1. Funktion den 2. Funktionswert usw. (das übliche Abzähl.Verfahren, um bijektiv NxN <-> N abzubilden) ...
da es sich nur um berechenbare Funktionen handeln soll, wäre mit einer universellen TM jeder solche Funktionswert berechenbar und alle hintereinander aufs Ausgabeband zu schreiben.Es entstünde auf dem Ausgabeband eine Abzählung aller Funktionswerte aller berechenbaren Funktionen, und zwar in Form von ineinander verschränkten Wertetabellen:
f_0(0), f_1(0), f_0(1), f_2(0), f_1(1), f_0(2), f_0(3), f_1(2), f_2(1), f_3(0) ... usw.
- ?
-
aber ich sehe gerade: auch diese Methode hakt daran, daß eine Abzählung der berechenbaren Funktionen f_1, f_2, ... her muß - also bringt die Codierung in Form von Wertetabellen uns hier auch nicht weiter.
-
doch noch eine Idee:
Es soll also eine Turingmaschine M her, die alle berechenbaren Fkt. ausspuckt.
Falls die Ausgabe in Form von Turingprogrammen erfolgen soll, ist die Sache trivial - jedes Turingprogramm repräsentiert eine berechenbare Fkt.
Falls die Ausgabe in Form von Wertetabellen erfolgen soll, kann so etwas nie rekursiv aufzählbar sein, weil Wertetabellen von Funktionen N --> N i.a. unendlich lang sind, wogegen rekursive Aufzählbarkeit erfordert, daß die Wertetabellen nacheinander ausgespuckt werden, und zwar jeweils in endlicher Zeit.
- hängt scheint also IMHO davon abzuhängen, in welcher Codierung die berechenbaren Fkt. ausgegeben werden sollen.
-
Bashar schrieb:
Kuwe schrieb:
Bashar schrieb:
Ich habe da so meine Zweifel. Was heißt das, eine Funktion zurückliefern?
Naja, die Turing-Maschine zurückliefern, welche diese Funktion berechnet.
Eine Turing-Maschine ist aber nicht dasselbe wie eine berechenbare Funktion. Es gibt nichtmal eine Bijektion dazwischen.
Eine Bijektion nicht, aber die Arbeitshypothese ist doch meines wissens http://de.wikipedia.org/wiki/Church-Turing-These
Die besagt, dass die Abbildung Φ: {Turingmaschinen}-->{berechenbare Funktion}, M |--> Funktion, die von M berechnet wird surjektiv ist. Das besagt doch genau, dass die Menge der Turingmaschinen eine geeignete Kodierung für die Menge der berechenbaren Funktionen ist.
-
ja, aber wenn man die berechenbaren Funktionen aufzählt, indem man zugehörige Turingprogramme binär codiert und aufzählt:
1, 2, 3, 4, ....
(dabei natürlich alle Zahlen entfernt, die *nicht* formal korrekte Turingprogramme in der gewählten Binärcodierung sind)
wird die Aufgabe trivial, denn jedes Turingprogramm repräsentiert eine berechenbare Funktion.
-
Natürlich wird es dann trivial, das ist ja auch kein Wunder, wenn man die ganze Maschinerie mit Gödelnummern etc. reinsteckt. Das ist ja gerade der Sinn von solchen theoretischen Werkzeugen.
-
Das seh ich auch so. Dass es trivial ist kann nicht das Gegenargument sein. Es wird aber erst dadurch trivial, dass man sich die Codierung selbst aussucht. Von der Aufgabenstellung ist das nicht gedeckt. Lass die Eingabe beliebige prädikatenlogische Formulierungen sein, dann ist das schon nicht mehr ganz so trivial. Und auch nicht mehr möglich.
-
Schaut doch mal in diesem Skript auf Seite 103 (PDF Seite 111) bzw. die Leute mit weniger Hintergrund ab Seite 89 (PDF Seite 97).
Den Weg über die while-Programme finde ich schöner (sehen auch etwas übersichtlicher aus als eine TM)
-
Karlsruher Studi schrieb:
Schaut doch mal in diesem Skript auf Seite 103 (PDF Seite 111) bzw. die Leute mit weniger Hintergrund ab Seite 89 (PDF Seite 97).
Den Weg über die while-Programme finde ich schöner (sehen auch etwas übersichtlicher aus als eine TM)Hehe, cool unser altes Skript... das konnte ich alles mal.
-
Was soll uns das jetzt weiterhelfen?
-
Naja, ich denke man muß halt einfach ein paar vernünftige Annahmen machen. Sonst ist auch das Problem die Summe zweier Zahlen zu bestimmen nicht machbar, sagen wir jede Eingabe-Zahl wäre durch eine Turingmaschine kodiert, wenn die bei jeder Eingabe anhält, dann kodiert das die Eingabe 1 und sonst die 0. Warum ist es absurd anzunehmen, dass die Zahlen so fies kodiert sind und im Gegensatz dazu komisch, wenn ich annehme, dass ich meine Funktionen mit Gödelnummern kodieren darf?
-
Ich stimme dir zwar nicht zu, außerdem stellst du meine Position völlig verzerrt dar, aber du wirst wohl in Bezug auf "vernünftige" (sprich: was Informatik-Aufgaben-Ausdenker sich so denken) Annahmen mehr Erfahrung haben.