Menge der berechenbaren Funktionen rekursiv aufzählbar?
-
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.
-
Bashar schrieb:
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.
Es ist nicht meine Absicht Postings verzerrt darzustellen. Mir geht es um den Sachverhalt an sich. Natürlich beinhaltet die Aufgabenstellung an dieser Stelle keine konkrete Kodierung. Offensichtlich gibt es aber jede Menge unsinnige Kodierungen, die selbst einfachste Problem unlösbar schwierig machen.
Meine Frage war auch durchaus ernst gemeint, wo liegt der himmelweite Unterschied zwischen den beiden Situationen. Wenn ich mir bei Zahlen keine Gedanken über die Kodierung mache, warum dann bei berechenbaren Funktionen? Und mit "mir" meine ich an dieser Stelle tatsächlich mich selbst. Das Argument, dass das halt bei dem einen gefühlt wichtig ist und bei dem anderen eben nicht, kann ich nicht wirklich zählen lassen (mehr habe ich dazu momentan nach kurzem Überlegen aber auch nicht zu bieten). Insofern bin ich durchaus an Deiner Meinung zu dem Thema interessiert. Es tut mir leid, wenn mein Posting vielleicht etwas schroff gewirkt hat, das war nicht beabsichtigt. Ich habe leider im Moment nicht so viel Zeit, wie ich für sowas gerne hätte.
edit: welche gebräuchlichen Kodierungen für berechenbare Funktionen fallen euch denn noch so ein? Die Church-Turing-These erwähnt explizit Turingmaschinen, while-Programme etc. gehen natürlich genauso. Was gibts noch? -- Wertetabellen funktionieren, wie user-l ausgeführt hat, ja nicht.
-
Herr Beutelspacher hat mal einen sehr schönen Satz formuliert: "Mathematik ist Mut zur Einfachheit".