Nummerierungen und Berechenbar < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Aufgabe:
Zeigen sie das die Menge [mm] \IN [/mm]
[mm] \nu_{\IQ}-rekursiv [/mm] ist |
Halli Hallo!
Ich habe da mal wieder eine Frage. Diesmal zum ThemaNummerierungen und induzierte Berechenbarkeit.
Ich habe folgende Definition von [mm] \nu_{\IQ}:
[/mm]
[mm] \IN \to \IQ, \nu_{\IQ}:=\bruch{i-j}{1+k} [/mm] für alle [mm] i,j,k\in \IN
[/mm]
Eine Definition für [mm] \nu [/mm] ist:
Es seien [mm] \nu: \subseteq \IN \to [/mm] M und (....) Nummerierungen.
eine Menge [mm] X\subseteq [/mm] M heisst v-rekursiv, gdw es eine berechenbare Funktion [mm] g:\subseteq \IN \to \IN [/mm] gibt mit
1 falls [mm] \nu(i)\in [/mm] X
g(i) { (für alle [mm] i\inDef(\nu)) [/mm] }
0 (sonst)
Kann ich jetzt nicht einfach sagen:
[mm] \IN \subseteq \IQ [/mm] heisst [mm] \nu_{\IQ} [/mm] rekursiv, gdw es eine berechenbare Funktion :
g: [mm] \IN\to\IQ [/mm] gibt mit
1 falls [mm] \nu_{\IQ}(i) \in\IN
[/mm]
g(i,j,k)={ (für alle [mm] i,j,k\in Def(\nu_{\IQ}) [/mm] }
0 sonst
?
Ist das so korrekt? oder habe ich da mal wider einen denkfehler???
Danke für eure hilfe!
LG,
Nicole
|
|
| |
|
Hallo Nicole,
ich wuerde sagen, Du liegst genau richtig. Laut der von Dir gegebenen Definitionen
ist die Existenz eines solchen g genau das, was Du zeigen musst.
Du kannst dabei jetzt ja schon benutzen, dass die Funktionen <....> und ihre Projektionen
berechenbar sind.
Nur zur Notation: es sollte sicherlich
[mm] \nu_{\IQ}() [/mm] lauten, oder ? Denn Du hast ja die drei Zahlen, die Dir die
rationale Zahl [mm] \frac{i-j}{1+k} [/mm] definieren.
Dir weiter viel Erfolg !!!
Viele Gruesse,
Mathias
|
|
|
|
