Endscheidbarkeit Berechenbarke < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:44 Di 21.04.2009 | | Autor: | krueemel |
| Aufgabe | Wann ist eine Funktion entscheidbar, wann berechenbar? Wie hängen diese Begriffe miteinander zusammen?
Beispiele für berechen- und entscheidbare? |
Hallo,
mir ist schon klar, was berechenbar und entscheidbar bedeutet. Doch gibt es einen direkten Zusammenhang?
Wenn eine Funktion berechenbar ist, ist sie dann entscheid und auch umgekehrt?
berechenbare Funktionen:
- entscheidbare: Primzahlen, Quadratzahlen, ...
- partiell entscheidbare: Wundersamkeit, ...
nicht berechenbare Funktionen:
Halteproblem, ...
habt ihr noch mehr Beispiele?
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:40 Mi 22.04.2009 | | Autor: | bazzzty |
> Wann ist eine Funktion entscheidbar, wann berechenbar? Wie
> hängen diese Begriffe miteinander zusammen?
> Beispiele für berechen- und entscheidbare?
Die Frage ist schon falsch gestellt. Eine Funktion kann berechenbar sein (d.h. man kann einen Algorithmus angeben, der sie berechnet).
*Entscheidbar* können nur Mengen sein. Eine Menge ist entscheidbar, wenn die sogenannte charakteristische Funktion berechenbar ist. Diese Funktion liefert 1 genau für Elemente der Menge, sonst 0 (totale Entscheidbarkeit).
Beispiel: Die Menge der Primzahlen ist eine entscheidbare Menge, die zugehörige charakteristische Funktion ist berechenbar.
> mir ist schon klar, was berechenbar und entscheidbar
> bedeutet.
So wie die Aufgabe gestellt ist, scheint das selbst dem Aufgabensteller nicht ganz klar zu sein.
> Doch gibt es einen direkten Zusammenhang?
Ja. Beliegige Funktionen [mm]f:A\to B[/mm] können berechenbar sein. Sie sind es, wenn man, salopp gesagt, aufschreiben kann, wie man sie berechnet.
Eine Menge (wie die Menge der Primzahlen) [mm]M\subset \IN[/mm] ist entscheidbar, wenn die Funktion "[mm]\chi_M:\IN\to \{0,1\}[/mm] mit [mm]\chi(n)=1[/mm] genau dann, wenn [mm]n\in M[/mm]" berechenbar ist.
> Wenn eine Funktion berechenbar ist, ist sie dann entscheid
> und auch umgekehrt?
Nein. Spezielle berechenbare Funktionen entscheiden Mengen. Die sind dann entscheidbar.
> berechenbare Funktionen:
> - entscheidbare: Primzahlen, Quadratzahlen, ...
Prim- und Quadratzahlen sind Mengen von Zahlen. Sie sind entscheidbar, weil man eine berechenbare Funktion angeben kann, die sie entscheiden.
> - partiell entscheidbare: Wundersamkeit, ...
Partielle Entscheidbarkeit von Mengen fordert nur partielle Berechenbarkeit (was wiederum heißt: Der Algorithmus, der die charakteristische Funktion berechnet, muss bei Elementen [mm]m\not\in M[/mm] nicht terminieren)
> nicht berechenbare Funktionen:
> Halteproblem, ...
Die Menge aller immer terminierender Programme ist nicht entscheidbar, weil die charakteristische Funktion nicht berechenbar ist.
> habt ihr noch mehr Beispiele?
Ich hoffe, ich habe erstmal die Missverständnisse behoben.
|
|
|
|
