Hi,

http://de.wikipedia.org/wiki/Satz_von_Rice, hier gibt es einen beweis zum satz von rice. der beweis wird im f3-skript im prinzip genauso geführt.
wenn ich den beweis richtig verstehe, konstruiert man sich einen algorithmus, der dieselbe funktion wie M_f berechnet, wenn M_w terminiert. terminiert M_w nicht, wird die überall undefinierte funktion berechnet. aber mit diesem beweis könnte man doch auch eine entscheidbare menge auf das halteproblem reduzieren, was ja falsch wäre.
wenn ich mir eine turingmaschine M baue, in die eine turingmaschine M' integriert ist. diese tm M' simuliert eine beliebige tm mit einer beliebigen eingabe. terminiert M', dann hat M die eigenschaft einer entscheidbaren menge. wenn M' nicht terminiert, dann gehört M nicht zu der entscheidbaren menge.
dieser beweis würde doch im prinzip genauso funktionieren, wie der bei wiki bzw. wie der im f3-skript. aber der beweis kann ja nicht richtig sein, weil er ein entscheidbares problem auf das halteproblem reduzieren würde. [img]http://www.fb18.de/gfx/3.gif[/img]
irgendwo hab ich hab ich einen denkfehler, den ich nicht finde

wenn ich den beweis richtig verstehe, konstruiert man sich einen algorithmus, der dieselbe funktion wie M_f berechnet, wenn M_w terminiert. terminiert M_w nicht, wird die überall undefinierte funktion berechnet. aber mit diesem beweis könnte man doch auch eine entscheidbare menge auf das halteproblem reduzieren, was ja falsch wäre.

Du meinst sicher, dass dann das Halteproblem auf eine
entscheidbare Menge reduzierbar wäre (denn tatsächlich
ist jede entscheidbare Menge auf jede nichttriviale Menge
reduzierbar).

wenn ich mir eine turingmaschine M baue, in die eine turingmaschine M' integriert ist. diese tm M' simuliert eine beliebige tm mit einer beliebigen eingabe. terminiert M', dann hat M die eigenschaft einer entscheidbaren menge. wenn M' nicht terminiert, dann gehört M nicht zu der entscheidbaren menge.
dieser beweis würde doch im prinzip genauso funktionieren, wie der bei wiki bzw. wie der im f3-skript.

Nein, das würde nicht genauso funktionieren. Du sagst
ja einfach: Wenn M' hält, dann soll M irgendwas tun, um
dann diese entscheidbare Eigenschaft zu haben und wenn M'
nicht hält, dann soll M irgendwas tun, um diese Eigenschaft
nicht zu haben. Wie das aber genau funktionieren soll,
sagst du nicht. Das Problem ist nämlich, dass das garnicht geht.
Der Grund, warum der Beweis vom Satz das genau erklärt, ist,
dass dort nicht vorausgesetzt wird, dass die Eigenschaft
entscheidbar ist, sondern sie einfach erfüllt wird oder eben
nicht. Und deine Aussage ist ja nun: Hmm, das geht dann doch
bestimmt auch mit einer entscheidbaren Eigenschaft. Du müsstest
dann aber eine tatsächlich entscheidbare Menge angeben, die dann von
M angenommen wird (oder eben nicht). Aber das geht nicht, denn
sobald eine TM-Eigenschaft entscheidbar ist, lässt es sich von
einer TM nicht zur Laufzeit festlegen, ob sie diese Eigenschaft nun
erfüllen möchte oder nicht (das ist die eigentliche Aussage,
die man dem Beweis entnehmen sollte und die auch praxis-relevant
ist, die aber schwierig präzise zu formulieren ist, deswegen
belässt man's beim Satz von Rice bei den Eigenschaften von
Sprachen).

Ist das klar geworden?

hm, ich steig noch nicht ganz dahinter, warum dieser beweis nur bei einer unentscheidbaren menge korrekt ist.

wenn ich mir eine turingmaschine M baue, in die eine turingmaschine M' integriert ist. diese tm M' simuliert eine beliebige tm mit einer beliebigen eingabe. terminiert M', dann hat M die eigenschaft einer entscheidbaren menge. wenn M' nicht terminiert, dann gehört M nicht zu der entscheidbaren menge.
dieser beweis würde doch im prinzip genauso funktionieren, wie der bei wiki bzw. wie der im f3-skript.

wenn ich nicht voraussetzen würde, dass diese menge entscheidbar ist, dann wäre der beweis doch so wie im skript. wenn ich also nicht weiss, ob diese menge entscheidbar ist, dann sagt der beweis mir doch immer, dass sie es nicht ist.
mir fehlt einfach die stelle, an der der beweis berücksichtigt, ob diese menge entscheidbar ist oder ist. hab da irgendwie einen knoten im kopf

hm, ich steig noch nicht ganz dahinter, warum dieser beweis nur bei einer unentscheidbaren menge korrekt ist.

Der Beweis setzt nicht voraus, dass die Eigenschaft S
unentscheidbar ist, sondern er beweist erst, dass sie
das ist.

Vielleicht hilft dir die Analogie: wenn du beweisen
willst, dass alle natürlichen Zahlen positiv sind,
wird der Beweis natürlich nicht funktionieren, wenn du
an einer entscheidenden Stelle negative Zahlen einsetzt.

wenn ich mir eine turingmaschine M baue, in die eine turingmaschine M' integriert ist. diese tm M' simuliert eine beliebige tm mit einer beliebigen eingabe. terminiert M', dann hat M die eigenschaft einer entscheidbaren menge. wenn M' nicht terminiert, dann gehört M nicht zu der entscheidbaren menge.
dieser beweis würde doch im prinzip genauso funktionieren, wie der bei wiki bzw. wie der im f3-skript.

wenn ich nicht voraussetzen würde, dass diese menge entscheidbar ist, dann wäre der beweis doch so wie im skript. wenn ich also nicht weiss, ob diese menge entscheidbar ist, dann sagt der beweis mir doch immer, dass sie es nicht ist.

Richtig! Das ist ja gerade die Aussage des Satzes: jede
nichttriviale Eigenschaft von rekursiv aufzählbaren
Sprachen ist unentscheidbar!

mir fehlt einfach die stelle, an der der beweis berücksichtigt, ob diese menge entscheidbar ist oder ist.

Danach wird man vergeblich suchen: das wird ja erst gefolgert.
In der Analogie: der Beweis für die Positivität aller
natürlichen Zahlen wäre ziemlich sinnlos, wenn er voraussetzte,
dass diese positiv sind [img]http://www.fb18.de/gfx/28.gif[/img]


Edit: Ich glaube, ich weiss jetzt, was dein Problem ist.
Die Sprache [img]http://mokrates.de/cgi-bin/texstring?M_w[/img] (nach der Bezeichnung bei
Wikipedia) muss man unentscheidbar wählen, damit der Beweis
funktioniert. Das ist aber nicht zu verwechseln mit der
Eigenschaft, deren Unentscheidbarkeit man nachweist! Das sind
zwei verschiedene Mengen. [img]http://mokrates.de/cgi-bin/texstring?M_w[/img] setzt man als
unentscheidbar voraus, und daraus folgert man die
Unentscheidbarkeit von C(S).
Und wenn man die Konstruktion aus dem Beweis mit einem
entscheidbaren [img]http://mokrates.de/cgi-bin/texstring?M_w[/img] macht, hat man nicht bewiesen,
was man wollte, sondern bekommt ein triviales Ergebnis:
Wenn man C(S) entscheiden könnte, dann auch [img]http://mokrates.de/cgi-bin/texstring?M_w[/img].
Insofern hätte man dann tatsächlich ein entscheidbares Problem
auf ein unentscheidbares reduziert.

ah, dein nachtrag hat für etwas klarheit gesorgt. [img]http://www.fb18.de/gfx/danke.gif[/img]

aber eine frage hab ich noch, ich glaub dann hab ich es weitgehend verstanden [img]http://www.fb18.de/gfx/28.gif[/img]:

bei dem beweis nimmt man sich ja eine menge S, von der man nicht weiss, ob sie entscheidbar ist. dann zeigt man mit hilfe des beweises, dass sie unentscheidbar ist. kann es nicht theoretisch sein, dass man bei dieser menge S an eine entscheidbare menge gerät, von der man nicht weiss, dass sie es ist. dann folgert man wegen des beweises, dass sie unentscheidbar ist. der beweis ist dann nicht korrekt, weil S ja entscheidbar ist. aber da man nicht weiss, dass S entscheidbar ist, bemerkt man gar nicht, dass der beweis nicht korrekt ist.
dieses szenario ist sehr konstruiert, aber wäre das nicht möglich?

bei dem beweis nimmt man sich ja eine menge S, von der man nicht weiss, ob sie entscheidbar ist. dann zeigt man mit hilfe des beweises, dass sie unentscheidbar ist. kann es nicht theoretisch sein, dass man bei dieser menge S an eine entscheidbare menge gerät, von der man nicht weiss, dass sie es ist. dann folgert man wegen des beweises, dass sie unentscheidbar ist. der beweis ist dann nicht korrekt, weil S ja entscheidbar ist. aber da man nicht weiss, dass S entscheidbar ist, bemerkt man gar nicht, dass der beweis nicht korrekt ist.
dieses szenario ist sehr konstruiert, aber wäre das nicht möglich?

Wenn ein Beweis einen Fehler enthält, kann er
natürlich zu falschen Schlüssen führen (z.B. dazu,
dass alle Zahlen gleich sind [img]http://www.fb18.de/gfx/28.gif[/img]). Wenn der Beweis
aber richtig ist, sagt er ja gerade, dass kein
solches S entscheidbar ist. Und die Richtigkeit
des Beweises ist unabhängig davon, welches S
"gewählt wird", denn der Beweis ist ja nur dann
richtig, wenn alle Folgerungen unabhängig vom
gewählten S richtig sind.

Ich schätze, ich kann mir vorstellen, wie der Anonyme überhaupt auf solche Gedanken kommt. (ich hoffe das, was ich schreibe ist korrekt, aber sonst wird mich sicherlich jemand korrigieren)

Du scheinst zu denken, dass die Menge S im Satz von Rice einfach beliebig wählbar ist. Aber du kannst natürlich nicht einfach sagen, ich nehme mir jetzt eine entscheidbare Menge und zeige mit dem Satz, dass sie unentscheidbar ist. Du musst bedenken, dass S eine Teilmenge (nicht leer und nicht voll¹) der aufzählbares Sprachen sein soll. Nur darüber macht der Satz eine Aussage. Ein Beweis kann also nicht nur falsche Ergebnisse liefern, wenn der Beweis selbst falsch ist, sondern auch wenn die Nebenbedingungen des Beweises nicht erfüllt werden.

¹irgendwie fehlt dieses Wort in der Mathematik für eine Menge dessen Komplement leer ist

¹irgendwie fehlt dieses Wort in der Mathematik für eine Menge dessen Komplement leer ist

Ich weiß nich, ob es dafür 'n Wort gibt.

Wenn du damit ausdrücken willst, dass es mindestens ein Element in der Menge der aufzählbaren Sprachen gibt, das NICHT in S enthalten ist, S also weniger Elemente hat als diese Menge, dann kann man auch davon sprechen, dass S eine nicht leere "echte Teilmenge" der Menge der aufzählbaren Sprachen ist.

so richtig klar ist es mir immer noch nicht, aber egal ich glaub den satz jetzt einfach.
aber danke für den versuch, mich aufzuklären…

so richtig klar ist es mir immer noch nicht

Hm, OK, ich versuche es nochmal anders. Der Beweis
will ja zeigen: "Jede nichttriviale Eigenschaft der
rekursiv aufzählbaren Sprachen ist unentscheidbar".
Und um das zu beweisen, muss er ja von einer
beliebigen solchen Eigenschaft S zeigen, dass
sie unentscheidbar ist. Er sagt also: Sei S eine
solche Eigenschaft. Dann gilt dies und das und jenes
und das sowieso. …Und darum muss S unentscheidbar
sein.
Damit hat man erklärt, dass, wenn man ein beliebiges
S herausgreift, man ein unentscheidbares gefunden
hat.

Und die Richtigkeit eines Beweises zeichnet sich
dadurch aus, dass für jeden Fall, der eintreten
kann, die Folgerungen richtig sind.

——–
Man kann den Beweis außerdem leicht in einen
Widerspruchsbeweis umschreiben, der geht
dann etwa so: Angenommen, es gäbe eine
nichttriviale entscheidbare Eigenschaft S.
Dann könnnte man mit einer TM, die diese
Eigenschaft S überprüft, folgende
TM bauen: …….. Und damit hat man eine TM, die
das Halteproblem entscheiden kann. Widerspruch!

So formuliert ist es vielleicht etwas eingängiger.

Hm, OK, ich versuche es nochmal anders. Der Beweis
will ja zeigen: "Jede nichttriviale Eigenschaft der
rekursiv aufzählbaren Sprachen ist unentscheidbar".
Und um das zu beweisen, muss er ja von einer
beliebigen solchen Eigenschaft S zeigen, dass
sie unentscheidbar ist. Er sagt also: Sei S eine
solche Eigenschaft. Dann gilt dies und das und jenes
und das sowieso. …Und darum muss S unentscheidbar
sein.
Damit hat man erklärt, dass, wenn man ein beliebiges
S herausgreift, man ein unentscheidbares gefunden
hat.

jo, das hab ich jetzt (endlich!) verstanden.

Du scheinst zu denken, dass die Menge S im Satz von Rice einfach beliebig wählbar ist. Aber du kannst natürlich nicht einfach sagen, ich nehme mir jetzt eine entscheidbare Menge und zeige mit dem Satz, dass sie unentscheidbar ist. Du musst bedenken, dass S eine Teilmenge (nicht leer und nicht voll¹) der aufzählbares Sprachen sein soll. Nur darüber macht der Satz eine Aussage. Ein Beweis kann also nicht nur falsche Ergebnisse liefern, wenn der Beweis selbst falsch ist, sondern auch wenn die Nebenbedingungen des Beweises nicht erfüllt werden.

dass der satz sich nur auf nichttriviale eigenschaften von aufzählbaren sprachen bezieht, ist klar. es ist auch nicht der satz von rice an sich, der mich irritiert, sondern die methode wie er bewiesen wird. ich kann nicht nachvollziehen, warum dieses beweisprinzip (nicht der satz selbst) nicht auf beliebige mengen anwendbar ist. also, wenn ich z. b. eine kontextfreie sprache habe und gucken will, ob diese entscheidbar ist oder nicht. dann sehe ich keinen grund, warum in diesem fall die anwendung des beweisprinzips falsch wäre. aber dann wäre diese beliebige kontextfreie sprache automatisch unentscheidbar.
aber es ist bestimmt wichtiger, den satz verstanden zu haben, als das prinzip, wie er bewiesen wird [img]http://www.fb18.de/gfx/25.gif[/img]

dass der satz sich nur auf nichttriviale eigenschaften von aufzählbaren sprachen bezieht, ist klar. es ist auch nicht der satz von rice an sich, der mich irritiert, sondern die methode wie er bewiesen wird. ich kann nicht nachvollziehen, warum dieses beweisprinzip (nicht der satz selbst) nicht auf beliebige mengen anwendbar ist.

OK, ich glaube jetzt habe ich verstanden, wo das Problem liegt.

also, wenn ich z. b. eine kontextfreie sprache habe und gucken will, ob diese entscheidbar ist oder nicht.

Vorsicht, darüber macht der Satz keine Aussage! Er handelt nur
von der Entscheidbarkeit von Eigenschaften von aufzählbaren
Sprachen, nicht von der Entscheidbarkeit von Sprachen selbst
(höchstens indirekt, aber S ist keine Sprache!). Und eine
Spracheigenschaft wird formalisiert als Menge aller Sprachen,
die diese Eigenschaft erfüllen. Wenn also S die Eigenschaft
"enthält ein Wort, das nur aus einem Buchstaben besteht", dann
ist S die Menge aller Sprachen [img]http://mokrates.de/cgi-bin/texstring?L%5Csubseteq%5CSigma%5E*[/img] mit [img]http://mokrates.de/cgi-bin/texstring?L%5Ccap%5CSigma%5Cne%20%5Cemptyset[/img].
Und man muss strenggenommen erst definieren, was
Entscheidbarkeit für eine solche Eigenschaft heißen soll.
Und da sagt man: eine Eigenschaft S ist entscheidbar, wenn für
die dazugehörige Menge der Kodierungen von TM, die eine Sprache
akzeptieren, die diese Eigenschaft hat (d.h.
[img]http://mokrates.de/cgi-bin/texstring?L_S%3D%5C%7Bw%5Cin%5CSigma%5E*%5Cmid%20L(M_w)%5Cin%20S%5C%7D[/img]), gilt: [img]http://mokrates.de/cgi-bin/texstring?L_S[/img] ist entscheidbar.

Edit: Der Satz sagt also auch nicht,
dass alle nichtleeren echten Teilmengen von Sigma*
unentscheidbar sind!

Was hier also höchstens ginge, wäre z.B. S als die Eigenschaft
"kontextfrei" zu wählen, d.h. [img]http://mokrates.de/cgi-bin/texstring?S%3D%5Cmathcal%7BC%7Df[/img],
aber das ist genauso unentscheidbar wie die anderen
Eigenschaften.

dann sehe ich keinen grund, warum in diesem fall die anwendung des beweisprinzips falsch wäre. aber dann wäre diese beliebige kontextfreie sprache automatisch unentscheidbar.

Die Stelle, an der es schief gehen würde, wäre gaaanz am Anfang.
Du müsstest nämlich, um den Beweis auf eine "entscheidbare
nichttriviale Eigenschaft" anzuwenden, erstmal eine finden. Und
das wird nicht klappen.

aber es ist bestimmt wichtiger, den satz verstanden zu haben, als das prinzip, wie er bewiesen wird [img]http://www.fb18.de/gfx/25.gif[/img]

Das sehe ich anders [img]http://www.fb18.de/gfx/17.gif[/img]

Sind jetzt alle Unklarheiten beseitigt? [img]http://www.fb18.de/gfx/23.gif[/img]

ah, ich glaube, ich hab es kapiert.
der beweis ist korrekt, weil es sich bei der menge ganz allgemein um irgendeine eigenschaft der aufzählbaren sprachen handelt.
würde ich das beweisprinzip auf eine ganz spezielle menge anwenden (z. b. die kontextfreie sprache L = {a^i | i ist eine primzahl}, die sogar entscheidbar wäre }, dann wäre der beweis nicht korrekt, weil ich eben keine allgemeine menge gewählt habe.

richtig?

(z. b. die kontextfreie sprache L = {a^i | i ist eine primzahl}

Nur um Irrtümern vorzubeugen: die Menge
L = {a^i | i ist eine Primzahl}
ist NICHT kontextfrei (!)

würde ich das beweisprinzip auf eine ganz spezielle menge anwenden (z. b. die kontextfreie sprache L = {a^i | i ist eine primzahl}, die sogar entscheidbar wäre }, dann wäre der beweis nicht korrekt, weil ich eben keine allgemeine menge gewählt habe.

Nein. S muss eine Eigenschaft und keine Sprache sein!
S darf keine Wörter enthalten! S ist eine Menge von Sprachen.

Und dass man den Begriff "entscheidbar" auf S anwenden kann,
liegt daran, dass Entscheidbarkeit nicht nur für Sprachen
sondern auch für Mengen von Sprachen eingeführt wurde. Wenn ich
jetzt definiere: Ein Auto heißt entscheidbar, wenn es vier Räder
hat, dann ist eine entscheidbare Sprache auch kein Gegenbeispiel
für den Satz: "Jedes entscheidbare Auto hat mindestens 3 Räder.".

Der Satz macht Aussagen über Eigenschaften von Sprachen.
Nicht über Sprachen. Das ist ein Unterschied wie zwischen
Tag und Nacht (oder besser: Tag und Woche). Das eine sind
Kästen mit Murmeln drin und das andere sind Kästen, die Kästen
enthalten, die wiederum Murmeln enthalten. Ein Beispiel für S wäre
[img]http://mokrates.de/cgi-bin/texstring?%5C%7B%5C%7Babc%2C%20abb%2C%20bbc%5C%7D%2C%20%5C%7Bjkl%5C%7D%2C%20%5Cemptyset%5C%7D[/img], aber nicht obiges L.

Dieses L kann garnicht für S gewählt werden, und zwar aus dem
gleichen Grund, aus dem man den Beweis nicht auf 27 oder 1/2
anwenden kann.

Ist dir der Unterschied jetzt klar?

Nachdem das geklärt ist: wenn du nun wirklich eine "nichttriviale
entscheidbare Eigenschaft von Sprachen" einsetzen willst,
findest du keine, weil es keine gibt. Und entscheidbare Sprachen
sind nicht erlaubt (weil sie keine Mengen von Sprachen sind)!

jo, danke nun kapiert.
hat zwar etwas lange gedauert, aber besser spät als nie [img]http://www.fb18.de/gfx/25.gif[/img]