hallo, vielleicht kann mir jemand bei folgendem beweise helfen.
Ich habe eine Menge S die rekursiv aufzählbar aber nicht rekursiv ist.
Menge L= {(x,y)| x Element S und y Element nicht S(komplement)}
hmm…
1)Ist L rekursiv aufzählbar? Und vor allem, kann man das beweisen.
2)Ist nicht L(komplement) rekursiv aufzählbar?
ich würde sagen L ist rekursiv aufzählbar wenn sowohl S als auch das Komplement von S rekursiv aufzählbar sind, dann ist L sogar rekursiv. Aber schreibe ich das schön als beweis hin.
zu 2 weiss ich spontan erstmal nicht viel…
vielleicht kann mir jmd bei den beweisen helfen, das wäre nett.
merci.
Hi…
Ich habe eine Menge S die rekursiv aufzählbar aber nicht
rekursiv ist.
Menge L= {(x,y)| x Element S und y Element nicht
S(komplement)}
hmm…
1)Ist L rekursiv aufzählbar? Und vor allem, kann man das
beweisen.
2)Ist nicht L(komplement) rekursiv aufzählbar?
ich würde sagen L ist rekursiv aufzählbar wenn sowohl S als
auch das Komplement von S rekursiv aufzählbar sind, dann ist L
sogar rekursiv.
Das ist im Prinzip richtig, aber wenn sowohl S als auch rekursiv aufzählbar sind, dann ist S rekursiv, was Deiner Voraussetzung widerspricht.
zu 2 weiss ich spontan erstmal nicht viel…
Ich auch nicht. Wenn ich die Aufgabe richtig lese, würde ich sagen, weder L noch sind rekursiv aufzählbar, weil die in den Elementen von L enthaltenen y nicht rekursiv aufzählbar sind.
Allerdings ist das nicht gerade mein Spezialgebiet, darum kann ich diese eher intuitive Behauptung nicht formal beweisen (und mit Intuition sollte man bei nichtrekursiven Mengen sehr vorsichtig sein).
genumi