ฝัง
- เผยแพร่เมื่อ 8 พ.ย. 2024
- Um den Satz von Rice anwenden zu können, sehen wir uns verschiedene Eigenschaften von Turingmaschinen (DTMs) an und besprechen für jede dieser Eigenschaften, ob sie semantisch und ob sie trivial ist. Der Satz von Rice kann nämlich nur angewendet werden für Eigenschaften, die semantisch und nicht-trivial sind.
![Aufgaben zu Entscheidbarkeit und Satz von Rice [Klausuraufgaben Berechenbarkeit #03]](http://i.ytimg.com/vi/jpbGGNbpYzM/mqdefault.jpg)
![Aufgaben zu Unentscheidbarkeit und Satz von Rice [Klausuraufgaben Berechenbarkeit #04]](/img/n.gif)
Top, gutes video. Ich hoffe ich besteh die bka klausur nächsten montag
super videos danke!
Sehr gutes Video.
#DankeDoctorNLogSpace
10:52
Ich habe eine Frage zur Aussage, dass "M hält auf epsilon" nicht semantisch sei.
Bei uns an der Uni wird Rice von einer anderen Seite angegangen, die wahrscheinlich letztlich doch aufs selbe hinausläuft (... vermute ich jedenfalls ...). Wir fragen uns bei "semantisch" nicht, ob es um die von einer TM erkannte Sprache, sondern ob es um eine (Maschinen-unabhängige) Eigenschaft der von der TM berechneten Funktion geht.
"Hält M auf epsilon" an wäre gleichbedeutend mit "Ist die von M berechnete Funktion für die leere Eingabe definiert". Dies wäre nach unserer Definition durchaus eine semantische Eigenschaft einer TM und damit das Problem nach Rice unentscheidbar.
Kannnst du mir kurz sagen, ob das so Sinn ergibt? Danke!!
Ja, das ergibt Sinn! Man kann den Satz von Rice einerseits für formale Sprachen formulieren (so wie ich das in den Videos gemacht habe), andererseits auch für die berechneten Funktionen. Im zweiten Fall interpretiert man eine Endlosschleife nicht als Verwerfen, sondern als undefinierten Ausgabewert, sodass Nicht-Anhalten äquivalent ist zu undefiniertem Ausgabewert. Wie Du richtig beschreibst, ist das dann eine semantische Eigenschaft.
@@NLogSpace Cool, danke!
Hallo, ich habe dein Video geschaut und finde verständlich. Was du erzählst, funktioniert auch bei Aufgabelösen bis ich diese Aufgabe konfrontiere: N = { p | p ist ganzzahliges Polynom über x mit ganzzahliger Nullstelle}, ist die Sprache N entscheidbar?
ich dachte es wäre eindeutig eine semantische und nicht triviale Eigenschaft, somit könnte man Satz der Rice anwenden. Aber erstaunlicherweise ist die Sprache sogar entscheidbar? Wo hat diese Sprache die Voraussetzungen von Satz der Rice verletzt?
Der Satz von Rice spricht über Turingmaschinen, er kann also nur auf Sprachen der Form {code(M) | M ist eine DTM mit Eigenschaft .....} angewendet werden.
@@NLogSpace Kann man es in diesem Fall als "M ist eine DTM, die ganzzahliges Polynom über x mit ganzzahliger Nullstelle akzeptiert" umformulieren?
@@pupus3531das fehlt dass das es codiert werden können muss vielleicht
Ist eine Rechtsdrall-Turingmaschine zu sein eine semantische Eigenschaft?
Ich glaube, man kann mit einem Trick für das Problem "M überschreibt ein blanc bei Eingabe abba" Rice anwenden: Man nehme eine universelle TM .die als eingabe #abba bekommt und ein zusätzliches Feature eingbaut hat. Die UTM simuliert die berechnung von M und sobald ein blanc überschrieben wird, akzeptiert sie die Eingabe. Wenn M terminiert und kein blanc überschrieben wurde, wird die Eingabe von der UTM nicht akzeptiert. Damit ist die Frage, ob ein blanc überschrieben wurde, eine nihttriviale semantische Eigenschaft der UTM
👍
Hallo, ich verstehe nicht, warum "Hält M auf Eingabe epsilon an?" keine semantische Eigenschaft ist. Man kann das doch umformulieren zu "Enthält L(M) das leere Wort?" und somit ist es ja eine Eigenschaft, die nur die Sprache betrifft, oder?. Und die beiden TM, die Du als Beispiel gegeben hast unterscheiden sich in der von ihnen erkannten Sprache ja genau darin: die linke erkennt das leere Wort, die rechte nicht, daher denke ich dass sie nicht die gleiche Sprache erkennen - wo liegt mein Denkfehler?
Nein, die beiden DTMs dort erkennen die gleiche Sprache, nämlich die leere Sprache. Das liegt daran, dass der Zustand nicht als akzeptierender Zustand ausgezeichnet ist. Somit habem wir zwei DTMs die die gleiche Sprache erkennen, aber eine erfüllt die Eigenschaft und die andere nicht. Daher ist es keine semantische Eigenschaft.
@@NLogSpace Ah okay verstanden, danke
Es ist zwar keine semantische Eigenschaft, es gibt aber einen Trick, daraus eine zu machen: Man bastelt sich aus der Turing Maschine M ein Turing Maschine u(M) , die fast genauso aussieht wie M mit dem Unterschied, das jeder terminierende Zustand auch ein akzeptierender ist. Dann gilt M hält bei Eingabe x an gdw. x ist in L(u(M)) , womit das eine sematische Eigenschaft von u(M) ist.
Außerdem was ist mitnehmen epsilon halteproblem passiert
Brauche Ihre Hilfe Doctor NLogSpace.
L3 = {M M' | es gibt ein Wort, das sowohl von M als auch von M' akzeptiert wird}.
Verstehe, dass eine Reduktion auf das HP sein muss, aber habe Probleme mit der Reduktion selbst. Welche Idee für die Reduktion?
Wahrscheinlich steckt man zwei TM nacheinander und die zweite wird TM, die HP löst?
Wozu HP? das geht besser mit Rice