rekursiv rekursiv aufzählbar < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Aufgabe:
Es sei Q [mm] \subseteq \IN^3 [/mm] rekursiv.
Dann ist A:= { i [mm] \in \IN [/mm] | ( [mm] \existsj,k)(i,j,k) \in [/mm] Q}
rekursiv aufzählbar |
| Aufgabe 2 | Aufgabe:
Es sei Q [mm] \subseteq \IN^3 [/mm] rekursiv.
Dann ist B:= { i [mm] \in \IN [/mm] | ( [mm] \existsj,k \le [/mm] i )(i,j,k) [mm] \in [/mm] Q }
rekursiv. |
Halli Hallo!
Ich habe irgendwie ein paar Startschwierigkeiten mit den rekursiven Mengen.
Also bei a:
Die Rekursivität von Q Teilmenge von [mm] N^3 [/mm] ist ja schon vorgegeben.
Das heisst das eine Charakteristische Funktion für A existiert die
berechenbar ist.
Das ist ja soweit gegeben und da muss ich nichts zeigen oder?
So. um jetzt zu zeigen dqas A rekursiv ist habe ich ja unterschiedliche
möglichkeiten.
* Die menge ist endlich
* Sie ist semientscheidbar
* sie ist leer
* es gibt eine surjektiv berechenbare Funktion N--->M
So. ausschliessen kann ich das sie leer ist oder?
Wie bzw mit welchem Punkt der aufgeführten zeige ich jetzt das sie
rekursiv aufzählbar ist?
Kann mir jemand die Definition unserer Menge A mal erläutern? Ich bin
durch die Klammern irritiert.Was genau ist denn i, j, k was die erste und
die zweite klammer, versteh ich nicht so ganz...
Ist die Menge vielleicht schon durch das i Element von N endlich und
damit rekursiv aufzählbar?
Danke für Eure hilfe!
LG,
NIK
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:57 Di 03.01.2006 | | Autor: | Frank05 |
> Aufgabe:
>
> Es sei [mm]Q \subseteq \IN^3[/mm] rekursiv.
> Dann ist [mm]A:= \{ i \in \IN |(\exists j,k)(i,j,k) \in Q \}[/mm]
> rekursiv aufzählbar
> Ich habe irgendwie ein paar Startschwierigkeiten mit den
> rekursiven Mengen.
>
> Also bei a:
>
> Die Rekursivität von Q Teilmenge von [mm]\IN^3[/mm] ist ja schon
> vorgegeben.
>
> Das heisst das eine Charakteristische Funktion für A
> existiert die
> berechenbar ist.
Vorsicht #1: Von der Existenz brauchen wir gar nicht erst zu reden. Diese charakt.Fkt.s existieren immer. Du weißt wie sie definiert sind, also brauchst du das nur noch hinschreiben und schon gibts die Funktion. Interessant sind einzig und allein die Eigenschaften dieser Funktion - insbesondere die Berechenbarkeit.
Vorsicht #2: Du musst sorgfältig unterscheiden zwischen der charakt.Fkt. und der halben charakt.Fkt. Ist eine Menge rek.aufz., bzw. semi-entscheidbar, so ist erstmal lediglich die halbe charakt. Fkt. berechenbar.
> Das ist ja soweit gegeben und da muss ich nichts zeigen
> oder?
Was soll man auch zeigen bei gegebenen Voraussetzungen.
> So. um jetzt zu zeigen dass A rekursiv ist habe ich ja
> unterschiedliche möglichkeiten.
>
> * Die menge ist endlich
> * Sie ist semientscheidbar
> * sie ist leer
> * es gibt eine surjektiv berechenbare Funktion N--->M
und noch einige mehr 
Sieh vielleicht mal in deinem Skript nach. Bei uns stand da etwa eine halbe Seite mit Aussagen, die äquivalent sind zu "A ist semi-entscheidbar". (Aber im Prinzip genügen dir die wichtigsten, die du hier genannt hast)
> So. ausschliessen kann ich das sie leer ist oder?
Nein.
Ob sie leer ist hängt von Q ab. Wenn Q schon leer wäre, dann wäre auch A leer.
Du kannst es also nicht ausschließen, aber mit einer Fallunterscheidung ist das schnell erledigt: Falls A leer wäre, dann wäre A nach Def. rek.aufz. Fertig. Also sei jetzt o.B.d.A. die Menge A nicht leer.
> Wie bzw mit welchem Punkt der aufgeführten zeige ich jetzt
> das sie
> rekursiv aufzählbar ist?
Ganz unabhängig von der Thematik solltest du vielleicht mal einen Blick auf ![[]](/images/popup.gif) www.dassdas.de werfen.
Ich würde hier mittels der rekursiven Aufzählbarkeit von Q argumentieren und mit der aus der entsprechenden Definition gegebenen berechenbaren Fkt [mm]f:\IN \rightarrow Q[/mm] die halbe charakt. Fkt. von A berechnen.
> Kann mir jemand die Definition unserer Menge A mal
> erläutern? Ich bin
> durch die Klammern irritiert.Was genau ist denn i, j, k
> was die erste und
> die zweite klammer, versteh ich nicht so ganz...
Die erste Klammer um den Existenzquantor ist eher ungebräuchlich. Die kannst du auch einfach weglassen. Da aber Q eine Teilmenge von [mm]\IN^3[/mm] ist befinden sich in Q gerade Tripel von natürlichen Zahlen. Daher stammt die Schreibweise [mm](i,j,k)[/mm] für ein solches Zahlentripel. Die Fragestellung, die sich hinter A verbirgt lautet somit: gegeben eine nat. Zahl i, gibt es in Q ein Zahlentripel, dessen erste Zahl gleich i ist? Eben diese Frage musst du nun noch umschreiben in die entsprechende halbe charakt.Fkt. von A und dann noch zeigen, dass diese berechenbar ist. Da das nicht wirklich schwer ist will ich dir hier den Spass nicht nehmen und es dich selbst versuchen lassen 
> Ist die Menge vielleicht schon durch das i Element von N
> endlich und
> damit rekursiv aufzählbar?
i.A. Nein.
Es hängt wiederum von Q ab, ob A endlich ist.
|
|
|
| |
|
Hi!
erst einmal danke für Deine Antwort. Etwas klarer ist es schon, aber ganz klar auch noch nicht.
Also Im klartext heisst es ja das JEDE rekursive Menge auch rekursiv aufzählbar ist.
also [mm]Q \subseteq \mathbb{N}^3[/mm] heisst rekursiv aufzählbar gdw es eine partielle Funktion [mm]f \subseteq \mathbb{N}^3 \to Q[/mm] gibt mit [mm]Q := \mathrm{Def}(f)[/mm]. Das ist eine Definition aus meinem Skript, die dann wohl gleich ist mit der halben charakteristischen Funktion???
Wenn die halbe Charakteristische Funktion existiert sieht das dann so aus?
[mm]\mathrm{cf}: \mathbb{N}^3 \to Q[/mm] mit [mm]\mathrm{cf}\left(A(i)\right) := \begin{cases}1 & \texttt{falls }i \in Q\\\mathrm{div}&\texttt{sonst}\end{cases}[/mm]
?
Oder ist das jetzt kompletter unsinn?
Und unsicher bin ich auch bei der [mm]\mathrm{cf}[/mm] weil ich nicht sicher bin ob ich die jetzt von [mm]A[/mm] oder von [mm]Q[/mm] brauche.
Hm, irgendwie bin ich noch komplett unsicher. :-(
Danke schon mal für Deine hilfe...
Liebe Grüße,
NIK
|
|
|
| |
|
Hallo,
die ''halbe'' charakteristische Funktion hast Du richtig hingeschrieben, aber
auch von mir nochmal der Hinweis:
Zu einer gegebenen Menge [mm] A\subseteq \IN^d [/mm] existieren die charakteristische
Funktion
[mm] \chi_A\colon \IN^d\to \{0,1\}, \chi_A(x)=1 \Leftrightarrow x\in [/mm] A
und die ''halbe char. Funktion'' [mm] cf_A [/mm] - wie von Dir definiert- immer !
A ist rekursiv gdw [mm] \chi_A \mu-rekursiv [/mm] ist, und A ist rekursiv aufzaehlbar gdw
[mm] cf_A \mu-rekursiv [/mm] ist.
Mach Dir doch zu den zur Diskussion stehenden Mengen erst einmal intuitiv klar,
wie Du, ausgehend von der Rekursivitaet der ersten Menge - war es A oder Q ???-
die beiden ''Projektionsmengen'' algorithmisch angehen wuerdest:
Im Falle der unbeschraenkten Projektion wuerdest Du doch systematisch nach solchen
Zahlen suchen, ueber die existentiell quantifiziert wird, also Anwendung des [mm] \mu-Operators.
[/mm]
Im anderen Fall ist diese Suche beschraenkt, d.h. Du durchsuchst eine endliche Menge
von Zahlen, d.h. die Suche terminiert in endlicher Zeit, also ist diese Menge rekursiv.
Eine generelle Empfehlung: Nimm vielleicht zum Skript noch etwas Lieratur
hinzu, zB das Buch ueber Rekursionstheorie von Rogers.
Gruss,
Mathias
|
|
|
| |
|
Hallo Matthiash oder frank oder alle anderen!
Also ich komme leider keinen Schritt weiter. Ich brauche eine Erklärung für Dummies.
Nach meinem Skript , mit dem ich ja Probleme habe, dachte ich ich muss diesen Projektionssatz anwenden.
1. A [mm] \subseteq \IN [/mm] ist rekursiv aufzählbar gdw A = [mm] \emptyset [/mm] oder A= Bild(g) für ein g [mm] \in [/mm] R^(1).
2. A [mm] \subseteq \IN^k [/mm] ist rekursiv aufzählbar gdw. A = {x [mm] \in \IN^k [/mm] | [mm] (\exists [/mm] t)(x,t) [mm] \in [/mm] B} für eine rekursive Menge B [mm] \subseteq \IN^k+1.
[/mm]
Tja, und leider komme ich trotz Bücher die ich gier habe nicht zurecht.
Für weitere Hilfe wäre ich mehr als dankbar!
LG,
NIK
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:17 Mi 04.01.2006 | | Autor: | Frank05 |
> Nach meinem Skript , mit dem ich ja Probleme habe, dachte
> ich ich muss diesen Projektionssatz anwenden.
>
>
> 1. A [mm]\subseteq \IN[/mm] ist rekursiv aufzählbar gdw A =
> [mm]\emptyset[/mm] oder A= Bild(g) für ein g [mm]\in[/mm] R^(1).
Ich weiß jetzt nicht, was du mit R^(1) meinst. Die Schreibweise ist mir nicht geläufig, aber es gibt einen Satz, dass A rek.aufz. ist gdw A Wertebereich einer berechenbaren Funktion ist (der Fall A = [mm]\emptyset[/mm] ist da bereits mit eingeschlossen, weswegen der Satz von dir wohl eine etwas andere Bedeutung zu haben scheint).
> 2. [mm]A \subseteq \IN^k[/mm] ist rekursiv aufzählbar gdw. A =
> [mm]\{x \in \IN^k[/mm] | [mm](\exists[/mm] t)(x,t) [mm]\in B\}[/mm] für eine rekursive
> Menge B [mm]\subseteq \IN^k+1.[/mm]
Das sieht doch deiner Aufgabe schon recht ähnlich. Allerdings ist jetzt [mm]Q \subseteq \IN^3[/mm] und [mm]A \subseteq \IN[/mm] und somit der Satz nicht direkt anwendbar. Aber du bist definitiv auf der richtigen Spur.
Und falls dir das noch niemand gesagt hat, dann pass jetzt besonders gut auf:
Häufig befinden sich die interessanten Erkenntnisse im Beweis, nicht im Satz selbst
Wenn du dir den Beweis zu diesem Satz ansiehst wirst du mit sehr hoher Wahrscheinlichkeit auf ein Beweisverfahren stoßen, dass du nach genau dem gleichen Schema auf deine Aufgabe anwenden kannst. Es würde mich zumindest schwer wundern, wenn dem nicht so wäre
Als kleiner Tipp, was du evtl noch dazu brauchen kannst: Wirf auch nochmal einen Blick auf den Beweis für die Abzählbarkeit von [mm]\IN^k[/mm]. Dieses Beweisverfahren kannst du zusammenbringen mit dem Beweisverfahren des obigen Satzes, um somit den gesuchten Beweis zu erzeugen.
|
|
|
|
