Übungsblatt 12 Flashcards
1
Q
Jeder linear beschränkte Automat ist eine Turingmaschine?
A
Wahr, ein LBA ist eine Turingmaschine mit Einschränkungen
2
Q
Eine Turingmaschine darf nie das Blanksymbol auf das Band schreiben?
A
Falsch, nur LBAs dürfen das Blanksymbol nicht schreiben
3
Q
Es gibt überabzählbar (reelle Zahlen) unendlich viele Wörter über einem endlichen Alphabet?
A
Falsch, es gibt abzählbar unendlich viele Wörter über einem endlichen Alphabet
4
Q
Es gibt abzählbar (ganze Zahlen) unendlich viele berechenbare Funktionen f: N^k -> N
A
Wahr
5
Q
Es gibt überabzählbar (reelle Zahlen) unendlich viele Funktionen f: N^k -> N
A
Wahr
6
Q
Es gibt überabzählbar (reelle Zahlen) unendlich viele Funktionen f: N -> N
A
Wahr
