Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Rekursive Funktionenschar - als ganzes rekursiv?
Druckversion
Druckversion
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: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

fed-Code einblenden

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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2010
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 <math>k</math>-stellige konstante Funktion <math>c^k_t:\mathbb{N}^k\to\mathbb{N}, (x_1, \hdots, x_k) \mapsto t</math> mit einem festen <math>t\in \mathbb{N}</math> (primitiv) rekursiv ist.

Außerdem ist nach Definition jede <math>k</math>-stellige Projektionsfunktion <math>\pi^k_i</math> auf das <math>i</math>-te Argument primitiv rekursiv.

Die Funktion <math>f_x</math> lässt sich dann ausdrücken als <math>f_x(y)= f(c^1_x(y), \pi^1_1(y))</math>. Wegen des Abschlusses der partiell rekursiven Funktionen gegen Kompositionen und der Rekursivität von <math>f</math> ist sie damit selbst partiell rekursiv. Weil mit <math>f</math> erst recht auch <math>f_x</math> 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 <math>x</math> 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 <math>f</math> so definierst, dass jedes <math>f_x</math> eine dieser beiden konstanten Funktionen ist, dann ist jedes <math>f_x</math> total rekursiv. Versuche nun, sicherzustellen, dass <math>f</math> selbst nicht rekursiv sein kann, indem du das Halteproblem bei der Definition von <math>f</math> "hineinkodierst".

Viele Grüße und viel Erfolg
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pwin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.12.2018
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2010
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 <math>\psi</math> 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 <math>f</math> rekursiv wäre.

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pwin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.12.2018
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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

fed-Code einblenden

Die Umkehrfunktion einer Bijektion ist wohl wegen

fed-Code einblenden

rekursiv (du meinst wohl, die Umkehrfunktion einer rekursiven Funktion, nicht einer beliebigen Bijektion?). LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2010
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-03-22


Hallo Pwin,

<math>\psi^{-1}(x)</math> ist aber gar nicht definiert, wenn <math>x</math> nicht in <math>C</math> liegt. Da <math>C</math> 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 <math>\psi</math> komplett zu verzichten. Dann funktioniert der Beweis so wie von dir beabsichtigt.

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
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.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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]