Entscheidbarkeitsproblem: TM < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Treffen Sie eine Aussage zur Entscheidbarkeit und begründen Sie diese:
[mm] C=\{|M ist TM und T(M) enthaelt genau 42 Woerter\} [/mm] |
Ich verstehe zum Einen die Aussage der Aufgabe nicht ganz:
Ist damit gemeint, ob man entscheiden kann, dass eine TM genau 42 gültige Eingaben hat?
Zum Anderen habe ich auch einen Lösungsansatz bekommen, den ich aber nicht verstehe und auch nicht genau weiß, ob er überhaupt richtig ist:
Reduzierung [mm] A_{TM} [/mm] reduzierbar C.
Für ein Paar <M,w> bilde [mm] M_{w41} [/mm] wie folgt: wähle ein a nicht Element Sigma{M}.
Eingabe für [mm] M_{w41} [/mm] sei x: falls Eingabe [mm] x=a^{i}, [/mm] i Element [mm] \{1,...,41 \} [/mm] akzeptiere, andernfalls simuliere M mit Eingabe w und akzeptiere wie M.
Vielen Dank für euere Hilfe!!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:21 Fr 04.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
