Hallo Sabine
Hallöchen!
Ich habe ein kleines Problem mit dem Verständnis von
entscheidbaren Mengen. Und zwar habe ich folgende Fragen:
* wie darf ich mir die Sache "vorstellen", wenn da steht, die
Menge A ist entscheidbar,
Um es umgangsprachlich zu formulieren : Du hast eine Menge A und Dir wird ein "potenzielles" Element x dieser Menge vorgesetzt, welches allerdings erst noch "getestet" werden muss, ob es in A tatsächlich enthalten ist oder nicht. Wenn es nun ein Programm gibt, welches egal welches x man ihm zum testen als Eingabe gibt, immer nach endlicher Zeit anhält und die korrekte Antwort gibt (also ob x in A oder x nicht in A ), dann ist A entscheidbar. Die Funktion, die von diesem Programm realisiert wird heisst übrigens "Characteristische Funktion".
In diesem Zusammenhang wirst Du übrigens auch auf den Begriff "rekursiv aufzählbar" stoßen. R.a. ist eine Menge dann, wenn es ein Programm gibt, welches bei jedem eingegebenen, zu testenden x zumindest dann immer nach endlicher Zeit anhält, und die richtige Antwort "x gehört zu A" ausgibt, wenn x tatsächlich zu A gehört, wenn x nicht zu A gehört, darf das Programm sich hingegen in endlose Schleifen begeben.
* wie kann ich sagen, dass etwas entscheidbar ist, bzw dieses
Begründen? (z.B: warum ist diese Menge entscheidbar?
{(x,y)E N^2 | x = y^2 } )
Naja, Du kannst doch ein Programm schreiben, welches ein Zahlenpaar (x,y) als Eingabe bekommt und dann immer nach endlicher Zeit richtig ausgeben kann, ob x das Quadrat von y ist, oder ob das nicht der Fall ist. also ist diese Menge entscheidbar.
Kann mir da irgendjemand weiterhelfen, oder hat irgendjemand
was schriftliches (Internetseite...) dazu, das weiterhelfen
könnte?
Ich hoffe, diese sehr untechnische Erklärung ist Dir nicht zu unwissenschaftlich, aber ich dachte, vielleicht findest Du an der theoretischen Informatik und ihren Formalismen nicht so viel gefallen.
Bin dankbar für jede Hilfe...
;-)
Ausserdem hast Du ja sicher auch hilfsbereite Kommilitonen, Tutoren oder Professoren.
viel Spaß noch mit Info wünscht Dir
unimportant
