Berechenbarkeitsbegriff Flashcards
Berechenbarkeit - Definition
Church’sche These
Intuitive Berechenbarkiet = Turning-Berechenbarkeit
Turing-Berechenbarkeit I - Definiton
Turing-Berechenbarkeit II - Definition
entscheidbar - Definiton
Eine Sprache L heißt entscheidbar, wenn XL berechenbar ist
semi-entscheidbar - Definition
Eine Sprache L heißt semi-entscheidbar wenn X’L berechenbar ist.
k-Band Turing-Maschine M - Defintion
Erlauben bequemes Programmieren (um Berechenbarkeit zu zeigen)
Mehrband-TM Äquivalenz - Theorem
Zu jeder k-Band-TM M gibt es eine Einband-TM Q mit T(M) = T(Q)
Mehrband-TM übersetzen
Die Idee besteht darin, eine Einband-Turing-Maschine Q mit einem erweiterten Bandalphabet zu verwenden. Die Elemente des Bandalpahbets bestehen dabei jeweils aus 2k Zeichen des ursprünglichen Bandalphabets.
Für jedes Band i gibt es 2 “Spuren”, wovon eine den Inhalt von Band i enthält. In der zweiten Spur befindet sich genau eine 1, die die position des Kopfes auf Band i angibt, und sonst nur 0’en. Somit enhalten wir eine Turing-Maschien Q mit einem “fetten” Band, das alle Informationen über die k Bänder von M enthählt. Diese können nun von einem “Dickkopf” gelesen und der Überführungs-funktion von M entsprechend manipuliert werden.
