Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Entscheidbarkeit und Semi-Entscheidbarkeit
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Entscheidbarkeit und Semi-Entscheidbarkeit
luisa01
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.07.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-01


Hallo zusammen!

Ich studiere momentan medizinische Informatik und muss daher auch einen Kurs zur theoretischen Informatik belegen.
Dabei haben wir folgende Aufgabe in einer Übung gestellt bekommen:

a) Zeigen sie, dass das Problem HΣ∗={⟨M⟩|M ist eine Turingmaschine, die auf allen Eingaben hält} nicht entscheidbar ist, indem sie das allgemeine Halteproblem auf HΣ∗ reduzieren

b) Zeigen Sie, dass HΣ∗ sogar nicht semi-entscheidbar ist (Hinweis: Konstruieren Sie unter der Annahme, daß HΣ∗ semi-entscheidbar ist, eine neue TM, die auf jeder Eingabe hält, deren Sprache sich aber von jeder TM in HΣ∗ unterscheidet (logischer Widerspruch). Benutzen Sie dazu ein Diagonalisierungsargument und berechenbare Aufzählungen aller Wörter aus Σ∗ und aller TM aus HΣ∗

c) Zeigen Sie, dass das Problem F={⟨M⟩|L(M) ist nicht leer} semi-entscheidbar ist

d) Was folgt aus Teilaufgabe c für das Problem E={⟨M⟩| M ist eine Turingmaschine und L(M) ist leer}?

Ich weiß ehrlich gesagt überhaupt nicht, wie ich da anfangen soll. In unserem Skript gibt es zwar zur a den Hinweis, dass man analog vorgehen soll wie bei der Reduktion des allg. Halteproblems auf die Sprache HE={⟨M⟩|M hält auf dem leeren Wort}, mir scheint mein Ansatz aber viel zu trivial. Bei den anderen Aufgaben kann ich mir nicht mal einen Ansatz vorstellen.

Vielen Dank schon mal fürs Anschauen!

Liebe Grüße
Luisa



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-01


Hallo Luisa, und herzlich willkommen auf dem Matheplaneten!

Ich greife mir mal die Aufgabe c) heraus.

2020-07-01 11:21 - luisa01 im Themenstart schreibt:
c) Zeigen Sie, dass das Problem F={⟨M⟩|L(M) ist nicht leer} semi-entscheidbar ist

\(F\) ist die Menge der Kodierungen all jener Turingmaschinen, deren erzeugte Sprache nicht leer ist.

Habt ihr bereits die aufzählenden Turingmaschinen behandelt? Wenn ja, dann genügt es zu zeigen, dass die Sprache \(F\) aufzählbar ist.

Wenn nein, dann müssen wir die Definitionen zerpflücken.

Hast du ein Skript, das ich mir mal zu Gemüte führen kann?

Kannst du hiermit etwas anfangen, insb. Blatt 98 und Blatt 124?

mfg
thureduehrsen


-----------------
sammeltlemmas.blogspot.de/

https://www.informatik.uni-kiel.de/~tdu/



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
luisa01
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.07.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-01


Hallo thureduehrsen!

Danke zuerst mal für deine Antwort.
Nein, wir hatten aufzählbare Sprachen noch nicht, also kann ich damit leider nicht so viel anfangen.

Das Skript bzw. die Seiten, die du mir schicken wolltest, kann ich leider nicht aufrufen. Mein Skript von der Uni zum Thema findest du hier falls dir das hilft

Liebe Grüße
Luisa



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-01


Hallo Luisa,

dann müssen wir eine Turingmaschine \(E\) angeben, die folgende Eigenschaften hat:

Auf Eingabe \(\langle M\rangle\):

Wenn \(L(M)\) leer ist, dann hält \(E\) nicht.

Wenn \(L(M)\) nicht leer ist, dann hält \(E\).

Versuche, dies hinzubekommen, indem du eine beliebige, aber feste Abzählung \(a\) der Menge \(\Sigma^{\ast}\) betrachtest. (D.h. es möge \(\Sigma^{\ast}=\{a_i\,\colon\, i\in\mathbb{N}\}\) gelten.) Ungefähr so sieht das dann aus:

\(E:\)
\(\text{Auf Eingabe \(\langle M\rangle\)}:\)
\(i\leftarrow 0\)
\(\text{while true do}\)
\(\quad\text{für jedes j von \(0\) bis \(i\) einschließlich:}\)
\(\quad\quad\text{Lasse \(M\) auf Eingabe \(a_i\) laufen}\)
\(\quad\quad\text{Falls \(M\) die Eingabe \(a_i\) im \(j+1\)-ten Schritt akzeptiert, dann: ...}\)
\(\quad\quad\quad\text{muss etwas Bestimmtes passieren}\)
\(\quad\quad\text{sonst}\)
\(\quad\quad\quad\text{muss etwas Anderes passieren}\)
\(...\)

Versuche doch einmal, ob du das zuende führen kannst.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
luisa01 hat die Antworten auf ihre/seine Frage gesehen.
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-2021 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]