 Thema: Entscheidbarkeit, wenn A und Komplement semi entscheidbar |
|
|
Hallo,
Ich soll die Äquivalenz zwischen A entscheidbar und A und Komplement A semientscheidbar zeigen
Habe so angefangen:
Wenn L entscheidbar ist, gibt es ein X aus L, welches berechenbar ist. Man definiert ein X´, welches Semientscheidbar ist mit dem Inhalt r.
Dann gilt:
X´ Komplement L(r)={1, falls xL(r)=1 ; undefiniert, falls xL(r)=0
X´ Komplement L(r)={1, falls xL(r)=0 ; undefiniert, falls xL(r)=1
Da wir wissen, dass wenn XL entscheidbar ist, auch X Komplement L entscheidbar ist, heißt das, dass X´L und X´Komplement L berechenbar sind und somit L semientscheidbar und Komplement L semientscheidbar aus L entscheidbar folgen.
Leider komme ich mit dem Code nicht ganz klar, hoffe man kann es trotzdem entziffern.
Mir kommt dieser Beweis sehr schwammig vor und die andere Richtung fehlt noch,d a fehlt mir leider die Idee..
Danke!
|
|
| Thema: Registermaschine Kleines Element einer Liste |
|
|
Naja, wir haben noch keinen Befehl kennen helernt, um zu überprüfen, ob eine Zahl größer oder kleiner ist. Deshalb muss ich mir der Differenz arbeiten. Da ist nur das Problem, dass ich negative Werte nicht speichern kann.
Ich stehe echt auf dem schlauch..
|
|
| Thema: Registermaschine Kleines Element einer Liste |
|
|
Hallo Leute.
Ich bin am verzweifeln.
Alle haben es gesagt und es bewahrheitet sich. Theoretische Informatik ist schwierig. Aber ich muss da durch und möchte es auch schaffen.
Aber ich komme bei einer Aufgabe überhaupt nicht weiter.
Vieleicht könnt Ihr mir ja ein Denkanstoß geben.
Meine Ideen:
So wie ich das verstehe, habe ich eine Liste, deren Elemente bei C(8) anfangen. Das heißt ich lade mir dieses Element und schaue, ob es 0 ist, wenn nicht lade ich C(C(9)) und schaue dann ob das 0 ist, wenn nicht schaue ich ob C(8) > oder < ist als C(C(9)) und speichere diesen Wert wieder ab. Dann gehe ich zum nächsten Feld und schaue wiederum ob dieses Fel 0 ist, wenn nicht schae ich ob die Different dieses Elementes mit dem davor < ist als die DIfferenz zuvor, wenn ja speichere ich diese ab, wenn nein, nicht.
Das mache ich solange, bis ich das kleinste Element gefunden habe.
Mein Problem ist, wenn es so wäre, wie ich es beschrieben habe, wäre es eine Endlsschleife..
Dankbar für jeden Denkanstoß!
|
|
|
