Satz v. Rice: nicht-triviale Eigenschaft



  • Hallo, ich bins mal wieder.
    Was genau versteht man unter einer "nicht-trivialen Eigenschaft" bzgl. des Satz von Rice?

    Wikipedia und googlen haben mir irgendwie nicht ganz geholfen, das verständlichste was ich finden konnte war
    "Nichttrivial: Es gibt Turing-erkennbare Sprachen, die sie erfüllen, aber nicht alle Turing-erkennbaren Sprachen erfüllen sie."
    Aber auch das leuchtet mir nicht ein...
    Kann mir das wer simpel erläutern?

    Dann habe ich noch eine Frage bei der ich mir nicht ganz sicher bin. Was genau bedeutet <M> bzgl. einer Turing-Maschine M. Wir haben das glaube ich folgendermassen definiert:
    "Jede Turingmaschine kann man als Wort kodieren....Wir notieren diese Kodierung mit <M>"
    Ich verstehe aber nicht den Unterschied zwischen M und <M>?! Oft steht in der Aufgabe sowas wie
    {<M> | L(M) ... }
    Heisst das einfach "Wir haben eine Turing-Maschine M, für die Sprache die von M erkannt wird gilt..."?
    <M, w> heisst dann "M mit Eingabe w"?

    Danke schonmal.



  • Es ist also mal wieder Zeit fuer Klausuren in Theoretischer Informatik ...

    Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none

    Also sowas aehnliches wie: Sei x eine natuerliche Zahl mit der Eigenschaft groesser gleich -5.

    M und <M>

    Nach deiner Definition ist M die Turingmaschine und <M> deren Repraesentation. Genau wie die Zahl 5 hat sie einen Wert und eben eine Repraesentation. Das Wort "Rucksack" hat eine Bedeutung und eben die Repareasenation bestehend aus der Zeichenkette R-u-c-k-s-a-c-k, jeder einzelne Buchstabe hat auch eine Bedeutung und eine Repraesentation. Im Alltag bringt diese Unterscheidung aber nichts.

    <M, w>

    Nun, es handelt sich um eine Repraesentation von M in Kombination von w.



  • Ok, die zweite Hälfte deines Beitrages hat mir schonmal sehr geholfen, danke 😉
    Und ja, mal wieder Zeit für ne Klausur...

    Was nun genau eine triviale Eigenschaft ist ist mir aber immernoch nicht ganz klar. Also das x>=-5 dazu gehoert kann ich mir denken, aber das hilft mir leider nicht sonderlich weiter 😉



  • Eigentlich steht da schon alles was zu den nichttrivialen Eigenschaften zu sagen ist. Ich fürchte Du hast es nur überlesen. Also nochmal:

    Eine Eigenschaft ist trivial, wenn sie entweder a) für jede berechenbare partielle Funktion gilt oder b) für keine partielle berechnbare Funktion gilt. Du siehst, diese Eigenschaften sind trivial in dem Sinne, dass sie Dir keinerlei Möglichkeit bieten Informationen über zwei partielle berechenbare Funktionen irgendwelche Informationen zu gewinnen. Im Gegenzug ist eine Eigenschaft nicht-trivial, wenn sie nicht trivial ist (genial oder?). Wendet man die Negation auf die beiden obigen Aussagen an, so heißt das nichts anderes als "es gibt zwei partielle berechenbare Funktionen f_1 und f_2, sodass die Eigenschaft für f_1 gilt und für f_2 nicht."

    Oder, wie knivil es zitiert hat: Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none



  • Ok, also angenommen es geht darum zu zeigen dass diese Aussage falsch ist:
    http://gyazo.com/f09d701fbdc0450c3382d5cba0968192.png

    Dann sage ich "es gibt Sprachen die Co-Aufzählbar sind und welche die es nicht sind, daher ist 'L(M) aus A^co' nicht trivial und aufgrund des Satzes von Rice ist die Aussage somit nicht entscheidbar."?

    Danke soweit.



  • Und ich muss leider doch nochmal fragen, damit ich es (hoffentlich) 100% richtig verstehe.
    Was genau macht diese TM?
    http://gyazo.com/e56dd301626d90d2f90835fac32d812a.png
    Also in Worten beschrieben. "Wir haben eine TM die nennen wir REG. Die Sprachen die durch diese TM erkennt sind regulär." Richtig so? Mich verwirrt hier immernoch das <M> 😕



  • Wir haben eine Menge, die nennen wir REGTMREG_{TM}.
    Die Menge enthält alle codierten Turingmaschinen* (<M><M>) mit der Eigenschaft, dass die Sprache der Turingmaschinen(L(M)L(M)) aus den Regulären Sprachen (REGΣ\in REG_{\Sigma}) ist (Typ-3 in der Chomsky-Hierarchie).
    Mit dem E kann ich so ohne Zusammenhang erstmal nix anfangen. (Eigenscahften im Sinne von Anforderungen im Bezug auf den Satz von Reis vielleicht?! 😕 )

    * ich werfe an der Stelle einfach mal das Stichwort Gödelisierung in den Raum



  • Ok, danke, glaube es hat nun endlich klick gemacht. Das E steht für entscheidbar.
    Könnte dann schlussendlich nochmal wer was zu meinem vorletzten Post sagen?

    Danke vielmals 😉



  • Turingmaschinen arbeiten mit einem Alphabet, das sie in die einzelnen Zellen des Bandes schreiben/auslesen können. Wenn grob gesagt eine TM eine andere TM "untersuchen" soll muss vorher die zu untersuchende TM in eine Codierung verwandelt werden, so dass die untersuchende TM ihre Eingabe versteht.

    <M> ist einfach nur die Kodierung von M. Steht bestimmt irgendwo in deinen Skript. Stichwort: Gödelisierung.



  • Nagut, danke nochmal allen, ich mache mich mal auf den Weg zur Klausur 😉


Log in to reply