| |
| Autor |
 (Co)-Semi-Berechenbarkeit von Sprachen beweisen |
|
mistersun
Neu 
Dabei seit: 18.12.2022
Mitteilungen: 3
 |  Themenstart: 2022-12-18
|
Hallo zusammen,
ich beschäftige mich momentan mit einigen Aufgaben zur (Co-)Semi-Entscheidbarkeit von Sprachen und bin dahingehend ein wenig überfordert was das generelle Verständnis angeht.
Konkret geht es um folgende Aufgaben und mich würde interessieren, ob meine Gedankengänge in die richtige Richtung gehen oder ob ich vollkommen "auf dem falschen Dampfer" bin. Alle Sprachen sollen auf (Co-)Semi-Entscheidbarkeit untersucht werden.
1.) Sprache \(L = \lbrace w \in \lbrace 0,1 \rbrace ^{*} | L(M_w) \cup \lbrace 0, 1\rbrace^{*} \neq \emptyset \rbrace \).
Zunächst dache ich, dass ich mittels Dovetailing zeigen könnte, dass die Sprache semi-entscheidbar ist. Meine Konstruktion wäre die folgende (ich hoffe, man versteht meine Erklärung): Es wird eine DTM M konstruiert, die ein Wort aus der Sprache L sucht und dann hält, wenn man es findet -> M hält also an, wenn L nicht leer (genau das, was man für Semi-Entscheidbarkeit will).
Man guckt sich daher alle Wörter \(w_i \in L\) an und simuliert für jedes i aus den natürlichen Zahlen i Berechnungsschritte. Da jedes dieser i endlich ist, stellt man so sicher, dass M nicht endlos läuft, wenn es ein Wort gibt, das nach endlich vielen Schritten akzeptiert wird.
Da meine Intuition mir sagst, dass L nicht entscheidbar ist, dürfte L ja folglich jetzt nicht noch co-semi-entscheidbar sein, oder? Weil dann könnte man ja beide konstruierten DTM gleichzeitig laufen lassen und hätte sowohl für die Ja-, als auch für die Nein-Instanzen eine Entscheidung. Wie könnte ich zeigen, dass die Sprache nicht co-semi-entscheidbar ist? Ich hatte an eine Reduktion gedacht, aber weiß nicht ganz genau, auf welches Problem ich reduzieren soll. Meine erste Idee war das Halteproblem.
2.) Sprache \(T = \lbrace w \in \lbrace 0,1 \rbrace ^{*} | M_w \text{berechnet } \chi \text{ einer nicht entscheidbaren Sprache} \rbrace\)
Hier habe ich ehrlich gesagt keinen richtigen Ansatz gefunden. Ich dachte eigentlich, dass es nicht möglich sein sollte, \(\chi\) bei einer unentscheidbaren Sprache zu berechnen. Schließlich fordert diese Funktion ja, dass immer entschieden wird, ob das Wort in der Sprache ist oder eben nicht.
3.) Sprache \(S = \lbrace w \in \lbrace 0,1 \rbrace ^{*} | \text{Anzahl der Zustände von } M_w > |L(M_w)| \rbrace \)
Hier hatte ich an eine Mehrband-DTM gedacht. Man könnte das ja so konstruieren, dass man auf einem Band die durchlaufenen Zustände "zählt" und auf dem anderen Band die Berechnung durchführt, oder? Im Anschluss kann man dann die gezählten Zustände mit der Mächtigkeit der Sprache vergleichen -> aber wie? Hier hört meine Idee schon wieder auf.
Vielen Dank bereits vorab, wenn sich das jemand durchliest und an der einen oder anderen Stelle Erleuchtung schenken könnte!
Mit freundlichen Grüßen!
|
 Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1422
Wohnort: Kiel, Deutschland
 | Beitrag No.1, eingetragen 2022-12-18
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Hallo mistersun, und willkommen auf dem Matheplaneten!
Zu der zweiten Sprache: dein Ansatz, dass es nicht möglich ist, die charakteristische Funktion einer nichtentscheidbaren Sprache zu berechnen, sollte dich dazu bringen, die Menge
\[T = \lbrace w \in \lbrace 0,1 \rbrace ^{*} \mid M_w\ \text{berechnet } \chi \text{ einer nicht entscheidbaren Sprache} \rbrace\]
radikal einfacher darzustellen.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
mistersun
Neu
Dabei seit: 18.12.2022
Mitteilungen: 3
| Beitrag No.2, vom Themenstarter, eingetragen 2022-12-19
|
Hallo thureduehrsen,
vielen Dank für deine Antwort!
Das hat mir sehr weitergeholfen, glaube ich. Wenn ich nämlich jetzt die Sprache als leere Menge darstellen kann (da die Menge an sich ja quasi ein Widerspruch ist), dann kann ich schauen, ob die leere Sprache (co-)semi-entscheidbar ist. Und da es sich bei der leeren Sprache quasi um das Komplement der ersten Sprache handelt, kann ich einfach meinen Beweis entsprechend anpassen und komme zu dem Ergebnis, dass die Sprache T co-semi-entscheidbar ist.
Das ergibt Sinn! Aber ich frage mich nach wie vor: wie zeige ich denn, dass die Sprache nicht(!) semi-entscheidbar ist?
Vielen Dank auf jeden Fall, ich bin schon mal einen gutes Stück weiter!
Mit freundlichen Grüßen!
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1422
Wohnort: Kiel, Deutschland
| Beitrag No.3, eingetragen 2022-12-19
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2022-12-19 11:08 - mistersun in Beitrag No. 2)
Wenn ich nämlich jetzt die Sprache als leere Menge darstellen kann (da die Menge an sich ja quasi ein Widerspruch ist), dann kann ich schauen, ob die leere Sprache (co-)semi-entscheidbar ist.
\quoteoff
Du meinst: die die Menge definierende Eigenschaft ist widersprüchlich. Aber ja, das ist der richtige Gedanke.
\quoteon Und da es sich bei der leeren Sprache quasi um das Komplement der ersten Sprache handelt,
\quoteoff
Wie? Meinst du \(\varnothing = \{0,1\}^\ast\setminus L\)? (Kann das überhaupt stimmen?)
Wenn nein, was meinst du dann?
\quoteon kann ich einfach meinen Beweis entsprechend anpassen und komme zu dem Ergebnis, dass die Sprache T co-semi-entscheidbar ist.
\quoteoff
Nicht so schnell. Meiner Meinung nach haben die Sprachen \(L\) und \(T\) nicht sehr viel miteinander zu tun. Die Sprache \(L\) ist auch recht speziell, finde ich. Steht das wirklich so in der Aufgabe,
\[
L = \lbrace w \in \lbrace 0,1 \rbrace ^{*} \mid L(M_w) \cup \lbrace 0, 1\rbrace^{*} \neq \emptyset \rbrace\quad?
\]
\quoteon Aber ich frage mich nach wie vor: wie zeige ich denn, dass die Sprache nicht(!) semi-entscheidbar ist?
\quoteoff
Du könntest mit Reduktionen arbeiten.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
mistersun
Neu
Dabei seit: 18.12.2022
Mitteilungen: 3
| Beitrag No.4, vom Themenstarter, eingetragen 2022-12-19
|
Hallo noch mal!
Super, dann bin ich da schon mal einen großen Schritt weiter. 😊
Was ich meinte, war folgendes: Ich kann die Semi-Entscheidbarkeit von L zeigen, indem ich beweise, dass L nicht leer ist. Wie ich das mache, hab ich ja im Ursprungspost versucht, zu erklären (ob das so valide ist, weiß ich nicht genau, aber es ergibt (jedenfalls für mich 😉) Sinn. Jetzt muss ich mich ja um T kümmern. T ist ja, wie ich dank deinem Hinweis erkannt hab, die leere Menge. Also muss ich zeigen:
\(T = \emptsyset\) ist (co-)semi-entscheidbar. Ich weiß, dass eine nicht-leere Sprache (nämlich L) semi-entscheidbar ist. Wenn ich dann meine DTM so konstruiere, dass alle Ja-Instanzen von L nicht mehr akzeptiert werden, und alle Nein-Instanzen schon, dann hab ich doch gezeigt, dass T co-semi-entscheidbar ist. Oder?
Beim Abtippen von L ist mir tatsächlich ein Fehler unterlaufen - sorry. Es müsste nicht die Vereinigung, sondern der Schnitt da stehen. Macht es mMn aber nicht weniger kompliziert😁 Aber mein Ansatz bliebe tatsächlich derselbe.
Hättest du bzgl. der Reduktion vielleicht einen Tipp, wie ich das passende Problem auswähle, auf das ich reduzieren kann? Da tue ich mich sehr schwer. Ich kenne das spezielle oder das allgemeine Halteproblem (da beide unerfüllbar sind, ist es vielleicht eine gute Idee?) oder das Posttasche Korrespondenzproblem. Aber wie ich letzteres in diesem Fall anwenden soll, weiß ich ehrlich gesagt auch nicht. 🤔
Mit freundlichen Grüßen!
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1422
Wohnort: Kiel, Deutschland
| Beitrag No.5, eingetragen 2022-12-20
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2022-12-19 21:53 - mistersun in Beitrag No. 4)
Ich kann die Semi-Entscheidbarkeit von L zeigen, indem ich beweise, dass L nicht leer ist.
\quoteoff
Du musst für Semi-Entscheidbarkeit aber zeigen, dass deine TM auf allen Wörten aus \(L\) hält; es reicht nicht, wenn sie nur auf einigen Wörtern aus \(L\) hält und auf anderen Wörtern, die in \(L\) liegen, endlos läuft.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
tetriscyphervalo
Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 42
| Beitrag No.6, eingetragen 2023-01-02
|
Kann es sein, dass dein L noch nicht korrekt definiert ist, hinsichtlich der Schnittmenge mit $\{0,1\}^*$?
Zu 3.: Ich behaupte mal, dass die Sprache nicht entscheidbar ist, denn um zu prüfen, ob eine $w \in S $ gilt, muss man theoretisch gesehen, unendlich viele Wörter $t \in \Sigma^*$ testen, um entscheiden zu können, ob nun die kodierte Turing Maschine $M_w$ weniger Wörter $t$ akzeptiert, als es Zustände hat. Also existiert insbesondere keine DTM, und ist nicht semi-entscheidbar.
Zur co-semi-entscheidbarkeit kannst du dir Analog die Gedanken zu machen.
Btw. bin selbst nur ein Student. Gerne Verbessern, falls ich falsch mit meinem Beitrag liege.
|
Profil
|
Alex1234
Neu 
Dabei seit: 03.01.2023
Mitteilungen: 1
| Beitrag No.7, eingetragen 2023-01-03
|
\quoteon(2022-12-19 11:08 - mistersun in Beitrag No. 2)
...komme zu dem Ergebnis, dass die Sprache T co-semi-entscheidbar ist..
\quoteoff
Ich habe hier ne Frage zu. Wieso kann die leere Sprache denn nicht auch semi-entscheidbar sein. Du sagst hier nur, dass sie co-semi-entscheidbar ist.
Ich war der Meinung, dass die leere Sprache, als auch das Komplement, semi-entscheidbar ist.
PS: Bin nur Student und das ist mehr als Frage gemeint.😵
|
Profil
|
tetriscyphervalo
Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 42
| Beitrag No.8, eingetragen 2023-01-03
|
\quoteon(2023-01-03 15:15 - Alex1234 in Beitrag No. 7)
Ich habe hier ne Frage zu. Wieso kann die leere Sprache denn nicht auch semi-entscheidbar sein. Du sagst hier nur, dass sie co-semi-entscheidbar ist.
Ich war der Meinung, dass die leere Sprache, als auch das Komplement, semi-entscheidbar ist.
PS: Bin nur Student und das ist mehr als Frage gemeint.😵
\quoteoff
Stimme dir in beiden Fällen zu.
|
Profil
|
| mistersun hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
