Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 2 von 2 Treffern

Autor

Beitrag

Thema: PKP Reduktion auf 01-PKP

Hamsterchen

Antworten:	3
Hits:	5.425

04.08.2011 20:37

Forum: Theoretische Informatik

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

Thema: PKP Reduktion auf 01-PKP

Hamsterchen

Antworten:	3
Hits:	5.425

PKP Reduktion auf 01-PKP 27.07.2011 12:36

Forum: Theoretische Informatik

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 [latex]f(a_i)=10^i[/latex]

. 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 [latex]10^i[/latex]

muss in dem Fall doch so gedeutet werden: [latex]10^3=101010[/latex]

, oder? Sonst geht das doch nicht glaube ich.
Zweite Frage: Das selbe könnte ich doch auch so machen: [latex]f(a_i)=0^i[/latex]

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

Zeige Beiträge 1 bis 2 von 2 Treffern