Die Mathe-Redaktion - 23.08.2019 13:35 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 483 Gäste und 20 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Sind folgende Sprachen entscheidbar? (u.a. Satz von Rice)
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Sind folgende Sprachen entscheidbar? (u.a. Satz von Rice)
felix_macht_mathe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 19.01.2016
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-18


Hallo zusammen,

ich muss folgende Aufgaben lösen, und sagen, ob die Sprachen entscheidbar, semi-entscheidbar oder co-semi-entscheidbar sind.

\(L = \{ \langle M \rangle | L (M) = \{0,1\} \} \)
Rein vom Gefühl her wäre die Sprache entscheidbar, aber irgendwie passt der Satz von Rice; die Eigenschaft ist ja semantisch, und doch auch nicht trivial, wenn ich das richtige verstehe  :-? Es gibt ja sowohl eine TM, die eben nur L(M) = {0,1} beschreibt, aber auch eine TM, die \(Sigma^* \) \ {0,1} beschreibt?

\(L = \{ \langle M \rangle | L (M)\) enthält keine zwei Wörter mit identischer Länge }
Wäre für mich co-semi-entscheidbar, da es ja semi-entscheidbar ist ob eine Sprache nur Wörter der selben Länge hat.

\( L = \{\langle M\rangle | L(M)\) enthält die ersten 42 binärkodierten Quadratzahlen}
Wäre vom Gefühl her ebenfalls durch den Satz von Rice nicht entscheidbar.

Wie ihr seht, ist bei mir der Groschen noch nicht so richtig gefallen...
Vielen Dank für Eure Hilfe.

Felix



  Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1943
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-18


Hallo Felix,

Deine Aussagen, dass die erste und die dritte Sprache nach dem Satz von Rice nicht entscheidbar seien und die zweite co-semi-entscheidbar ist, stimmen schon mal.  smile

Noch zwei Kommentare von mir zu Deinen Begründungen:

Es gibt ja sowohl eine TM, die eben nur L(M) = {0,1} beschreibt, aber auch eine TM, die Sigma∗ \ {0,1} beschreibt?

Das ist zwar als Begründung für die Nichttrivialität der Menge korrekt, allerdings würde für den zweiten Teil auch reichen, irgendeine Maschine zu nehmen, die nicht <math>\{0,1\}</math> erkennt (zum Beispiel eine, die nie hält). Die Sprache <math>\Sigma^\ast \setminus \{0,1\}</math> spielt hier keine Sonderrolle. Wie gesagt, ich erwähne das nur, um Missverständnisse bei Dir auszuschließen.

Wäre für mich co-semi-entscheidbar, da es ja semi-entscheidbar ist ob eine Sprache nur Wörter der selben Länge hat.

Das stimmt als Begründung so nicht. Die Sprache
<math>\{\langle M\rangle: L(M) </math> hat nur Wörter derselben Länge<math>\}</math>
ist nicht semi-entscheidbar. Denn dafür müsste man eine Maschine <math>M</math> auf allen Eingaben laufen lassen, was in endlicher Zeit nicht möglich ist. Die Sprache ist aber co-semi-entscheidbar.

Allerdings geht es gar nicht um diese Sprache, sondern du musst die Sprache
<math>\{\langle M\rangle: L(M) </math> hat zwei Wörter derselben Länge<math>\} \cup\{w: w</math> ist keine Kodierung einer Turingmaschine <math>\}</math>
betrachten. Der zweite Teil ist entscheidbar, du musst also noch begründen, warum der erste Teil semi-entscheidbar ist.

Außerdem hast du noch keine Aussage darüber getroffen
- ob die erste Sprache zumindest semi- oder co-semi-entscheidbar ist.
- ob die dritte Sprache zumindest semi- oder co-semi-entscheidbar ist.
- ob die zweite Sprache vielleicht sogar entscheidbar ist.

Was fällt dir denn zu diesen Fragen ein?

Viele Grüße
Thorsten



-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



  Profil  Quote  Link auf diesen Beitrag Link
egf
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2008
Mitteilungen: 551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-07-18


Hallo

Sorry, ich will dir nicht dreinreden oder felix_macht_mathe's Thread kapern:

2019-07-18 14:11 - Bilbo in Beitrag No. 1 schreibt:
Das ist zwar als Begründung für die Nichttrivialität der Menge korrekt, allerdings würde für den zweiten Teil auch reichen, irgendeine Maschine zu nehmen, die nicht <math>\{0,1\}</math> erkennt (zum Beispiel eine, die nie hält). Die Sprache <math>\Sigma^\ast \setminus \{0,1\}</math> spielt hier keine Sonderrolle. Wie gesagt, ich erwähne das nur, um Missverständnisse bei Dir auszuschließen.

Es ginge mir um die Klammer: "eine, die nie hält": Das wäre mMn nicht zulässig, denn eine Solche erkennt ja gar keine Sprache, resp. dann wäre ja jede Sprache nicht-trivial.



  Profil  Quote  Link auf diesen Beitrag Link
felix_macht_mathe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 19.01.2016
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-07-18


Vielen Dank schon mal für Eure Antworten!

Zu Sprache 2 erstmal; du hast natürlich recht, da habe ich wohl das falsche Komplement in meinem Kopf gebildet...  smile
{\(L(M)\) hat zwei Wörter der selben Länge} wäre für mich semi-entscheidbar, da ich theoretisch eine TM darauf ansetzen könnte, die als Input das erste Wort von L(M) empfängt, die Länge mit allen anderen Wörtern in L(M) abgleicht, und entweder 1 bei gleicher Länge ausgibt, oder so lange weiter sucht, bis alle Wörter ausprobiert wurden... aber was, wenn die Sprache unendlich viele Wörter besitzt  confused Dürfte ich auch sagen, dass ich zuerst einen Algorithmus laufen lasse, der meine Sprache L(M) nach der Wörterlänge sortiert und dann immer eine Wortlänge \(|w_i|\) mit \(|w_(i+1)|\) vergleiche?

Sprache 1 müsste eigentlich semi-entscheidbar sein, da es ja im Grunde das rekursiv-aufzählbare Wortproblem beschreibt (mit der Frage: sind 0 & 1 Teil der Sprache)

Sprache 2 kann eigentlich nicht entscheidbar sein, da dadurch dass sie co-semi-entscheidbar ist, würde sie ja durch Semi-Entscheidbarkeit wiederum insgesamt entscheidbar werden.

Sprache 3 könnte semi-entscheidbar sein, wenn ich eine TM auf das Problem ansetze, soll sie 1 ausgeben, wenn die erste binärkodierte Quadratzahl erkannt wurde und die nächste überprüfen, ansonsten weitersuchen. Hier bin ich mir aber ziemlich unsicher...


Macht das bis hierher Sinn?  smile



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1943
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-07-19


Hallo zusammen!

@egf:
2019-07-18 15:04 - egf in Beitrag No. 2 schreibt:
Es ginge mir um die Klammer: "eine, die nie hält": Das wäre mMn nicht zulässig, denn eine Solche erkennt ja gar keine Sprache, resp. dann wäre ja jede Sprache nicht-trivial.

Nein, das stimmt so nicht. Trivialität ist ja eine Eigenschaft einer Indexmenge, also einer Menge von Maschinenkodierungen. Und Nichttrivialität bedeutet in diesem Zusammenhang nur, dass es mindestens eine Maschine gibt, deren Kodierung in dieser Menge enthalten ist und mindestens eine, deren Kodierung nicht darin enthalten ist. Dabei sind alle Maschinen zu berücksichtigen, egal ob sie überall halten oder nur manchmal oder nirgendwo.


{L(M) hat zwei Wörter der selben Länge} wäre für mich semi-entscheidbar, da ich theoretisch eine TM darauf ansetzen könnte, die als Input das erste Wort von L(M) empfängt, die Länge mit allen anderen Wörtern in L(M) abgleicht, und entweder 1 bei gleicher Länge ausgibt, oder so lange weiter sucht, bis alle Wörter ausprobiert wurden... aber was, wenn die Sprache unendlich viele Wörter besitzt  confused Dürfte ich auch sagen, dass ich zuerst einen Algorithmus laufen lasse, der meine Sprache L(M) nach der Wörterlänge sortiert und dann immer eine Wortlänge |wi| mit |w(i+1)| vergleiche?

Erst einen solchen Sortieralgorithmus laufen zu lassen, funktioniert leider auch nicht, da Du ja bei einer unendlichen Sprache immer noch das Problem hättest, dass dieser unendlich lange laufen würde. Einen Ausweg bietet die sogenannte Dovetailing-Methode: Dabei versuchst Du, für alle Eingabepaare <math>(w, w") \in \Sigma^\ast \times \Sigma^\ast</math> parallel zu vergleichen, ob <math>M(w)</math> und <math>M(w")</math> die gleiche Länge haben. Was damit gemeint ist, habe ich hier schon mal erklärt: dove-tailing

Sprache 1 müsste eigentlich semi-entscheidbar sein, da es ja im Grunde das rekursiv-aufzählbare Wortproblem beschreibt (mit der Frage: sind 0 & 1 Teil der Sprache)

Achtung, die Frage ist nicht: "Sind 0 und 1 Teil der Sprache?" Sondern hier: "Sind 0 und 1 die einzigen Wörter der Sprache?"
Das ist eine deutliche Verschärfung ...

Sprache 2 kann eigentlich nicht entscheidbar sein, da dadurch dass sie co-semi-entscheidbar ist, würde sie ja durch Semi-Entscheidbarkeit wiederum insgesamt entscheidbar werden.

Jetzt drehst Du dich im Kreis. Du sagst: Sie kann nicht entscheidbar sein, denn sonst wäre sie ja entscheidbar. smile Nein, da muss noch eine andere Begründung her (vergleiche auch die anderen beiden Sprachen).

Sprache 3 könnte semi-entscheidbar sein, wenn ich eine TM auf das Problem ansetze, soll sie 1 ausgeben, wenn die erste binärkodierte Quadratzahl erkannt wurde und die nächste überprüfen, ansonsten weitersuchen. Hier bin ich mir aber ziemlich unsicher...

Na, das passt von der Begründung her noch nicht so ganz, auch wenn ich mit der Semi-Entscheidbarkeit einverstanden bin. Versuch mal, es genau zu formulieren: Du willst eine Maschine <math>M"</math> konstruieren, die bei Eingabe <math>w \in \Sigma^\ast</math> die Ausgabe 1 liefert (und hält), wenn <math>w</math> in <math>L</math> liegt, und sonst nicht anhält. Bei Eingabewort <math>w</math> prüft <math>M"</math> nun zuerst, ob <math>w</math> die Kodierung einer Turingmaschine <math>M</math> ist, also ob <math>w = \langle M \rangle</math> für ein <math>M</math> gilt. Falls ja, dann ...
Kriegst du den Rest selbst hin?

Viel Erfolg und viele Grüße
Thorsten






-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



  Profil  Quote  Link auf diesen Beitrag Link
egf
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2008
Mitteilungen: 551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-07-19


Hallo Bilbo
Ich mache mal hier weiter um in diesem Thread nicht weiter zu stören.



  Profil  Quote  Link auf diesen Beitrag Link
felix_macht_mathe wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]