Die letzten 6 Beiträge |
Karlito |
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 |
Nightingale |
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.
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 |
Karlito |
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 |
Nightingale |
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.
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. |
Karlito |
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 |
Nightingale |
Diverse Reduktionen
Hallo, das Prinzip hinter dem Reduktionsbeweis habe ich soweit verstanden und bei sowie auch nachvollzogen.
Jetzt habe ich mich ein paar Reduktionsaufgaben gewidmet wobei ich die Reduktionsfunktion 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 2)
Gegeben sind die Mengen
= { | hält auf Eingabe 1 nicht an },
= { | hält auf allen Eingaben nicht an }.
Zeigen Sie, dass die Menge unentscheidbar ist, indem Sie auf reduzieren.
Meine Lösung:
Zu zeigen:
Konstruiere :
Man kann jedem Wort eine Turingmaschine zuordnen, die wie folgt verbal beschrieben ist...
Ist das Band zu Beginn nicht leer, löscht den Inhalt zunächst.
Auf leerem Band schreibt nun '1' aufs Band und verhält sich dann so wie (also der in kodierten Turingmaschine aus ).
Da sowohl berechenbar, als auch total ist, vermittelt 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 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. |
|
|