bereche. partieller Funktionen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Halli Hallo!
Ich habe da ein Problem mit der folgenden Aufgabe:
Zeigen Sie das die partielle funktion
$f: A [mm] \subseteq \IN \to \IN$
[/mm]
berechenbar ist.
[mm]f\left(n\right) := \begin{cases}\varphi_n \left(n\right)+1, & \mbox{für } n \in \mathrm{Def}\left(\varphi_n\right) \mbox{} \\ \mathrm{div}, & \mbox{für } n \notin \mathrm{Def}(\varphi_n) \mbox{} \end{cases}[/mm]
Die beiden geschweiften Klammern sollen eine grosse darstellen.
So.
Als erstes verstehe ich nicht was ich da machen muss. Irgendwie ist die Definition schon unklar.
Also eine Teilmenge von [mm] $\IN$ [/mm] abgebildet auf [mm] $\IN$
[/mm]
für die [mm] $\varphi_n(n)+1$ [/mm] ist falls $n [mm] \in \mathrm{Def}\left(\varphi_n\right)$.
[/mm]
Erste Frage: Was ist denn hier mein Def? Das hier ?:
$A [mm] \subseteq \IN \to \IN$
[/mm]
Und was ist [mm] $\varphi_n$?
[/mm]
Wenn $n [mm] \notin \mathrm{Def}\left(\varphi_n\right)$ [/mm] dann ist es div.
Aber wie zeige ich das?
das es berechenbar oder nicht berechenbar ist???
Ich finde absolut keinen Ansatz.
Vielen Dank,
NIK
|
|
| |
|
Hallo,
bei der Funktion [mm] \varphi [/mm] handelt es sich vermutlich um eine universelle Funktion fuer die
Klasse der [mm] $\mu$-rekursiven [/mm] Funktionen, dafuer wird das Symbol zumindest typischerweise
in dem Kontext verwendet. Es ist also [mm] \varphi_n(x)=\varphi(n,x) [/mm] die n-te [mm] $\mu$-rekursive [/mm] Funktion
(die Numerierung ist dann nachweislich nicht injektiv).
Dann ist die Aufgabenstellung vermutlich so zu verstehen, dass gezeigt werden soll,
dass auch die Funktion
[mm] f(n)=\begin{cases}\varphi(n,n)+1 & \mbox{ für} \ \varphi(n,n) \ \mbox{definiert}\\ undef & \mbox{sonst}\end{cases}
[/mm]
[mm] $\mu$-rekursiv [/mm] ist (man koennte auf den ersten Blick das Gegenteil vermuten, da ja zur
Definition fon f die universelle Funktion (man sagt auch: Goedel-Numerierung) der
mu-rek. Funktionen verwendet wird.
Intuitiv ist es klar, dass f [mm] $\mu$-rekursiv [/mm] ist, da es sich um eine berechenbare (implementierbare) Berechnungsvorschrift handelt. Formal entsteht f aus der Funktion [mm] \varphi [/mm] (die vorher als [mm] $\mu$-rekursiv [/mm] nachgewiese wurde), der Addition und der konstanten
Funktion x |-> 1 durch Einsetzung.
Der Definitionsbereich von f ist nach Definition genau der von n -> [mm] \varphi(n,n),
[/mm]
also die Menge K, die als Halteproblem bekannt ist.
Viele Gruesse,
Mathias
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo Matiash!
Erst einmal Danke für Deine schnelle Antwort!
Leider ist unser Skript etwas kompliziert.
Die Goedel sache hab ich mir ebend angekuckt und es scheint plausibel.
Ich weiss jedoch immer noch nicht wie ich zeigen kann das es berechenbar ist. Das es berechenbar ist ist zwar klar, aber wie zeig ich das.
Inzwischen habe ich auch herausgefunden das mit phi die Standardnummerierung phi gemeint ist.
Gezeitg werden kann es wohl mit dem utm Theorem und folgendem Lemma:
Die wie folgt definierte Funktion h : \IN^3 \to \IN ist berechenbar.
1 + phi klein i (n) falls Standardkomplexität (groß phi ist das ) (n) existiert und groß phi i(n) <= t
h(i,n,t)= {
0 sonst.
Ich verstehe einfach nicht wie ich mit den Sachen zeigen kann das f berechenbar ist.
|
|
|
| |
|
Hallo nochmal,
zu Deiner Nachfrage: Es sollte doch klar sein, dass, wenn die Funktion [mm] \phi \mu-rekursiv
[/mm]
ist, dann auch die Funktion f [mm] \mu-rekursiv [/mm] ist (man sagt auch: berechenbar), denn sie
entsteht dann ja aus bereits als [mm] \mu-rekursiv [/mm] nachgewiesenen Funktionen durch
Einsetzen (Substitution).
Dann kann doch eigentlich fuer Dich nur noch unklar sein, warum die Funktion [mm] \phi
[/mm]
[mm] \mu-rekursiv [/mm] ist, oder genauer: warum es eine [mm] \mu-rekursive [/mm] Funktion [mm] \phi [/mm] gibt, so dass
die Menge der Funktionen [mm] \phi_n,n\in \IN [/mm] genau die Menge [mm] F_{\mu} [/mm] der [mm] \mu [/mm] - rekursiven
Funktionen ist.
Dies ist sozusagen Vorgeschichte zu der von Dir beschriebenen Aufgabenstellung.
Die Konstruktion einer solchen Funktion [mm] \phi [/mm] beruht darauf, [mm] \mu [/mm] - rekursive Funktionen
durch natuerliche Zahlen zu kodieren (''Goedelisierung''). Im Detail findet man die
Konstruktion einer solchen Funktion in jedem Buch ueber Berechenbarkeit. Die Kodierung wird entlang des Aufbaus von [mm] F_{\mu} [/mm] definiert: Die Grundfunktionen kodiert
man durch feste kleine Zahlen, Substitution etc. durch Tupel der Kodierungen der beteiligten Funktionen und einer festen Zahl fuer den Substitutionsoperator etc.
Dann muss man bei der Definition von [mm] \phi [/mm] nur darauf achten, dass diese Kodierungen
wieder richtig interpretiert werden.
Vielleicht ist Dir einfach nicht klar, was Berechenbarkeit heisst: Es ist -fuer Funktione-
lediglich ein Synonym fuer [mm] \mu-Rekursivitaet.
[/mm]
Hilft das weiter ?
Viele Gruesse,
Mathias
|
|
|
| |
|
Hallo,
bei der Funktion phi handelt es sich vermutlich um eine universelle Funktion fuer die
Klasse der mu-rekursiven Funktionen, dafuer wird das Symbol zumindest typischerweise
in dem Kontext verwendet. Es ist also [mm] phi_n(x)=phi(n,x) [/mm] die n-te mu-rekursive Funktion
(die Numerierung ist dann nachweislich nicht injektiv).
Dann ist die Aufgabenstellung vermutlich so zu verstehen, dass gezeigt werden soll,
dass auch die Funktion
f(n) = [mm] \begin{cases} phi(n,n) +1 & \mbox{ für phi(n,n) definiert}\\
undef & \mbox{sonst}
\end{cases}
[/mm]
mu-rekursiv ist (man koennte auf den ersten Blick das Gegenteil vermuten, da ja zur
Definition fon f die universelle Funktion (man sagt auch: Goedel-Numerierung) der
mu-rek. Funktionen verwendet wird.
Intuitiv ist es klar, dass f mu-rekursiv ist, da es sich um eine berechenbare (implementierbare) Berechnungsvorschrift handelt. Formal entsteht f aus der Funktion phi (die vorher als mu-rekursiv nachgewiese wurde), der Addition und der konstanten
Funktion x |-> 1 durch Einsetzung.
Der Definitionsbereich von f ist nach Definition genau der von n -> phi(n,n),
also die Menge K, die als Halteproblem bekannt ist.
Viele Gruesse,
Mathias
|
|
|
|
