Menge der berechenbaren Funktionen rekursiv aufzählbar?
-
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".
-
Jester schrieb:
\mu$-rekursive Funktionen$ Registermaschinen Die Situation mit der Abhängigkeit von der Codierung ist hier ungefähr so, wie wenn man zwei Nullstellen von sin(x) angeben soll - darf man in der Ausgabecodierung die Zahl pi als Symbol benutzen, ist die Sache trivial, in der Ausgabecodierung als Binärstrings ist es unmöglich.edit: welche gebräuchlichen Kodierungen für berechenbare Funktionen fallen euch denn noch so ein?
-
Informatikker, Der schrieb:
"Mathematik ist Mut zur Einfachheit".
Mathematik ist die Wissenschaft, bei der man nicht weiß wovon man redet, noch ob das, was man sagt, den Tatsachen entspricht. :p
-
u_ser-l schrieb:
Die Situation mit der Abhängigkeit von der Codierung ist hier ungefähr so, wie wenn man zwei Nullstellen von sin(x) angeben soll - darf man in der Ausgabecodierung die Zahl pi als Symbol benutzen, ist die Sache trivial, in der Ausgabecodierung als Binärstrings ist es unmöglich.
Ja, mein Punkt war ja, dass man bei beliebig fieser Kodierung auch einfachste Probleme nicht mehr in den Griff bekommt.
Eine weitere Möglichkeit zum Umgang mit reellen Zahlen (zumindest einer größeren Teilmenge davon) besteht darin eine verallgemeinerte Turingmaschine (nämlich eine, die endlos läuft) zurückzugeben, die die Stellen der Lösung nacheinander ab einer bestimmten Stelle auf das Band schreibt.
-
Jester, wenn man nach einem Entscheidungsalgorithmus fragt, der Elemente einer Menge M von einem Rest-Universum U\M trennen kann, muss man außer M auch U kennen, schon allein, weil es die Allmenge nicht gibt. Normalerweise ist U = IN oder Σ*, und aus dem Kontext geht hervor, was gemeint ist. Den Luxus haben wir hier nicht, da die Menge der berechenbaren Funktionen keine Teilmenge einer dieser Mengen ist. Hier schon eine Codierung in Form von Turing-Maschinen oder anderen äquivalenten Darstellungen vorzunehmen, hieße, das Ergebnis vorwegzunehmen.
Du setzt einfach U = M und nennst das eine vernünftige Annahme. Kann man machen, muss man aber nicht. Was wären größere nützliche Universen? Mir fällt da eine prädikatenlogische Formulierung ein, da weiß ich (hoffe ich) wenigstens, dass ich definitiv nicht-berechenbare Funktionen darstellen kann. Besonders fies kommt mir das nicht vor, abgesehen davon, dass das Problem dann nicht mehr lösbar ist. Vielleicht kennst du aber eine weniger fiese Codierung einer Klasse von Funktionen, die über die berechenbaren Funktionen hinausgeht?
Das alles lässt noch außer Acht, dass die "Codierung" berechenbarer Funktionen durch Turing-Maschinen keine ist, da man im Allgemeinen die Semantik einer Turing-Maschine nicht identifizieren kann. Es ist also schon allein aufgrund dessen ein ziemlicher Sprung, die Frage nach der rekursiven Aufzählbarkeit der berechenbaren Funktionen als Frage nach der rekursiven Aufzählbarkeit der Turing-Maschinen aufzufassen.
-
Jester schrieb:
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?
Mit Zahl meine ich normalerweise eine natürliche Zahl. Das kannst man kodieren. Mit Funktion meint ich normalerweise in diesem Kontext etwas von N nach N. Das kannst man nicht kodieren, da es überabzählbar ist. Da ist der Unterschied.
Eine Menge ist rekursiv aufzählbar wenn sie das Bild einer berechenbaren Funktion ist. Funktionen vom Typ f:N -> {N->N} können aber nicht berechenbar sein, da die Bildmenge nicht abzählbar ist und somit die Elemente nicht auf das Band einer TM passen. (Bitte beachte, dass f(N)≠{N->N}. Wenn man die Bildmenge auf f(N) einschränkt, dann wird sie abzählbar.)
Wenn man immer die Kodierung implizit frei wählen kann (was für die Identifikation N <-> f(N) notwendig ist), dann ist, so weit ich das einschätzen kann, abzählbar und rekursiv abzählbar das selbe. Man packt einfach den nicht berechenbaren Teil in die Definition der Kodierung und braucht diesen somit nie auszuführen.
Sei g:N -> Foo eine nicht unbedingt berechenbare bijektive Funktion. Foo ist offensichtlich abzählbar. Mit der Kodierung g(0), g(1), g(2), g(3), ... auch rekursiv abzählbar. (Ich identifiziere da n mit g(n) ohne g auszurechnen.)
Da ich zu jeder abzählbaren Menge Foo ein solches g finde, folgt dass: Zu jeder abzählbaren Menge Foo gibt es eine Kodierung bezüglich derer Foo rekursiv abzählbar ist.
EDIT: Was ich damit sagen will, ist dass man seine Kodierung festlegen muss, weil einem sonst selbst die elementarsten Begriffe kaputt gehen.
PS: Zugegeben, das ist Definitionsreiterei in Reinform.
-
Ben04 schrieb:
Eine Menge ist rekursiv aufzählbar wenn sie das Bild einer berechenbaren Funktion ist. Funktionen vom Typ f:N -> {N->N} können aber nicht berechenbar sein, da die Bildmenge nicht abzählbar ist und somit die Elemente nicht auf das Band einer TM passen.
"alle" geht nicht, klar, aber es sollen ja nicht alle Funktionen, sondern nur die berechenbaren aufgezählt werden. Und Turingprogramme gibt es abzählbar viele.
Funktionen N -> { N -> N} sind nicht per se unberechenbar - da man jede Funktion f: N -> {N->N} als Funktion g: N x N -> N darstellen kann: g(x,y) := f(x)(y)
weiter kann man jede Funktion N x N -> N als Funktion N -> N codieren, etwa, indem man eines der üblichen Abzählverfahren für N x N ~ N vorschaltet.
-
Ben04 schrieb:
Mit Zahl meine ich normalerweise eine natürliche Zahl. Das kannst man kodieren. Mit Funktion meint ich normalerweise in diesem Kontext etwas von N nach N. Das kannst man nicht kodieren, da es überabzählbar ist. Da ist der Unterschied.
Das sehe ich nicht so. Wir sprachen nicht von Funktionen sondern von berechenbaren Funktionen, die kann man kodieren. Wieso muß ich die Menge aller Funktionen in betracht ziehen, wenn ich die berechenbaren Funktionen anschauen möchte, aber du darfst wenn Du natürliche Zahlen anschaust die reellen Zahlen außer betracht lassen?
Das Hauptproblem liegt wohl daran, dass es keine Definition für den Begriff "berechenbare Funktion" gibt. Das was dem am nächsten kommt ist die Church-Turing-These und da kommen dann die Turingmaschinen ins Spiel.