Berechenbarkeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Die Funktion [mm] $f:\subseteq\IN^4\to\IN$ [/mm] sei definiert durch [mm] $f(i,j,x,y):=\phi_i^{\phi_j(x)}(y)$ [/mm] für alle $i,j,x,y [mm] \in \IN$. [/mm] Zeigen Sie, dass $f$ berechenbar ist. |
Hallo,
hat jemand einen Tipp, wie ich hier vorgehen muss? utm/smn-Theorem benutzen, Satz von Rogers? Ich hab irgendwie leider noch keine Idee.
Vielen Dank für die Hilfe.
Gruß, Stefan.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:12 Mi 02.12.2009 | | Autor: | felixf |
Hallo Stefan.
> Die Funktion [mm]f:\subseteq\IN^4\to\IN[/mm] sei definiert durch
> [mm]f(i,j,x,y):=\phi_i^{\phi_j(x)}(y)[/mm] für alle [mm]i,j,x,y \in \IN[/mm].
> Zeigen Sie, dass [mm]f[/mm] berechenbar ist.
Wenn du uns mitteilen wuerdest, was die ganzen [mm] $\phi$s [/mm] bedeuten sollen, und was genau ihr unter berechenbar (Turing-berechenbar?) versteht, koennten wir dir evtl. weiterhelfen.
> utm/smn-Theorem benutzen,
Was ist das?
> Satz von Rogers?
Meinst du den Aequivalenzsatz / das Isomorphietheorem (oder wie auch immer das noch so heisst)?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:03 Do 03.12.2009 | | Autor: | stefan00 |
Hallo Felix,
> Wenn du uns mitteilen wuerdest, was die ganzen [mm]\phi[/mm]s
> bedeuten sollen, und was genau ihr unter berechenbar
> (Turing-berechenbar?) versteht, koennten wir dir evtl.
> weiterhelfen.
ok, ich gebe mal die Definitionen an, die evtl. wichtig sein könnten:
Definition: Standardnummerierung [mm] $\phi$:
[/mm]
1. Es ist eine Ordnungsfunktion [mm] $a:{1,...,8}\to \Omega$ [/mm] definiert durch
[mm] $(a_1|a_2|...|a_8):=(1|B|(|)|:|,|R|L)$. [/mm] Es sei [mm] $\nu_\Omega$ [/mm] die aus a abgeleitete Standardnummerierung von [mm] $\Omega^\*$.
[/mm]
2. Es sei [mm] $\nu_P:\IN\toBP$ [/mm] definiert durch
[mm] $\nu_P(i)=\begin{cases} \nu_\Omega(i), & \mbox{falls } \nu_\Omega(i) \in \mbox{ BP} \\ "(:B,,)", & \mbox{sonst. } \end{cases}$
[/mm]
3. Es sei [mm] $\xi:BM\toP^{(1)}$ [/mm] definiert durch [mm] $\xi(M):=\iota^{-1}f_M\iota$ [/mm] (wobei [mm] $\iota:\IN\to\{1\}^\*,\iota(i):=1^i$).
[/mm]
4. Dann sei [mm] $\phi: \IN \to P^{(1)}$ [/mm] definiert durch [mm] $\phi_i:=\phi(i):=\xi\nu_M\nu_P(i)$ [/mm] für alle [mm] $i\in\IN$. [/mm] Die Nummerierung [mm] $\phi$ [/mm] heißt die Standardnummerierung von [mm] $P^{(1)}$.
[/mm]
>
> > utm/smn-Theorem benutzen,
>
> Was ist das?
Satz: utm-Theorem
Die Funktion [mm] $u_\phi:\subseteq\IN^2\to\IN$ [/mm] sei definiert durch [mm] $u_\phi(i,x):=\phi_i(x)$ [/mm] für alle $i,x [mm] \in \IN$.
[/mm]
Dann ist [mm] $u_\phi$ [/mm] berechenbar. (Man nennt [mm] $u_\phi$ [/mm] die universelle Funktion von [mm] $\phi$.)
[/mm]
Satz: smn–Theorem, Übersetzungslemma
Es sei $f [mm] \in P^{(2)}$ [/mm] eine beliebige zweistellige berechenbare Funktion. Dann gibt es eine total-rekursive Funktion $r [mm] \in R^{(1)}$ [/mm] mit [mm] $f(i,j)=\phi_{r(i)}(j)$ [/mm] für alle [mm] $i,j\in\IN$.
[/mm]
Ich hoffe, das hellt die Sache etwas auf.
Vielen Dank für die Hilfe, Gruß, Stefan.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Di 08.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
