Entscheidbarkeit < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 23:26 Sa 02.05.2009 | | Autor: | eps |
| Aufgabe | | L entscheidbar [mm] \Rightarrow L^{\*} [/mm] entscheidbar |
L ist entscheidbar, wenn es eine Tuningmaschine M gibt mit:
(1) M hält auf allen Eingaben
(2) L = L(M) := {x [mm] \in \summe^{\*} [/mm] | M akzeptiert x}
[mm] L^{\*}=\bigcup_{i=1}^{\infty} L^{i}
[/mm]
Wenn L entscheidbar ist, ist doch auch L*L entscheidbar und da die Vereinigung zweier entscheidbarer Sprachen entscheidbar ist, folgt [mm] L^{\*} [/mm] ist entscheidbar.
Stimmt das, oder ist das Produkt zeier entscheidbarer Sprachen nicht entscheidbar?
- das müsste ich auch noch zeigen und weiss leider nicht wie.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:23 Di 05.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
