Turing Maschinen I

Question 1

Σ*

Answer 1

Kleenesche Abschluss von Σ, enthält alle Wörter über Σ

Question 2

Problem als Relation R ⊆ Σ* x Σ’*

Answer 2

Ein Paar (x,y) liegt in R, wenn y eine Ausgabe zur Eingabe x ist

Question 3

Problem als Funktion f : Σ* -> Σ’*

Answer 3

Suche Ausgabe f(x) ϵ Σ’* zur Eingabe x ϵ Σ*

Question 4

Entscheidungsproblem-Form

Answer 4

f : Σ* -> {0,1}

Question 5

L=f^-1 (1) ⊆ Σ*

Answer 5

Die zu dem f definierten Entscheidungsproblem gehörende Sprache

Question 6

Turingmaschine Definition

Answer 6

7-Tupel (Q, Σ, Γ, B, q0, q-, δ)

Question 7

Q

Answer 7

endliche Zustandsmenge

Question 8

Σ

Answer 8

endliche Eingabealphabet

Question 9

Γ ⊃ Σ

Answer 9

endliche Bandalphabet

Question 10

B ϵ Γ\Σ

Answer 10

Blank

Question 11

q0

Answer 11

Anfangszustand

Question 12

q-

Answer 12

Endzustand

Question 13

δ : ( Q{q-} ) x Γ -> Q x Γ x {R,L,N}

Answer 13

Zustandsüberführungsfunktion

Question 14

Ende der Berechnung der TM

Answer 14

TM stoppt, wenn sie den Endzustand erreicht. Ausgabewort vom Band beginnend mit Kopfposition lesen.

Question 15

M entscheidet L, wenn…

Answer 15

M auf jeder Eingabe hält und M genau die Wörter aus L akzeptiert.

Question 16

Wenn TM eine Sprache entscheidet, so muss sie immer

Answer 16

halten

Question 17

Eine Funktion f : Σ* -> Σ* heißt rekursiv(Turing-berechenbar), wenn…

Answer 17

es eine TM gibt, die aus der Eingabe x den Funktionswert f(x) berechnet.

Question 18

Eine Sprache L ⊆ Σ* heißt rekursiv(Turing-entscheidbar), wenn…

Answer 18

es eine TM gibt, die für alle Eingabe terminiert und die Eingabe w genau dann akzeptiert, wenn w ϵ L ist.

Question 19

Konfiguration einer TM

Answer 19

String αqβ mit qϵQ und α, β ϵ Γ*

Question 20

α’q’β’ direkte Nachfolgekonfiguration von αqβ, falls…

Answer 20

α’q’β’ in einem Rechenschritt aus αqβ entsteht.

Question 21

α’‘q’‘β’’ Nachfolgekonfiguration von αqβ, falls…

Answer 21

α’‘q’‘β’’ in endlich vielen Rechenschritten aus αqβ entsteht.

Question 22

k-spurige TM

Answer 22

eine TM, bei der das Band in k Spuren eingeteilt ist. Der Kopf kann k Zeichen gleichzeitig lesen.

Question 23

Speicher im Zustandsraum der TM erweitern

Answer 23

Qneu = Q x Γ^k

Question 24

Bandalphabet von Mehrspurmaschinen erweitern

Answer 24

Γneu = Γ ∪ Γ^k

Question 25

Laufzeit

Answer 25

Anzahl von Zustandsübertragungen bis zur Terminierung

Question 26

Speicherbedarf

Answer 26

Anzahl von Bandzellen, die während der Berechnung besucht werden

Question 27

M berechnet f : Σ* -> Σ’*, wenn…

Answer 27

für jedes Wort wϵ Σ* M auf Eingabe w terminiert und dabei die Ausgabe f(w) hat.