Entscheidbarkeit

freakC++

Hallo zusammen,

unser Professeur meinte, dass ein einzelnes Problem niemals un-/entscheidbar sein kann. Das verstehe ich aber nicht, denn man sagt doch, dass beispielsweise das Halteproblem nicht entscheidbar ist.

Wisst ihr mehr?

edit: Außerdem grübele ich über den folgenden Satz: Das Post'sche Korrespondenzproblem ist rekursiv aufzählbar, aber nicht rekursiv entscheidbar.

Bedeutet dies, dass es für jedes PCP eine Turingmaschine gibt, aber sie nicht rekursiv entscheidbar ist, weil diese Turingmaschine nicht unbedingt terminieren muss...

Vielen Dank
LG, freakC++

Bashar

freakC++ schrieb:

unser Professeur meinte, dass ein einzelnes Problem niemals un-/entscheidbar sein kann. Das verstehe ich aber nicht, denn man sagt doch, dass beispielsweise das Halteproblem nicht entscheidbar ist.

Was genau ist denn mit einem "einzelnen" Problem gemeint?

Michael E.

freakC++ schrieb:

unser Professeur meinte, dass ein einzelnes Problem niemals un-/entscheidbar sein kann. Das verstehe ich aber nicht, denn man sagt doch, dass beispielsweise das Halteproblem nicht entscheidbar ist.

Hier fehlt ein wenig der Kontext. Hat er vielleicht gesagt, dass eine einzelne Instanz nicht unentscheidbar sein kann? Oder bezieht er sich darauf, dass man sich zuerst auf ein Rechenmodell einigen muss?

edit: Außerdem grübele ich über den folgenden Satz: Das Post'sche Korrespondenzproblem ist rekursiv aufzählbar, aber nicht rekursiv entscheidbar.

Bedeutet dies, dass es für jedes PCP eine Turingmaschine gibt, aber sie nicht rekursiv entscheidbar ist, weil diese Turingmaschine nicht unbedingt terminieren muss...

Nicht "sie", sondern "es". Für eine Turingmaschine macht die Eigenschaft "entscheidbar" keinen Sinn. So ganz stimmt deine Aussage nicht, denn sonst wäre jedes Problem rekursiv aufzählbar, indem man für jedes Problem eine Turingmaschine nimmt, die nie hält.

knivil

http://de.wikipedia.org/wiki/Rekursiv_aufzählbare_Menge

Bedeutet dies, dass es für jedes PCP eine Turingmaschine gibt, aber sie nicht rekursiv entscheidbar ist, weil diese Turingmaschine nicht unbedingt terminieren muss...

Nicht praezise genug. Aber im Prinzip: Ja. Nur Probleme sind (nicht) entscheidbar. Die Turingmaschine ist nur ein Werkzeug. Ist ein Hammer entscheidbar?

freakC++

Alles klar Danke für die Antworten. Ich habe mich schlecht ausgedrückt, aber ich habe es nun verstanden :). Super!

Bis bald und danke

PS.: Nein, ein Hammer ist nicht entscheidbar, aber man kann damit entscheiden