| zstern |
Ist eine Menge entscheidbar? (Berechenbarkeit)
Meine Frage:
Hallo liebe Community!
Das ist meiner erster Post hier.
Ich beschäftige mich gerade mit dem Thema "Berechenbarkeit" bzw. "Entscheidbarkeit" aus der theoretischen Informatik. Dazu habe ich ein paar Lern-Feedback-Aufgaben. Ich würde nachfolgend die Fragestellung und meine Antwort dazu notieren und würde mich über Feedback zu meinen Antworten freuen. Insbesondere wenn eine Antwort falsch ist, dann wäre ich für eine Erklärung dankbar.
Aufgabentyp: Mann muss jeweils für jede Mende entscheiden, ob
(E) die Menge entscheidbar ist,
(A) aufzählbar aber nicht entscheidbar,
(N) nicht aufzählbar ist.
RAM bezeichnet hier eine Random Access Machine (Registermaschine) und i ist dabei die zugehörige Gödelnummer.
Die Funktion bei A3 und A4 ist die nirgends definierte einstellige Funktion 0: GOTO 0.
Die Mengen sind unten auch als Abbildung angehängt.
-------------
Meine Ideen:
A1: { n | n in N und das Polynom x^n + n hat eine Nullstelle in den reellen Zahlen}
Meine Lösung: E, algorithmisch berechenbar und somit entscheidbar.
A2: {n | n in N und das Polynom x^n+n hat eine Nullstelle in den ganzen Zahlen}
Meine Lösung: E, algorithmisch berechenbar und somit entscheidbar.
A3: { i | RAM M_i berechnet nicht ½^1}
Meine Lösung: A, da nach Satz von Rice nicht entscheidbar. Allerdings kann mit einer RAM und Vorgabe von maximaler Rechenschritte durch eine RAM entschieden werden, ob eine Ausgabe erfolgt oder nicht. Daher semi-entscheidbar.
A4: { i | RAM M_i berechnet ½^1}
Meine Lösung: N, da A3 aufzählbar aber nicht entscheidbar, denn A4 ist das Komplement von A3.
A5: { i | RAM M_i hält auf mindestens 3 Eingaben aus N}
Meine Lösung: A. Das Halteproblem ist semi-entscheidbar. Also kann man auch hier bei der Lösung zu A3 prüfen, ob eine RAM nach einer maximalen Anzahl von Schritten stoppt auf mindestens drei natürlichen Zahlen.
Für hilfreiche Rückmeldungen wäre ich dankbar!
zstern hat diese Bilder (verkleinerte Versionen) angehängt:
  
 
|
