www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - rekursiv rekursiv aufzählbar
rekursiv rekursiv aufzählbar < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

rekursiv rekursiv aufzählbar: Problem
Status: (Frage) beantwortet Status 
Datum: 09:52 Di 03.01.2006
Autor: Flugzwerg

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

        
Bezug
rekursiv rekursiv aufzählbar: Antwort
Status: (Antwort) fertig Status 
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 []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.

Bezug
                
Bezug
rekursiv rekursiv aufzählbar: Frage und Versuch
Status: (Frage) beantwortet Status 
Datum: 11:52 Di 03.01.2006
Autor: Flugzwerg

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





Bezug
                        
Bezug
rekursiv rekursiv aufzählbar: Antwort
Status: (Antwort) fertig Status 
Datum: 12:56 Di 03.01.2006
Autor: mathiash

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

Bezug
                                
Bezug
rekursiv rekursiv aufzählbar: nochmal
Status: (Frage) beantwortet Status 
Datum: 11:31 Mi 04.01.2006
Autor: Flugzwerg

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

Bezug
                                        
Bezug
rekursiv rekursiv aufzählbar: Antwort
Status: (Antwort) fertig Status 
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.


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de