Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Rekursive Funktionenschar - als ganzes rekursiv?
Autor
Kein bestimmter Bereich J Rekursive Funktionenschar - als ganzes rekursiv?
Pwin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.12.2018
Mitteilungen: 24
  Themenstart: 2020-03-22

Hallo, wir haben rekursive Funktionen als die totalen partiell rekursiven Funktionen definiert. Die partiell rekursiven sind der Abschluss von Null-, Nachfolger- und Projektionsfunktionen (beliebiger Stelligkeit) unter Verknüpfung, primitiver Rekursion und Minimierung. Ich stehe bei folgender Aufgabenstellung an: Für jedes x \el\ \IN sei f_x: \IN->\IN und sei f: \IN^2->\IN, (x,y)|->f_x(y). Sind folgende Aussagen wahr? 1) Alle f_x rekursiv => f rekursiv 2) f rekursiv => alle f_x rekursiv. Meine Vermutung ist, dass 2) wahr ist und 1) falsch. Wenn f rekursiv ist, ist f_x als "Teil" in meinen Augen auch rekursiv, man muss nur das x "herausfinden". Weiß aber nicht, wie ich das formal zeigen soll. Und bei 1) finde ich kein Gegenbeispiel. Kann mir jemand helfen bitte?


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2030
  Beitrag No.1, eingetragen 2020-03-22

Hallo Pwin, falls ihr das noch nicht in der Vorlesung getan habt, überleg Dir zuerst, dass auch jede $k$-stellige konstante Funktion $c^k_t:\mathbb{N}^k\to\mathbb{N}, (x_1, \hdots, x_k) \mapsto t$ mit einem festen $t\in \mathbb{N}$ (primitiv) rekursiv ist. Außerdem ist nach Definition jede $k$-stellige Projektionsfunktion $\pi^k_i$ auf das $i$-te Argument primitiv rekursiv. Die Funktion $f_x$ lässt sich dann ausdrücken als $f_x(y)= f(c^1_x(y), \pi^1_1(y))$. Wegen des Abschlusses der partiell rekursiven Funktionen gegen Kompositionen und der Rekursivität von $f$ ist sie damit selbst partiell rekursiv. Weil mit $f$ erst recht auch $f_x$ total ist, ist sie also sogar total rekursiv. Deine Vermutung stimmte also. Allerdings trifft die Formulierung, man müsse das x "rausfinden", nicht den Kern der Sache. Im Gegenteil wird das $x$ ja nun als Konstante betrachtet, die man in der Definition mitverwenden darf. Deine Vermutung für Teil a) stimmt ebenfalls. Hier kannst du am einfachsten wieder benutzen, dass die konstante 0- und die konstante 1-Funktion total rekursiv sind. Wenn du $f$ so definierst, dass jedes $f_x$ eine dieser beiden konstanten Funktionen ist, dann ist jedes $f_x$ total rekursiv. Versuche nun, sicherzustellen, dass $f$ selbst nicht rekursiv sein kann, indem du das Halteproblem bei der Definition von $f$ "hineinkodierst". Viele Grüße und viel Erfolg Thorsten


   Profil
Pwin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.12.2018
Mitteilungen: 24
  Beitrag No.2, vom Themenstarter, eingetragen 2020-03-22

Ok vielen Dank, das ist eine große Hilfe! Der zweite Teil ist dann eh einfach. Beim ersten hätte ich jetzt so argumentiert: Sei C die Menge aller Operatorterme e, die partielle Funktionen mit Stelligkeit 1, \phi_e, beschreiben. C ist abzählbar; sei \psi: \IN->C eine rekursive Bijektion (bin mir nicht sicher ob es eine rekursive gibt?). Definiere f_x(y) := \chi_K(\psi(x)), wobei K := menge(e \el\ C | \phi_e(e) ist definiert). Jedes f_x ist konstant 0 oder 1 und somit rekursiv. Wäre f jedoch rekursiv, so wäre die Diagonale des Halteproblems entscheidbar, was nicht der Fall ist. ---- Bei dieser Argumentation müsste eben auch die Umkehrfunktion von \psi rekursiv sein, da man sonst \chi_K nicht aus f zurückgewinnen kann. Hoffe, das ist aber der Fall. LG


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2030
  Beitrag No.3, eingetragen 2020-03-22

Hallo Pwin, ich kenne eure Definitionen ja nicht, aber wenn dein C keine Menge natürlicher Zahlen ist, kann man dann eigentlich davon Sprechen, dass dein $\psi$ rekursiv ist? Wenn ja, und wenn ihr das Halteproblem tatsächlich als eine Menge von Operatortermen, und nicht als Menge von natürlichen Zahlen (die diese Operatorterme in nachvollziehbarer Form kodieren) definiert habt, dann kann man das wohl so stehenlassen. Die Umkehrfunktion einer totalen bijektiven Funktion ist übrigens allgemein immer total rekursiv (versuch das zu beweisen). Du solltest auch noch etwas formal begründen, warum die Diagonale des Halteproblems entscheidbar wäre, wenn $f$ rekursiv wäre. Viele Grüße Thorsten


   Profil
Pwin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.12.2018
Mitteilungen: 24
  Beitrag No.4, vom Themenstarter, eingetragen 2020-03-22

Ok danke, das habe ich schlampig hingeschrieben, C enthält die Codierungen der Operatorterme, ist also eine Teilmenge der natürlichen Zahlen. Die Diagonale wäre entscheidbar wegen \chi_K(x) = f(\psi^(-1)(x),0) = Cn[f, Cn[\psi^(-1), p_1^1], 0]. Die Umkehrfunktion einer Bijektion ist wohl wegen f^(-1)(y) = \mue x (\chi_(=) (f(x), y) rekursiv (du meinst wohl, die Umkehrfunktion einer rekursiven Funktion, nicht einer beliebigen Bijektion?). LG


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2030
  Beitrag No.5, eingetragen 2020-03-22

Hallo Pwin, $\psi^{-1}(x)$ ist aber gar nicht definiert, wenn $x$ nicht in $C$ liegt. Da $C$ entscheidbar ist, könntest du diesen Fall durch eine Fallunterscheidung abdecken (wenn ihr schon gezeigt habt, dass die rekursiven Funktionen gegen solche Fallunterscheidungen abgeschlossen sind). Die einfachere Lösung ist aber, auf das $\psi$ komplett zu verzichten. Dann funktioniert der Beweis so wie von dir beabsichtigt. Viele Grüße Thorsten


   Profil
Pwin hat die Antworten auf ihre/seine Frage gesehen.
Pwin hat selbst das Ok-Häkchen gesetzt.
Pwin wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]