Unentshceidbarkeit Flashcards
1
Q
Is Pot(N) abzahlbar?
A
Nein.
2
Q
Wie viele TMen gibt es?
A
Abzahlbar viele.
3
Q
Diagonalsprache unentshceidbar?
A
Ja.
4
Q
Formal definition of Diagonalsprache?
A
{ w in {0,1}* | w = w_i und M_i akzeptiert w nicht }
5
Q
Komplement der DIagonalsprache?
A
Unentscheidbar
6
Q
Wenn die Sprache L in {0,1}* unentscheidbar so ist das Komplement davon…
A
unentscheidbar
7
Q
Wenn die Sprache L in {0,1}* entscheidbar so ist das Komplement davon…
A
entscheidbar
8
Q
Halteproblem un- oder entscheidbar?
A
Entscheidbar
9
Q
Entshceidbare Beispielen:
A
L(M) in {0,1}*
L(M) von 1 TM akz
2222 in L(M)
2222 not in L(M)
M gerade Anzahl von Q
M hat Endzustand
|| Primzahl
