Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Diverse Reduktionen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Diverse Reduktionen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Nightingale
Grünschnabel

Dabei seit: 13.03.2015
Beiträge: 5

Diverse Reduktionen

Zitatantwort auf diesen Beitrag erstellen

Hallo, das Prinzip hinter dem Reduktionsbeweis habe ich soweit verstanden und bei $[latex]K \leq H[/latex]$ sowie $[latex]H \leq H_0[/latex]$ auch nachvollzogen.

Jetzt habe ich mich ein paar Reduktionsaufgaben gewidmet wobei ich die Reduktionsfunktion [latex]f[/latex]

meist verbal beschreiben musste, einmal aber auch direkt angeben konnte. Beim Beschreiben bin ich noch eher unsicher ob es der richtige Ansatz ist, oder wohl Aussagekräftig genug ist.

Ich denke ich poste einfach erstmal 2 Aufgaben, dann kann man weitersehen.

Zitat:

Aufgabe 1)

Gegeben ist die Menge

= {

| $[latex]M_{w_2}[/latex]$ hält mindestens bei allen Eingaben, bei denen auch $[latex]M_{w_1}[/latex]$ hält }.

Zeigen Sie durch Reduktion, dass [latex]I[/latex]

unentscheidbar ist. Nutzen Sie dafür die bekanntermaßen unentscheidbare Menge $[latex]H_{\forall}[/latex]$ = { [latex]w[/latex]

| $[latex]M_{w}[/latex]$ hält auf allen Eingaben }.

Meine Lösung:
Zu zeigen: $[latex]H_{\forall}\leq I[/latex]$

$[latex]w \in H_{\forall}[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf allen Eingaben}[/latex]$
$[latex]\Leftrightarrow\ M_{w_2}\ \text{haelt mindestens bei allen Eingaben, beim denen} M_{w_1} \text{haelt}[/latex]$
$[latex]\Leftrightarrow\ f(w)\in I[/latex]$

mit [latex]f(w) = w[/latex]

Überlegung: Die Turingmaschine $[latex]M_{w}[/latex]$ aus $[latex]H_{\forall}[/latex]$ hält auf allen Eingaben (was im Grunde irrelevant ist). Verkettet man es mit Trennsymbol # wie es [latex]f(w)[/latex]

tut, sind die Turingmaschinen $[latex]M_{w_1}[/latex]$ und $[latex]M_{w_2}[/latex]$ identisch. $[latex]M_{w_2}[/latex]$ hält also sogar exakt bei den Eingaben, für die auch $[latex]M_{w_1}[/latex]$ hält, was nicht im Konflikt mit der Bedingung in [latex]I[/latex]

steht. Soweit OK und genügt das?

Zitat:

Aufgabe 2)

Gegeben sind die Mengen

= {

| $[latex]M_{w}[/latex]$ hält auf Eingabe 1 nicht an },
$[latex]H_{1^+}[/latex]$ = { [latex]w[/latex]

| $[latex]M_{w}[/latex]$ hält auf allen Eingaben $[latex]x \in \{1\}^+[/latex]$ nicht an }.

Zeigen Sie, dass die Menge $[latex]H_{1^+}[/latex]$ unentscheidbar ist, indem Sie [latex]H_1[/latex]

auf $[latex]H_{1^+}[/latex]$ reduzieren.

Meine Lösung:
Zu zeigen: $[latex]H_1\leq H_{1^+}[/latex]$

$[latex]w \in H_1[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf Eingabe 1 nicht an}[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf allen Eingaben } x \in \{1\}^+ \text{ nicht an}[/latex]$
$[latex]\Leftrightarrow\ f(w)\in H_{1^+}[/latex]$

Konstruiere [latex]f(w)[/latex]

:

Man kann jedem Wort [latex]w[/latex]

eine Turingmaschine [latex]M[/latex]

zuordnen, die wie folgt verbal beschrieben ist...

Ist das Band zu Beginn nicht leer, löscht [latex]M[/latex]

den Inhalt zunächst.
Auf leerem Band schreibt [latex]M[/latex]

nun '1' aufs Band und verhält sich dann so wie $[latex]M_{w}[/latex]$ (also der in [latex]w[/latex]

kodierten Turingmaschine aus [latex]H_1[/latex]

).

Da

sowohl berechenbar, als auch total ist, vermittelt [latex]f[/latex]

die gewünschte Reduktion.

Überlegung: Bei dem Reduktionsbeweis bettet man ja das bereits bekannte Problem in ein neues ein. Im neuen Problem wird auf allen möglichen 1er-Kombinationen als Eingabe nicht gehalten. Die Eingabe 1 wie im alten Problem ist dort also bereits enthalten. Wenn ich sage, egal was meine aktuelle Eingabe ist, ich verwerfe diese und schreibe lediglich exakt 1 aufs Band und führe dann $[latex]M_{w} \in H_1[/latex]$ aus, habe ich das alte ins neue Problem eingebettet. Das alte Problem war schon unentscheidbar, somit wird es das neue Problem erst recht sein.

Passt das zumindest ungefähr so?

Wenn ich die beiden Aufgaben geblickt habe, kann ich gerne noch 2-3 weitere Beispiele bearbeiten und reinstellen, falls dort dann jemand nochmal drüber schauen mag.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Nightingale: 19.03.2015 01:51.

19.03.2015 01:46

Nehmen Sie Nightingale in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ach, verflucht... Jetzt weiß ich was Du mit Reduktion meinst. Ich dachte es geht um weitere Minimierungen von Automaten... Ich garantiere mal für nix aber schaue es mir gerne noch mal mit an. Wird vielleicht eine Weile dauern. Ich mochte das Thema, aber ich fand es nicht leicht (ist auch schon wieder ein paar Jahre her)...

Gruß,

Karlito

19.03.2015 03:06

Nehmen Sie Karlito in Ihre Freundesliste auf

Nightingale
Grünschnabel

Dabei seit: 13.03.2015
Beiträge: 5

Hehe, ach kein Problem, jetzt wo du es sagst Fakt es mir sonst auf, dass man das verwechseln könnte - gerade in der Kombi. Es im anderen Thread Reduktionsbeweis genannt zu haben, hatte wohl auch nicht nicht viel gebracht. Hehe und ich dachte mir schon woher du schon weißt, dass du nen anderes Verfahren dazu verwendest. großes Grinsen

Wie gesagt, kann man f() direkt angeben sollte es nicht ganz so schwer sein, auch wenn meine Überlegungen etwas knackiger sein könnten. Aber muss man die Reduktionsfunktion verbal beschreiben wird es doch komplizierter und ich unsicherer.

Ich denk mir dann immer, oder war es doch anders herum und verwirre mich selbst. Daher hätte ich gerne etwas mehr Routine darin um sicherer um werden.

Wie gesagt, wäre nett wenn du oder andere mal mit drüber schauen würden. Kann denke nicht schaden das mit mehreren mal anzuschauen.

19.03.2015 10:06

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Joar, mit der Richtung hatte ich auch immer Probleme... Und doch, Reduktionsbeweis hätte geholfen... Ich versuche mal mir das spätestens über's Wochenende anzuschauen. Du studierst nicht zufällig in Dresden?

Gruß,

Karlito

19.03.2015 10:12

Nightingale
Grünschnabel

Dabei seit: 13.03.2015
Beiträge: 5

Hi Karlito, danke für deine Mühe. Bist du eig. der Einzige der hier in theoretischen Teil des Forum Fragen aufgreift und beantwortet? Wäre schade drum.

Nein ich studiere nicht in Dresden, sondern in NRW. Augenzwinkern

Hattest du denn schon etwas Gelegenheit mal drüber zu schauen, bzw. soll ich evtl. zum (Wieder-)Einstieg nochmal K<=H oder H<=H0 hier posten?

Beste Grüße
Nightingale

22.03.2015 02:26

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Nightingale,

leider bin ich bisher noch nicht dazu gekommen und habe heute Abend auch noch was vor. Und ja, ich bin leider momentan der einzige, der hier Fragen zur theoretischen Informatik beantwortet. Ab und zu kommen noch einwürfe zu Komplexitätsproblemen, aber eher rar.

Ich kann leider nicht garantieren, dass ich noch dazu komme... Wenn ich noch mal die von dir genannten Reduktionen brauche, würde ich mich melden.

Gruß,

Karlito

22.03.2015 16:10

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Diverse Reduktionen