Entscheidbar, unentscheidbar, semi-entscheidbar?
Вставка
- Опубліковано 5 чер 2015
- Wir sehen uns eine intuitive Beschreibung der Begriffe "entscheidbar", "unentscheidbar" und "semi-entscheidbar" aus der theoretischen Informatik an. Diese werden zu Klassifikation von Entscheidungsproblemen benutzt.
Super erklärt und tolle einfache Bilder. Danke!
Nach 50Seiten Hopcroft, Motwani und Ullman hatte ich es nicht verstanden, aber hier ist der Groschen gefallen :D Danke
Ich kann den Sipser empfehlen: notendur.hi.is/mae46/Haskolinn/5.%20misseri%20-%20Haust%202018/Formleg%20mál%20og%20reiknanleiki/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf
willst du nicht meinen Dozenten ersetzen? Der bekommt nichts auf die Reihe.
Sehr gute Videos! Endlich kapier ich das Thema :D
Bumsfidelus Vielen Dank, es freut mich, dass es hilft!
Ohhh mein gott danke. Allein bei minute 4:00 hats schon klick gemacht und mein skript macht wieder sinn. Ehrenmann
echt gutes video. Die bilder helfen beim verständnis und deine stimme ist angenehm und klar verständlich. danke dafür
Dankedankedanke! Mega gut erklärt
Wann kommen den ungefähr die nächsten Videos? :)
Wenn ich Zeit habe und schlechtes Wetter ist. :D
Danke fur alles.
Hi Leif, danke dass du diese Videos machst! Ich hab wieder mal eine Frage und zwar komme ich einfach nicht darauf ob die folgende Sprache semi entscheidbar ist: { | M eine TM und L(M) ist entscheidbar}. Also in Worten: Ob die Sprache der Beschreibungen von Turingmaschinen, deren akzeptierte Sprache entscheidbar ist, selbst semi entscheidbar ist. Die Sprache ist wohl nicht entscheidbar, da man dies mit Satz von Rice recht einfach begründen kann, aber über die Semi-Entscheidbarkeit gelingt es mir keine Aussage zu beweisen. Eine intuitive Begründung hab ich mir allerdings überlegt, dass die Sprache vermutlich nicht semi entscheidbar sein kann: Es kann wohl nicht möglich sein, einen Algorithmus zu finden (selbst wenn der nicht terminieren muss) um zu bestimmen, ob es für eine vorgegebene TM eine TM gibt, die hält und dieselbe Sprache akzeptiert, weil nach endlicher Laufzeit kann man nicht mal mit Sicherheit wissen, was die von der TM akzeptierte Sprache so genau ist.
Hey,
schöne Frage und nicht ganz einfach! Habe mit Kollegen darüber geredet und die Antwort ist: Sei L die besagte Sprache. L ist weder semi-entscheidbar noch ist ihr Komplement semi-entscheidbar. Aus dem Satz von Rice folgt sofort, dass die Sprache unentscheidbar ist, und wenn man den Beweis analysiert folgt auch, dass sie nicht semi-entscheidbar ist, denn dort reduziert man vom Komplement des Halteproblems auf L.
Man kann auch vom Halteproblem auf L reduzieren: Wir müssen als eine Eingabe für das Halteproblem in eine Eingabe = n, d.h. nur endlich viele Worte werden nicht akzeptiert. Diese Sprache ist offensichtlich entscheidbar, also ist dann eine Nein-Instanz von L.
Herzlichen Dank für dein tolles Video!
Könntest du vielleicht auch ein Video machen zu den Begriffen "rekursive" , und "rekursiv aufzählbar", und wie diese mit den Begriffen Entscheidbar, Unentscheidbar, Semi-entscheidbar in Verbindung stehen, machen?
Weiters würde mich interessieren was mit dem Begriff "Reduktion" genau gemeint ist und wie dieser Begriff dann in Verbindung steht bzgl der Begriffe entscheidbar, unentscheidbar, semi-entscheidbar, rekursiv und rekursiv aufzählbar.
(z.B A
+Harald Weillechner Vielen Dank für den Kommentar! Ich habe fest vor, zu den genannten Themen Videos aufzunehmen. Es könnte allerdings noch etwas dauern, bis ich die Zeit dafür finde.
Etwas zu primitiv-rekursiven und u-rekursiven Funktionen in dieser grossartigen Weise erklärt wäre echt super! Also nicht dass ich mir wünsche, dass das Wetter schlecht wird.. ;)
Richtig gut
Die Gleichung ist ein sehr nettes und anschauliches Beispiel, jedoch ist es irgendwie evident, dass man nach einer konkreten natürlichen Zahl spätestens aufhören kann, da n! bzw. n^n wesentlich schneller ansteigt als 3^n bzw. polynomielle Funktionen.
Ja, also diese konkrete Gleichung ist vielleicht kein gutes Beispiel, aber wenn das Problem eine beliebige Gleichung als Eingabe bekommt, dann gibt es zunächst einmal keine klare Abbruchbedingung.
Servus, wie man Begriff "rekusiv Aufzählbar" definieren kann? Ist das Semi-entscheidbar? Ich kann das nicht so ganz verstehen.
Danke für deine Videos! :)
Also der Begriff "rekursiv aufzählbar" ist so definiert: Eine Sprache L ist rekursiv aufzählbar, wenn es eine DTM gibt, die, wenn man sie auf der leeren Eingabe startet, nach und nach alle Wörter aus L ausgibt. Dabei stellt man sich vor, dass die DTM einen speziellen "Aufzählzustand" hat und jedes Mal wenn sie diesen erreicht, wird der aktuelle Bandinhalt ausgegeben. Es stellt sich aber heraus, dass "semi-entscheidbar" und "rekursiv aufzählbar" äquivalent zueinander sind, das heißt man kann beweisen, dass jede semi-entscheidbare Sprache rekursiv aufzählbar ist und dass jede rekursiv aufzählbare Sprache semi-entscheidbar ist.
@@NLogSpace Das Halteproblem ist ja unentscheidbar und rekursiv aufzählbar. Wie ist hier die äqvivalenz zwischen rekursiv aufzählbar und semi-entscheidbar zu betrachten? Oder schließt sich unentscheidbar und semi-entscheidbar nicht aus?
Letzteres ist der Fall, unentscheidbar und semi-entscheidbar schließen sich nicht gegenseitig aus. Und das HP ist beides.
Hallo, bin ich im Fach "Theoretische Informatik" stecken geblieben. Ich bräuchte Hilfe bei DEAs/NEAs/Kellerautomaten und Turingmaschinen d.h. jemand, der Coach ist oder Nachhilfe im Bereich gibt? (Die Theorie habe ich viele Male durchgearbeitet, brauche aber Übungen und jemanden zur Seite, um zu sehen was ich falsche mache). An wen könnte ich mich da am besten wenden?
Wo hast du studiert/Wo studiertst du?
+TimoDJatomika In Bremen.
Also mir wurde gesagt, dass bei semi-entscheidbare Problemen entweder x elem. von L oder undefiniert ausgegeben wird. Wenn nun auch das Komplement von L semi-entscheidbar ist, warum folgt daraus, dass L entscheidbar ist? Kann es keine Schnittmenge geben, die undefiniert ist, also über deren Elemente wir keine Aussage treffen können?
P.S. Deine Videos im Allgemeinen sind unheimlich nützlich.
Kurze frage hatte bei einer klausur die frage ist das halteproblem berechenbar ja oder nein ?
adam khalil "Berechenbar" ist ein Begriff für Funktionen, d.h. der Begriff passt nicht so gut für Entscheidungsprobleme wie das Halteproblem. Falls du Entscheidbarkeit meinst: Das Halteproblem ist nicht entscheidbar, d.h. es gibt keinen Algorithmus, der für jede Eingabe des Halteproblems nach endlicher Zeit die richtige Antwort gibt. Dazu habe ich auch ein Video auf meinem Kanal!
Leifaktor
Danke für die schnelle antwort :)
Die antwort möglichkeiten waren nicht berechenbar und nicht berechenbar, fand die antwortmöglichkeiten komisch aber, ist schwer berechenbsr falsch als antwort 😅
ich beziehe mich jetzt auf die letzten 30 sek. Hast du ein Beispiel für ein Problem, das unentscheidbar und semi-entscheidbar ist?
+AC Doyouknow Genau diese Frage habe ich dort auch beantwortet: Das Halteproblem ist ein solches Problem. Zum Halteproblem habe ich auch nochmal ein eigenes Video. Ein anderes Problem, das unentscheidbar, aber semi-entscheidbar ist, ist z.B. das "Postsche Korrespondenzproblem".
Leifaktor Ahh dankeschön. Ja das PCP habe ich gerade auch schon gefunden. Beim Halteproblem war ich mir igendwann nicht mehr sicher.
Und unentscheidbar\semi-entscheidbar sind Probleme mit super-exponentiellen Laufzeiten wie busy beaver? Oder bin ich da nun in die falsche Schublade gehüpft?
Busy Beaver ist ebenfalls ein unentscheidbares Problem, das Halteproblem steckt auch dort quasi mit drin: Wenn man wissen möchte, ob eine Biber-Maschine eine gewisse Anzahl Einsen erzeugt und dann anhält, so muss man ja auch herausfinden, ob die Maschine überhaupt anhält.
Bzgl. "Super-exponentieller Aufwand": Das ist nicht ganz richtig. Für unentscheidbare Probleme gibt es gar keinen Algorithmus, also auch keinen mit super-exponentieller Laufzeit. Sie sind also noch schwieriger als solche Probleme, die man in exponentieller oder super-exponentieller Zeit lösen kann.
Das Halteproblem ist doch Semientscheidbar oder? Ich kann jedes Programm mit einer Turing Maschine simulieren und wenn es anhält "ja" sagen und wenn nicht dann hält es eben nie an und ist somit Semientscheidbar.
BlauerTeeTec Richtig!
Was, wenn man das Halteproblem so formuliert: "Läuft das Programm P auf Eingabe E endlos weiter?" dann würde es evtl. irgendwann terminieren, aber mit Antwort false. Und falls das Programm endlos weiter läuft, terminiert es nicht. Nennt man das auch semi-entscheidbar? Allerdings terminiert es ja nicht bei wahr sondern bei falsch, genau entgegen der Definition...
Das wäre dann nicht semi-entscheidbar, denn es kommt wirklich darauf an, dass das Programm bei den Ja-Instanzen terminiert. Das Komplement vom Halteproblem, das Du beschrieben hast, könnte man "co-semi-entscheidbar" nennen.
Das Entscheidungsverfahren, muss das nicht deterministisch sein?
Ja, die (Semi-)Entscheidungsverfahren hier sind alle deterministisch.
bester mann
Gutes Video! Warum wird eigentlich so viel auf semi-entscheidbaren Entscheidungsproblemen rumgeritten während semi-berechenbare Funktionen kaum erwähnt werden?
Das ist eine gute Frage, die man sich selbst beantworten kann. Tipp: Bei Entscheidungsproblemen gibt es nur zwei mögliche Ausgabe (ja/nein). Bei Funktionen kann es sehr viele mögliche Antworten geben.
@@NLogSpace Meinst du dass ein Semi-Entscheidungsverfahren eher nützlich ist als ein Semi-Berechnungsverfahren? Bei ersterem kann man "nein" raten wenn lange kein "ja" kommt, bei letzterem kann man alles mögliche raten.
Ich meine, dass gar nicht klar ist, was ein Semi-Berechnungsverfahren überhaupt sein soll. Wenn es um Entscheidungsprobleme geht, ist es klar: Ein Algorithmus, der bei Ja-Instanzen die Antwort nach endlicher Zeit findet und bei Nein-Instanzen nicht unbedingt. Aber bei einer Funktion mit vielen möglichen Ausgabewerten? Auf welchen Eingaben soll der Algorithmus den Funktionswert nach endlicher Zeit berechnen?
@@NLogSpace Na auf Eingaben für die die Funktion berechenbar ist, oder? Bei anderen Eingaben läuft der Algorithmus dann ewig. Wenn der Algorithmus etwas zurück gibt weiß man dass das für die jeweilige Eingabe das Ergebnis ist, wenn es dagegen kein Ergebnis gibt erfährt man das nie.
Eine Funktion ist nicht auf einigen Eingaben berechenbar und auf anderen Eingabe nicht. Eine Funktion ist eine Zuordnung, die für jede Eingabe spezifiziert, was die Ausgabe ist. Die Funktion ist entweder berechenbar (=Es gibt einen Algorithmus, der auf allen Eingaben die richtige Ausgabe liefert.) oder nicht (=Es gibt keinen Algorithmus, der auf allen EIngaben die richtige Ausgabe liefert). Wenn die Funktion nicht berechenbar ist, heißt das aber nicht, dass das an einzelnen bestimmten Eingaben liegt. Egal welche Eingabe für die Funktion man betrachtet, es gibt immer einen Algorithmus, der für diese Eingabe das richtige Ergebnis liefert. Wenn z.B. festgelegt ist, dass f(4815) = 162342 ist, dann gibt es einen Algorithmus, das für diese Eingabe das richtige Ergebnis liefert. Aber dieser Algorithmus liefert dann vielleicht auf anderen Eingaben nicht das richtige Ergebnis. Während bei Entscheidungsproblemen die Unterteilung des Definitionsbereichs klar ist (Ja-Instanzen versus Nein-Instanzen), gibt es bei Funktionen erstmal keine natürliche Art, den Definitionsbereich aufzuteilen.
Aber müsste nach deiner gegeben Definition nicht auch das Halteproblem semi-entscheidbar sein? Man kann die Eingabe ja einfach dem Programm geben und falls die Antwort "ja" lautet, endet der Algorithmus in endlicher Zeit und bei "nein", läuft das Programm endlos weiter. War nicht genau das deine Definition eines semi-entscheidbaren problems?
RIchtig. Genau das sage ich auch am Ende des Video (14:30).
Ist das Halteproblem nicht auch semi-entscheidbar? Man kann doch das Programm einfach laufen lassen - wenn es stoppt, bekommen wir eine Antwort, und andernfalls läuft es ewig weiter?
mrtn Völlig richtig!
Aber diese gleichung muss ja entscheidbar sein, immerhin ist n^2n größer als wie 3^n + n^7 wenn man die onotation hernimmt.
wenn man dann darüber ist muss man nciht weiter probieren.
ich sehe gerade das war schonmal wo in den kommentaren
@@tonikaiser2823 Genau, also das Beispiel ist nicht gut gewählt. Aber sollte ja nur verdeutlichen, was ein Semi-Entscheidungsalgorithmus ist. Ehrlich gesagt weiß ich nicht, ob dieses Problem entscheidbar ist oder nicht, wenn man eine beliebige Gleichung als Eingabe bekommt. Aber ein etwas generelleres Problem, bei dem man ein Gleichungssystem mit mehreren Gleichungen als Eingabe hat, ist unentscheidbar: de.wikipedia.org/wiki/Diophantische_Gleichung
Das Video hilft gut, macht aber das Thema nicht wirklich einfacher, weil du ( durchaus bewusst ) ja nicht auf die Formalismen eingehst. :x
Trotzdem danke!
Kurzes Klugscheißen hier:
Wenn du das Programm nach dem kürzesten Weg in einem Graphen suchen lässt, ist die Ausgabe des Programms im Optimalfall nicht die Länge des kürzesten Weges, sondern die Kantenfolge, die den kürzesten Weg darstellt.
8:36 no shit Sherlock o.O