PKP Reduktion auf 01-PKP

27.07.2011, 12:36	Auf diesen Beitrag antworten »
Hamsterchen	PKP Reduktion auf 01-PKP Hallo alle zusammen, ich hab Informatik als Beifach und höre dieses Semester TGI 1. In einer Übungsaufgabe sollten wir folgendes zeigen: In der Vorlesung wurde gezeigt, dass PKP unentscheidbar ist. a) Was ist, wenn das Alphabet auf {0,1} beschränkt ist? b) Was ist, wenn das Alphabet nur die 0 enthält. Leider hab ich keine Lösung zu der Aufgabe, also hab ich gegoogelt und folgendes gefunden: a) Wenn man sich eine Funktion f folgendermaßen defininiert: Sei $[latex]\Sigma=\{a_1,\ldots,a_n\}[/latex]$ , dann ist . f ist berechenbar und es gilt dann $[latex]\omega\in\,PKP\,\iff f(\omega)\in \,01\,PKP[/latex]$ . Daraus folgt dann, dass 01 PKP auch unentscheidbar ist. Meine Fragen dazu: das muss in dem Fall doch so gedeutet werden: , oder? Sonst geht das doch nicht glaube ich. Zweite Frage: Das selbe könnte ich doch auch so machen: und dann würde folgen, dass 0-PKP auch unentscheidbar ist, was aber nicht stimmt. b) Hier verstehe ich den Beweis den ich gefunden habe, aber nur, wenn bei PKP nicht jedes Element zwangsweiße vorkommen muss. Habe aber keiner Definition entnommen, dass man auch welche weglassen kann. Ist das so? Wäre für Antworten wirklich dankebar LG Hamsterchen


30.07.2011, 23:05	Auf diesen Beitrag antworten »
Zukatah	Hallo Hamsterchen. 10^i 10² bedeutet hier nicht 1010, sondern 100, ebenso 10³ nicht 101010, sondern 1000 Du hast also dein Alphabet, in deinem Fall Sigma, mit den Elementen a1,...,an, also a1, a2, a3, a4, usw. Du stellst nun das erste Zeichen (a1) durch 10^1, also 10 dar, das zweite (a2) durch 10^2, also 100, das dritte (a3) durch 10^3, also 1000, und so weiter. Auf diese Art, das ist das Wichtige, stellst du sicher, dass die Zuweisung, also deine Funktion f(ai) eindeutig ist; das heißt sie ist bijektiv und du könntest jederzeit eine Rückfunktion bestimmen. Würdest die Funktion (10)^i tatsächlich für i=2 1010, für i=3 101010 und so weiter ergeben, könntest du zB bei der Zeichenfolge 10101010 nicht sagen, ob du hier zweimal a2 hättest, also zweimal 1010, oder einmal a3 und einmal a1, also 101010 und 10, da beide zusammen jeweils die Folge 10101010 ergeben. Diese Funktion wäre also nicht eindeutig, nicht bijektiv; eine Rückfunktion wäre nicht eindeutig bestimmbar. Dadurch beantwortet sich auch der Aufgabenteil b. Wenn du nur 0en zur Verfügung hast, kannst du die Zeichen unmöglich eindeutig darstellen. Würden wir zB die Funktion 0^i nehmen, wäre a(1)=0, a(2)=00, a(3)=000, wenn wir unsre Funktion drauf anwenden. Wenn ich dir nun das Wort 0000 gebe, könntest du mir nicht sagen, ob ich a(1)a(3), a(2)a(2) oder a(4) oder a(1)a(2)a(1) uswusf meine, da alle, wenn man die Funktion 0^i anwendet, die gleiche Folge, nämlich 0000 ergeben. Ich hoffe ich konnte helfen. Nebenbei: Hörst du TGI zufällig in der UNI Mainz? Wir haben exakt die selbe Aufgabe mit quasi dem selben Wortlaut bereits durchgesprochen Viele Grüße Zukatah
04.08.2011, 20:37	Auf diesen Beitrag antworten »
Hamsterchen	Hi, ich hab gar nicht mitbekommen, dass du geantwortet hast. habe irgendwie keine mail bekommen. aber jetzt hab ichs ja gesehen ^^ ja ich höre tgi in mainz =) hast du auch die klausur gestern mitgeschrieben? ich hatte bei der aufgabe irgendwie voll den denkfehler, aber der ist mir vorgestern dann selbst aufgefallen. trotzdem vielen dank für deine ausführliche antwort. lg hamsterchen
05.08.2011, 19:40	Auf diesen Beitrag antworten »
Zukatah	Uni Mainz Schönen guten Abend! Ja, hab auch die Klausur am Mittwoch mitgeschrieben ; ) Im Gegensatz zu den Vorlesungen recht ertragbar, bis auf dass ich eine knappe Stunde Zeit wegen einem Lesefehler bei der 2D-TM-Aufgabe verloren hab : / ^^ Viele Grüße Zukatah
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »