Die Mathe-Redaktion - 23.07.2018 13:44 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
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 533 Gäste und 24 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Nicht-semientscheidbarkeit einer Sprache
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Nicht-semientscheidbarkeit einer Sprache
birdfreeyahoo
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.02.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-02-06

\(\begingroup\)
Hi, wir haben in der Uni eine Aufgabe gehabt die folgendermaßen aussieht:

\[L_{u,v} = \{<M> | u \in L(M) \wedge v \not\in L(M)\}\]
Die Aufgabe ist zu zeigen, dass diese Sprache und ihr Komplement nicht-semientscheidbar sind. (u und v sind beliebige, ungleiche Wörter aus dem Alphabet von L und das muss für alle u und v gelten).

Jetzt habe ich überlegt dass die Lösung sein könnte eine nicht-semientscheidbare Sprache auf L zu reduzieren. Da fiel mir das Komplement des Halteproblems ein. Allerdings weiß ich nicht ob man das einfach so reduzieren kann, weil das Halteproblem das Wort ja als Eingabe hat und diese Sprache hier nicht (die Wörter sind ja "statisch"). Außerdem habe ich keine Reduktion dafür gefunden. Habe mir jetzt einiges dazu durchgelesen, aber irgendwie komm ich auf keine Lösung.

Dazu kommt auch noch dasselbe für das Komplement zu beweisen.

Ich hoffe jemand hier kann mir helfen smile
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
bernd_brood
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2018
Mitteilungen: 3
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-02-07


Habe die gleiche Frage:
Sei a,b in Sigma*, a!=b, A={<M> | a in L(M) und b !in L(M)}

Ich denke man kann damit argumentieren, dass es ja anscheinend für jedes beliebige a und b gelten soll. Und nur dann <M> in A ist.
Testet man mit einem x und einem y (x != y) mit M so ist x in L(M) und y nicht in L(M). Testet man mit y x soll nun genau das selbe gelten und damit x in L und y nicht in L gelten.
Was bei jeder Sprache zum wiederspruch führt und L= {leer} gilt.
Und H(all) und H(e) (Spezielles Halteproblem) sind nicht entscheidbar.
Damit ist die Sprache und ihr Komplement nicht entscheidbar.

Ob das Spezielle Halteproblem und das Allgemeine Halteproblem beide wirklich nicht semi-entscheidbar sind weis ich nun auch nicht...
Das Halteproblem ist ja semi-entscheidbar



  Profil  Quote  Link auf diesen Beitrag Link
birdfreeyahoo
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.02.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-02-07


Hm das hört sich ja schon mal nach was an, aber ich denke nicht dass das so funktioniert, weil ich glaube dass konkrete werte für a und b eine konkrete Instanz dieser Problems darstellen und du das dann nicht einfach nochmal auf die gleiche Eingabe anwenden kannst. Will heißen in der einen Menge ist es drin, in der anderen dann aber nicht.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
bernd_brood
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2018
Mitteilungen: 3
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-02-19


Hey, hast du ne Lösung gefunden?



  Profil  Quote  Link auf diesen Beitrag Link
birdfreeyahoo 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-2018 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]