Turing Machine

Question 1

<b><u>Turingmaschine Komponenten</u></b>

Answer 1

1. Band
   - beidseitig offe
   - Enthält die Eingabe
   - andere Zellen enthalten Blank-Symbol
2. Lese-/Schreibkopf
   - ist Anfangs am weitesten Linken Symbol
   - immer über einer Bandzelle positioniert

Question 2

<b><u>Zustand und gelesenes Symbol führen zu:</u></b>

Answer 2

• Zustand wechseln
• Bandsymbol in gelesene Zeile schreiben
• Lese Schreibkopf bewegen (rechts, links oder stillstand)

Question 3

<b><u>Formale Beschreibung</u></b>

Answer 3

Siebentupel: M = (Q, Σ, Γ, δ, q0, B, F)

• Q endliche Menge von Zuständen,
• Σ endliche Menge der Eingabesymbole,
• Γ endliche Menge der Bandsymbole, Σ ⊂ Γ,
• δ : Q × Γ −→ Q × Γ × {L, R, S} Übergangsfunktion,
• q0 ∈ Q Startzustand,
• B ∈ Γ − Σ Blank-Symbol,
• F ⊆ Q Menge von Endzuständen

Question 4

<b><u>Übergänge</u></b>

Answer 4

(q, X; p, Y , D) ∈ δ

M liest im Zustand q auf dem Band Symbol X
- wechselt nun davon abhängig in den Zustand p,
- überschreibt Symbol X durch Symbol Y ,
- bewegt den Lese-/Schreibkopf in die durch D beschriebene
Richtung (D ∈ {L, R, S}).

Question 5

<b><u>DTM Deterministische Turingmaschine</u></b>

Answer 5

Eine Turingmaschine M heißt deterministisch, wenn für alle
(q, X) ∈ Q × Γ höchstens ein Element (q, X; p, Y , D) ∈ δ existiert, D
∈ {L, R, S}; wir schreiben dann auch δ(q, X) = (p, Y , D).

Question 6

<b><u>Konfiguration</u></b>

Answer 6

Am Anfang befindet sich nur das Eingabewort auf dem Band, welches
nach links und rechts mit unendlich vielen Blank-Symbolen umgeben
ist. Die TM ist im Startzustand und der Lese-/Schreibkopf befindet
sich uber dem am weitesten links stehenden Eingabesymbol. ¨
Mit jeder Bewegung ¨andert die TM ihre Konfiguration.

Question 7

<b><u>Akzeptierte Sprache</u></b>

Answer 7

Die von der (deterministischen) Turingmaschine M akzeptierte
Sprache L(M) besteht aus genau all jenen Wörtern, bei deren
Analyse M einen Endzustand erreicht

Question 8

<b><u>Rekursiv aufzählbare Sprache</u></b>

Answer 8

Eine formale Sprache heißt rekursiv aufzählbar wenn sie von einer
(deterministischen) Turingmaschine akzeptiert wird. (Turingmaschine hält an)

Question 9

<b><u>Rekursive (entscheidbare) Sprache</u></b>

Answer 9

Eine formale Sprache heißt rekursiv oder entscheidbar wenn sie von
einer (deterministischen) Turingmaschine akzeptiert wird, die immer
hält. (Man sagt dann auch: die TM entscheidet die Sprache)

Question 10

<b><u>Nichtdeterministische Turingmaschinen</u></b>

Answer 10

Eine NTM M akzeptiert eine Eingabe, wenn es eine Folge möglicher
Bewegungen gibt, die von der Startkonfiguration zu einer
Konfiguration mit einem akzeptierenden Zustand fuhrt.

Zu jeder nichtdeterministischen Turingmaschine MN gibt es eine
deterministische Turingmaschine MD mit L(MN) = L(MD).

Question 11

<b><u>Berechnung von Funktionen</u></b>

Answer 11

Eine (deterministische) Turingmaschine M kann auch zur
Berechnung von Funktionen verwendet werden, d.h., M beginnt
mit dem Input auf dem Band, der Output, also der Funktionswert
zum Input, ist das Ergebnis der Berechnung, wenn M hält.

Question 12

<b><u>Erzeugung von Sprachen</u></b>

Answer 12

Eine (nichtdeterministische) Turingmaschine M kann auch zur
Erzeugung von Wörtern verwendet werden, d.h., M beginnt mit
dem leeren Band, das Ergebnis der Berechnung ist das Wort, das am
Ende einer Berechnung, wenn M hält, auf dem Band steht.

Question 13

<b><u>Rekursive (entscheidbare) Sprachen und ihr Komplement</u></b>

Answer 13

• Das Komplement einer rekursiven Sprache ist rekursiv.

- Ist eine Sprache L und auch ihr Komplement L rekursiv aufzählbar, so
ist L (wie auch L) rekursiv.

Question 14

<b><u>Rekursive und rekursiv aufzählbare Sprachen</u></b>

Answer 14

Konsequenz: Sei L eine Sprache und L ihr Komplement.
Dann gilt eine der folgenden Aussagen:
1 sowohl L als auch L ist rekursiv.

2 sowohl L als auch L ist nicht rekursiv aufzählbar.

3 entweder L oder L ist rekursiv aufzählbar, aber nicht rekursiv,
und die jeweils andere Sprache ist nicht rekursiv aufzählbar.

Question 15

<b><u>Church-Turing-These</u></b>

Answer 15

Gibt es ein endlich beschreibbares Verfahren zur exakten
Spezifizierung einer formalen Sprache L, so gibt es eine
Turingmaschine, die L akzeptiert.

Question 16

<b><u>(Un)Entscheidbarkeit</u></b>

Answer 16

Wenn du sagst, dass du lugst, und das die Wahrheit ist, lügst du ¨
dann oder sprichst du die Wahrheit?

Question 17

<b><u>Das Halteproblem</u></b>

Answer 17

Gibt es einen Algorithmus (eine Turingmaschine), der
(die), gegeben den Code einer beliebigen Turingmaschine M und den
Code eines Eingabewortes w, immer entscheiden kann, ob M auf w
hält, bzw. ob M die Eingabe w akzeptiert?

NEIN!!!!

Question 18

<b><u>Berechenbarkeit</u></b>

Answer 18

Eine Funktion f : Σ∗ −→ Σ
∗ heißt partiell berechenbar, wenn es
eine Turingmaschine Mf gibt, fur die mit ¨ x ∈ Σ
∗ gilt:
Ist f (x) definiert, so h¨alt Mf
, gestartet mit x, und f (x) steht
dann auf dem Band.
Ist f (x) nicht definiert, so h¨alt Mf
, gestartet mit x, nicht.
Ist f total, d. h., fur alle ¨ x ∈ Σ
∗ definiert, und partiell berechenbar,
so heißt f (total) berechenbar.

Question 19

<b><u>Reduktion</u></b>

Answer 19

Reduktion ist eine Technik, die Unentscheidbarkeit von Problemen
durch Ruckf ¨ uhrung auf andere Probleme nachzuweisen, deren ¨
Unentscheidbarkeit bereits bekannt ist.

Question 20

<b><u>Reduktionen und (Nicht-)Entscheidbarkeit</u></b>

Answer 20

Seien A und B Sprachen mit A ≤ B. Dann gilt:

Ist A nicht entscheidbar, so ist auch B nicht entscheidbar.

Ist A nicht rekursiv aufzählbar, so ist auch B nicht rekursiv
aufzählbar.

Ist B entscheidbar, so ist auch A entscheidbar.

Ist B rekursiv aufzählbar, so ist auch A rekursiv aufzählbar.

Question 21

<b><u>Der Satz von Rice</u></b>

Answer 21

“Jede nicht triviale Eigenschaft der rekursiv aufz¨ahlbaren Sprachen ist
unentscheidbar.”

Eine Eigenschaft ist trivial, wenn sie entweder leer ist (d.h., sie
kommt keiner Sprache zu), oder aus allen rekursiv aufz¨ahlbaren
Sprachen besteht. Andernfalls ist sie nicht trivial.