Diskussion:Satz von Rice
Informationen und Beweis
Bitte noch mehr infos+Beweis hinzufügen, und vielleicht noch verständlich erklären, warum dies so ist. thx.
Satz-Aussage unklar?
Mit dem Satz von Rice kann nicht bewiesen werden, dass das Halteproblem nicht entscheidbar ist! Die Darstellung im Artikel ist falsch!
- Was soll falsch sein? Das Beispiel, dass man mit dem Satz von Rice zeigen kann, dass es nicht möglich zu entscheiden, ob eine Funktion total ist (also immer hält)? Das ähnelt dem Halteproblem nur und ist so richtig. Oder dass man, wenn der Satz von Rice nicht gelten würde, das Halteproblem lösen könnte? Das ist auch richtig und der einzige mir bekannte Beweis des Satzes von Rice. -- Tian 18:08, 28. Sep 2005 (CEST)
- ich denke, dass du falsch liegst. Du hast den Beweis verdreht. Der Satz von Rice besagt nämlich, dass jedes semantisch nichttriviale Entscheidungsproblem unentscheidbar ist (was ja in so ungefähr jedem informatik-buch steht). Dieser Satz lässt sich mittels Reduktion auf das Halteproblem EE-reduzieren. Der Beweis von Rice besagt, dass jedes nichttriviales Problem schwieriger ist als das Halteproblem. Dass das Halteproblem nicht rekursiv (somit nicht total) ist, kann man über die Diagonalsprache beweisen. --markus
- Auch wenns lange her ist, um das mal aufzuklären: Formal sind der Satz von Rice und die Unentscheidbarkeit des Halteproblems äquivalent. Der Beweis im Text folgert ja gerade das Erste aus dem Zweiten, die Umkehrung ist klar, da auf einer bestimmten Eingabe zu halten eine offenkundig nicht-triviale Eigenschaft von Turing-Maschinen ist. Aber in der Berechenbarkeitstheorie muss mensch die Unentscheidbarkeit von irgendwie anders zeigen, wie sonst sollte man den Satz von Rice folgern? Sobald für den Satz von Rice ein alternativer Beweis bekannt würde, könnte man die Beweiskette aber auch problemlos umkehren. -- 5.28.84.19 21:03, 9. Okt. 2013 (CEST)
- ich denke, dass du falsch liegst. Du hast den Beweis verdreht. Der Satz von Rice besagt nämlich, dass jedes semantisch nichttriviale Entscheidungsproblem unentscheidbar ist (was ja in so ungefähr jedem informatik-buch steht). Dieser Satz lässt sich mittels Reduktion auf das Halteproblem EE-reduzieren. Der Beweis von Rice besagt, dass jedes nichttriviales Problem schwieriger ist als das Halteproblem. Dass das Halteproblem nicht rekursiv (somit nicht total) ist, kann man über die Diagonalsprache beweisen. --markus
Verständnisfrage:
Wenn S eine Teilmenge von R ist und S nicht die leere Menge aber auch nicht R, wäre dann nicht S eine echte Teilmenge von R? Warum wird das dann nichttrivial genannt?
- Auch die leere Menge wird als echte Teilmenge bezeichnet, soll hier aber mit ausgeschlossen werden. Tian 22:59, 9. Okt. 2006 (CEST)
- Zum Glück ist Mathematik keine Religion. Nicht wie der unglückliche Kurt Gödel das Haushalten und Essen vergessen, wie manche Fernsehsüchtige vergessen den Müll rauszubringen. Viel Glück beim Bearbeiten des Artikels - ich verstehe Rice's Überlemma nicht.--84.157.242.85 18:07, 28. Jun. 2008 (CEST)
Scope of Rice
Im Artikel theoretische Informatik ist die Bedeutung von Rices Satz für meinen Geschmack nicht richtig klargestellt. Die Eineitung dieses Artikels gestattet dem Leser gedanklich Softwareverifikation für theoretisch möglich zu halten. Im theo. Inf. Artikel wurden die entsprechenden Aussagen gelöscht - obwohl es laut Heise-Newsticker für einen Wissenschaftler aus/in Texas dafür sowas wie den Turingpreis gab. Was meint ihr zu der verallgemeinerten Aussage mit dem Senkrecht-Operator? Ist Verfikation ein Gespenst das manchmal aus der Kiste kommt - oder gibt's solch ein Phänomen wirklich? e' * 1 = 1 = 1 * e" (Wort und Zahlenfunktion gehören unterschieden, wenn man nicht Georg Cantor heißt - er hätte auch so anfangen sollen - schicksal) --84.157.242.85 22:28, 28. Jun. 2008 (CEST) - Revision (Agent Smith)
Folgen in der Praxis
Wäre es nicht sinnvoll, ein paar praxisrelevante Folgen des Satzes aufzuschreiben? Mir fiele da z.B. ein, dass es unmöglich ist, die "Gut- oder Bösartigkeit" unbekannter Software algorithmisch festzustellen, siehe aktuelle Virenscanner-Debatte. :-) --RokerHRO 09:47, 13. Okt. 2011 (CEST)
Unpraezise Formulierung bei den Beispielen?
Die Aussage "Ebenso ist es nicht entscheidbar, ob eine Turingmaschine eine vorgegebene Funktion berechnet." gefaellt mir so nicht. Ich finde, es sollte heissen "... ist es im Allgemeinen nicht entscheidbar...". Man stelle sich nur als vorgegebene Funktion eine Funktion vor, die durch eine bekannte Turingmaschine definiert ist. Man kann zumindest feststellen, dass eben diese Turingmaschine die Funktion berechnet. Es ist ja "nur" nicht moeglich, das fuer jede Turingmaschine zu entscheiden. --Unixfan (Diskussion) 17:35, 27. Mär. 2013 (CET)
- Die Turingmaschine, für die man das überprüfen will, ist die Eingabe, ob die die Funktion berechnet, die Ausgabe. Dieses Problem ist nicht entscheidbar. „Im Allgemeinen“ klingt so, als gäbe es einzelne Funktionen oder einzelne TMs für die das entscheidbar wäre. Ersteres ist falsch, zweiteres macht keinen Sinn: Es geht um das Problem, bei dem eine beliebige TM gegeben ist. Das Problem, bei dem nur eine bestimmte TM akzeptiert wird und von der gesagt wird, ob die eine bestimmte Funktion berechnet, ist für jede TM und jede Fkt. entscheidbar. --Chricho ¹ ² ³ 17:44, 27. Mär. 2013 (CET)
- Ja, ich stimme prinzipiell zu. Vielleicht sollte ich mein Problem anders formulieren: Man kann doch so etwas wie partielle Entscheidungsalgorithmen finden, die nur auf eine Teilmenge der Kleeneschen Huelle angewendet werden koennen, oder? Kann sein, dass ich gerade total falsch liege, weil eventuell nicht entscheidbar ist, ob ein Algorithmus ein solcher partieller Entscheidungsalgorithmus ist.--Unixfan (Diskussion) 18:09, 27. Mär. 2013 (CET)
- Klar kann man das. Aber die von dir vorgeschlagene „im Allgemeinen“ Formulierung ist eben nicht gut, da sie falsche Dinge suggeriert. Die jetztige Formulierung scheint mir dagegen vertretbar: „Das Problem XY ist nicht entscheidbar“. Da meint man XY, und nicht XY eingeschränkt auf bestimmte Fälle. Aber mach einen besseren Vorschlag. --Chricho ¹ ² ³ 18:21, 27. Mär. 2013 (CET)
- Wie waere es mit: Ebenso ist nicht fuer jede Turingmaschine entscheidbar, ob sie eine vorgegebene Funktion berechnet.--Unixfan (Diskussion) 20:05, 27. Mär. 2013 (CET)
- Ne, birgt dasselbe Missverständnis. Für jede einzelne Turingmaschine ist dieses Problem nämlich durchaus entscheidbar – entweder mittels des Algorithmus, der 0 ausgibt, oder der 1 ausgibt. So kann man das zumindest leicht missverstehen. --Chricho ¹ ² ³ 20:19, 27. Mär. 2013 (CET)
- Du hast recht. Am besten bleibt es wie es ist, man sollte sich einfach selbst den exakt und schoen formulierten Satz anschauen und S={irgendein T-berechenbares f} setzen, dann ist die Aussage ja perfekt und wesentlich einfacher laesst es sich vermutlich nicht ausdruecken.--Unixfan (Diskussion) 20:37, 27. Mär. 2013 (CET)
- Ne, birgt dasselbe Missverständnis. Für jede einzelne Turingmaschine ist dieses Problem nämlich durchaus entscheidbar – entweder mittels des Algorithmus, der 0 ausgibt, oder der 1 ausgibt. So kann man das zumindest leicht missverstehen. --Chricho ¹ ² ³ 20:19, 27. Mär. 2013 (CET)
- Wie waere es mit: Ebenso ist nicht fuer jede Turingmaschine entscheidbar, ob sie eine vorgegebene Funktion berechnet.--Unixfan (Diskussion) 20:05, 27. Mär. 2013 (CET)
- Klar kann man das. Aber die von dir vorgeschlagene „im Allgemeinen“ Formulierung ist eben nicht gut, da sie falsche Dinge suggeriert. Die jetztige Formulierung scheint mir dagegen vertretbar: „Das Problem XY ist nicht entscheidbar“. Da meint man XY, und nicht XY eingeschränkt auf bestimmte Fälle. Aber mach einen besseren Vorschlag. --Chricho ¹ ² ³ 18:21, 27. Mär. 2013 (CET)
- Ja, ich stimme prinzipiell zu. Vielleicht sollte ich mein Problem anders formulieren: Man kann doch so etwas wie partielle Entscheidungsalgorithmen finden, die nur auf eine Teilmenge der Kleeneschen Huelle angewendet werden koennen, oder? Kann sein, dass ich gerade total falsch liege, weil eventuell nicht entscheidbar ist, ob ein Algorithmus ein solcher partieller Entscheidungsalgorithmus ist.--Unixfan (Diskussion) 18:09, 27. Mär. 2013 (CET)
semantisch nicht trivial = funktional
In https://www.youtube.com/watch?v=PCFyC-bNTvk&feature=youtu.be&t=14m28s wird der Begriff der "funktionalen Eigenschaft" statt "semantisch nicht-trivialer Eigenschaft" genutzt und auch erklärt, wie man solch eine Eigenschaft an zwei Merkmalen erkennt. Eventuell kann man dies hier mit einbauen/erwähnen, falls dies so Sinn macht, denn im Artikel wird nur auf "trivial" verwiesen und nicht genauer erklärt, wie dies (in diesem Fall) zu verstehen ist. --rugk (Diskussion) 22:39, 19. Jun. 2018 (CEST)
