DTM,Kopfbewegung -entscheidbar < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 00:27 Mi 18.01.2012 | | Autor: | Dym |
| Aufgabe | Für D [mm] \in\ [/mm] {L,R,N} sei
[mm] L_\neg_D [/mm] = {w [mm] \in\{0,1\}^\* [/mm] | [mm] M_w [/mm] ist eine 1-DTM,die bei Eingabe [mm] \epsilon [/mm] niemals die Kopfbewegung D ausführt }
Für welche Werte von D ist [mm] L_\neg_D [/mm] entscheidbar? |
Meine Gedanken zur Aufgabenstellung bis jetzt:
- [mm] L_R [/mm] und [mm] L_L [/mm] sind bei leerer Eingabe symmetrisch,weil bei Vertauschung
von L und R, L und R gegenseitig reduzierbar sind in allen Anweisungen der TM. Deshalb ist das Problem auf [mm] L_N [/mm] reduzierbar.
Bleibt noch zu fragen wie ich jetzt weitermache? Kann mir jemand da vielleicht einen Tipp geben oder ggf. ein Ansatz oder sowas bitte.
Gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Fr 20.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
