Universelle Funktion < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:08 Mi 26.06.2013 | | Autor: | sartari |
| Aufgabe 1 | Wir betrachten die Gödelisierung aller RAMs und definieren für alle $i [mm] \in \mathbb{N}$:
[/mm]
[mm] $\varphi_i=_{def} \text{ die von der Ram } M_i \text{ berechnete einstellige Funktion}$
[/mm]
Zeigen Sie, dass die universelle Funktion
$u : [mm] \mathbb{N}^2 \rightarrow \mathbb{N} [/mm] : (i,x) [mm] \mapsto \varphi_i(x)$
[/mm]
berechenbar ist. |
| Aufgabe 2 | Zeigen Sie, dass es berechenbare und totale Funktionen $r,s : [mm] \mathbb{N}^2 \rightarrow \mathbb{N}$ [/mm] gibt mit
(a) [mm] $\varphi_{r(i,j)} [/mm] = [mm] sum(\varphi_i,\varphi_j)$
[/mm]
(b) [mm] $\varphi_{r(i,j)} [/mm] = [mm] prod(\varphi_i,\varphi_j)$
[/mm]
Hierbei verwenden wir die Nummerierung der Funktionen wie in Aufgabe 1 |
So, ich bin da zu Aufgabe 1 einfach so vorgegangen, aber das kommt mir jetzt fast irgendwie zu simpel vor:
Die universelle Funktion $u: [mm] \mathbb{N}^2 \rightarrow \mathbb{N}: [/mm] (i,x) [mm] \mapsto \varphi_i(x)$ [/mm] berechnet erst die RAM [mm] $M_i$ [/mm] mit
[mm] $M_i=\begin{cases} M & \text{, falls }dya(i) = c(M) \text{ für eine RAM M gilt}\\
M^* & \text{, falls }dya(i)\text{ nicht der Code einer RAM ist}\end{cases}$
[/mm]
und dann deren Ausagabewert für $x$. Da die Funktion $u$ immer nur berechenbare RAMs $M [mm] \vee [/mm] M^* $ erzeugt und die berechne RAM mit Eingabewert $x$ simuliert, ist $u$ offensichtlich berechenbar. Da wir in Theorem 2.10 (RAM [mm] $\subseteq$ [/mm] TM) bereits gezeigt haben, wie eine RAM M durch eine TM M' simuliert werden kann und wir auch dort bereits eine dyadische Kodierung einer RAM benutzt haben, können wir dies auch beinahe äquivalent auf $u$ anwenden. Die Aufgabe von M' besteht also lediglich darin, aus $i$ RAM-Befehle zu konstruieren und diese zu simulieren, natürlich mit Eingabewert $x$. Ist $i$ durchlaufen und endete nicht auf $STOP$ oder ist in keiner korrekten Form, so schreiben wir nur die dyadische Kodierung von $STOP$ aufs Band.
Meine Frage dazu ist einfach, ob da noch mehr zu zeigen ist oder ob das damit überhaupt in irgendeiner Form gezeigt ist.
Insbesondere in Zusammenhang mit Aufgabe 2 bin ich da dann doch ein wenig ratlos.
Dankeschön!:)
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.;)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 28.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
