Unentscheidbarkeit Reduktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:59 Do 19.11.2009 | | Autor: | Ikit |
| Aufgabe | Man beweise mittels Reduktion, dass das Endlichkeitsproblem unentscheidbar ist:
L = {<M>| M ist eine Turingmaschine und hält für endlich viele Eingaben} |
Ich habe das mit der Reduktion noch nicht hundertprozentig verstanden:
Man nimmt an, dass es eine TM [mm] M_{L} [/mm] gäbe, die L entscheidet.
Ich muss mir doch dann eine TM M konstrutieren, die als Eingabe ein x und ein [mm] M_{2} [/mm] bekommt, so dass - wenn man dieses M dann [mm] M_{L} [/mm] übergibt - [mm] M_{L} [/mm] in der Lage wäre, das Halteproblem zu entscheiden.
Da das Halteproblem aber unentscheidbar ist, ist L dann auch unentscheidbar.
Ich komm aber einfach nicht drauf, wie ich mir so eine TM M (bzw. eine Funktion f) konstruieren soll, so dass [mm] M_{L} [/mm] in der Lage wäre, das Halteproblem zu entscheiden.
Gibt es da irgendeine allgemeine Vorgehensweise, wie man an solche Aufgaben und speziell an diese herangeht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Sa 21.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
