0

Hallo zusammen,

Hab ein bisschen ein Durcheinander mit dem Verständnis von Halteproblem und Acceptance Problem (ATM). Was ist das Halteproblem. Es bedeutet, dass es nicht entscheidbar ist bzw. es gibt keine Programme, welches bestimmte Probleme nicht lösen können. Eines davon ist das Halteproblem. Wie genau funktioniert das? Kann mir dies jemand anhand eines einfachen Beispieles erklären? Was ist der wesentliche Problem unterscheide ATM und Halteproblem?

Hier ist z.B. eine Aussage zu ATM F: Program A: Turing Machine

If F accepts ‹F›, then A says that it doesn't. If F does not accept ‹F›, then A says that it does. F(‹M›) If A answers true on input (‹M›, ‹M›) then loop forever else return true end if

Ist eine Turing Machine Computer und F bzw. decider ein Program. Wie kann das sein. Dass wenn das Program, akzeptiert, dass A dies ablehnt und umgekehrt?

Wie geht man mit Reduktionen um? Kann mir jemand dabei helfen?

enter image description here Lösung: Warum D komplement warum geht man von D komplement aus? Verstehe ich nicht enter image description here Prove that the following problems on pairs of Turing machines M;N are undecidable a) whether L(M) Intersect L(N) = empty b) whether |L(M) \ L(N)| < inf.

Lösung: enter image description here enter image description here if G accepts, then reject, otherwise accept diese Aussage verwirrt mich. Was akzeptiert G und was wird abgelehnt? enter image description here enter image description here enter image description here

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
1 Antwort
1

Das Halteproblem ist unentscheidbar aber semi-entscheidbar. Weil du zwar sagen kannst, wenn deine Maschine in endlicher Zeit hält. Aber du weißt nicht, wenn sie nicht hält ob sie noch halten wird. Du musst dir das so überlegen: du baust dir eine Maschine die eine andere Maschine nimmt, diese für ein Wort w simuliert und du sollst entscheiden, ob diese Maschine hält oder nicht. Für manche Probleme kann man das ganz schnell entscheiden. Du nimmst zb. die Maschine die die Sprache a^nb^n erkennen soll und gibst das Wort w=aaabb. Deine Maschine kann sehr schnell entscheiden ob die simulierte Maschine hält oder nicht nach endlicher Zeit. Jetzt denke dir aber eine andere Maschine die eine sehr viel kompliziertere Sprache erkennt und du weißt nicht was sie genau tut. Also willst du es ausprobieren. du gibst ein Wort w ein und startest die Maschine. Jetzt rechnet die ne ganze Weile und jetzt kannst du die Maschine entweder laufen lassen und unter Umständen wird es noch zb. 1 Millionen Jahre dauern bis sie anhält oder sie wird nie anhalten, weil sie zB. in einer Endlosschleife gelandet ist und da nie wieder rauskommen wird. Also das Prinzip des halteproblem ist, dass du eine Maschine erfinden müsstest die ein beliebiges Wort w bekommt und eine beliebige Maschine (Turingmaschine) die du vorher auch nicht kennen musst und dann entscheidet, ob diese Maschine halten wird. Das ist unmöglich festzustellen.

Mit Reduktionen kannst du dir bekannte Probleme wie das Halteproblem zunutze machen. Indem du dein gegebenes Problem so umbaust, dass du bei einem bekannten Problem landest. Das heißt am ende muss deine umgebautes Problem trotzdem noch das gleiche erkennen, also wenn w \in dem Problem ist, dann muss es auch ein element des anderen problems sein und umgekehrt. Durch diese Konstruktion zeigst du, dass dein gegebenes Problem die gleichen EIgenschaft hat, wie dein in der reduktion benutztes Problem. Weil könntest du dein gegebenes Problem lösen irgendwie, dann könntest du auch deine Konstruktion nutzen, um dein bekanntes Problem(das in der reduktion genutztes) auch zu lösen. Und da dies bewiesen ist, dass das nicht geht muss dein neues Problem die gleiche Eigenschaft haben.

Ich verstehe noch nicht ganz, was ATM akzeptieren soll und was ablehnen. Aber zu deiner Frage: Du kannst ja 2 Turingmaschinen bauen. Die eine nennst F, die andere A. Nun startest du F und wartest, ob diese auf ein Endzustand hält oder nicht. Die Turingmaschine nimmst diese Information als Eingabe an(also ob sie auf einem End... hält oder nicht) und macht dann genau das gegenteilige. Also akzeptiert, wenn F nicht akzeptiert und umgekehrt. Da siehst du auch schon wie du die Reduktion auf das Halteproblem machen kannst. Weil du ja nicht für jedes F sagen kannst ob es hält oder nicht musst du nur eine Konstruktion basteln die genau dann das Wort w akzeptiert, wenn das gleiche Wort vom Halteproblem akzepiert wird und wieder umgekehrt. Wenn du jetzt noch die genaue Reduktion sehen willst, dann sag bescheid. (Ich hab inzwischen die Konstruktion verstanden ^^)

Diese Antwort melden
geantwortet

Punkte: 55

 

Woow vielen Dank für die ausführliche Erklärung. Jetzt verstehe ich es ein bisschen besser.
Undecidable: bedeutet es kann entweder in einer gewissen Zeit halten oder in einer Endlosschleife landen.
Decidable: bedeutet das Programm kann eine bestimmte Wortlänge akzeptieren oder ablehnen
Recognizable: bedeutet wenn das bestimmte Wort in der Sprache ist?
Unrecognizable: Ist nicht in der Sprache?

Hab oben noch weitere Aufgaben mit Lösungen eingefügt. Könntest du in menschlicher Sprache erklären? :D Was ich mir darunter vorstellen soll bzw. wie ich mit der Reduktion bzw. beweisen umgehen soll. Hab immer noch nicht mit dem formalen beweisen verstanden, wie man vorgeht. Ohne Lösung komme ich nie darauf! Hast du dazu Tipps?

  ─   sayuri 24.06.2021 um 08:45

Untentscheidbar heißt, dass die Maschine die ein Problem löst entweder gar nicht antwortet oder eben nur eine Antwort liefern kann. Z.B. gibt es Probleme die sind untenscheidbar und weder co- noch semientscheidbar. Das heißt die Maschine wird dir nie eine Antwort liefern. Es gibt aber auch Probleme, siehe Halteproblem. Die sind untentscheidbar aber semi-entscheidbar. Wenn ein Problem semi und co-semi Entscheidbar sind dann ist es wieder entscheidbar. Das ist bischen verwirrend gemacht. Mit dem (un)recognizable hab ich kp auf was das sich bezieht.

  ─   carlos 24.06.2021 um 21:57

Ich schreib morgen ne nachricht wegen den oben gegebenen Aufgaben
Ich hab ansich das Prizip verstanden von rekursion und kann es auch umsetzen aber ich mach da gerne mal fehler deswegen brauche ich dafür ein wenig mehr Zeit. Vorallem um des auseinander zu flücken

  ─   carlos 24.06.2021 um 21:58

Alles klar danke dir!! Was ist erkennbar und unerkennbar? Verstehe es nicht, wie ich dies erkennen soll? Gibt es Schlüsselwörter, welches angibt ob es sich um entscheidbar, unentscheidbar, erkennbar oder unerkennbar ist?

  ─   sayuri 25.06.2021 um 20:25

Hi carlos,

Hast du eine Erklärung zu den obigen Fragen?

  ─   sayuri 27.06.2021 um 12:39

Hattest du die Zeit, um die Problem anzuschauen?

  ─   sayuri 04.07.2021 um 14:09

Kommentar schreiben