Turing Machines Flashcards
Definition 3.1 (Turing machine)
A Turing machine is a 7-tuple, M = (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, Γ are all finite sets and
- Q is the set of states,
- Σ is the input alphabet not containing the blank symbol t
- Γ is the tape alphabet, where t ∈ Γ and Σ ⊆ Γ,
- δ : Q × Γ → Q × Γ × {L, R} is the transition function,
- q0 ∈ Q is the start state,
- qaccept ∈ Q is the accept state, and
- qreject ∈ Q is the reject state, where qreject != qaccept.
Definition 3.2 (Configuration of a TM)
Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a Turing machine, u ∈ Γ
∗
, v ∈ Γ
ω and q ∈ Q. The setting
u q v
is a configuration of the Turing machine, where
u is the current tape content to left of the head,
q is the current state, and
v is the current tape content below (v1) and to
the right of the head (being terminated by
blanks t).
Definition 3.3 Let Σ be an alphabet. Then Σω …
is the set of all infinite strings over Σ.
Definition 3.4 Yield TM
Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a Turing machine, a, b, c ∈ Γ, u ∈ Γ∗, v ∈ Γω and qi
, qj ∈ Q. A configuration C1 yields a configuration C2 if M can
legally go from C1 to C2 in a single step. Hence, we say
(leftward move): ua qi bv yields u qj acv
if it holds δ(qi
, b) = (qj , c, L),
(rightward move): ua qi bv yields uac qj v
if it holds δ(qi
, b) = (qj , c, R),
(L-move, left tape end): qi bv yields qj cv
if it holds δ(qi
, b) = (qj , c, L),
(R-move, left tape end): qi bv yields c qj v
if it holds δ(qi
, b) = (qj , c, R).
Definition 3.5 (Characterization of configurations)
Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject)
be a Turing machine and C = u q v a configuration of M. We call C
start configuration on input w ∈ Σ
∗
, if u = ε, i.e. head is at leftmost end of
tape, q = q0 and v = w ◦ {t}ω
,
accepting configuration, if q = qaccept,
rejecting configuration, if q = qreject,
halting configuration, if it is accepting or rejecting configuration.
Definition 3.6 (Accepted input & recognized language)
Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a Turing machine and w ∈ Σ
∗
its input. M
accepts w, if a sequence of configurations C1, C2, . . . , Ck exists, such that
1. C1 is start configuration on input w
2. Ci yields Ci+1, i = 1, . . . , k − 1, and
3. Ck is accepting configuration.
The language of M is
L(M) := {w ∈ Σ
∗
|M accepts w} .
We say that L(M) is recognized by M.Definition 3.7 (Computation of a TM)
Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a Turing machine and w ∈ Σ
∗
its input. A
computation of M on w is a sequence of configurations C1, C2, . . ., such that
1. C1 is start configuration on input w
2. Ci yields Ci+1, i = 1, . . . , k − 1, and
Definition 3.8 (Turing Recognizable Languages)
A language is called Turing-recognizable or recursively enumerable if some Turing machine recognizes it.
Definition 3.10 (Decider)
We call a TM M a decider, if it halts on all inputs w ∈ Σ∗.
A decider M that recognizes L(M) is said to decide L(M).
Definition 3.11 (Decidable languages)
We call a language Turing-decidable, decidable or recursive if there exists a TM (i.e. a decider), that decides it.
Definition 3.12 (Multitape Turing machine)
A multitape Turing machine with k
tapes is a 7-tuple, M = (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, Γ are all finite sets
and
1. Q is the set of states,
2. Σ is the input alphabet not containing the blank symbol t
3. Γ is the tape alphabet, where t ∈ Γ and Σ ⊆ Γ,
4. δ : Q × Γ k → Q × Γ k × {L, R}^k is the transition function,
5. q0 ∈ Q is the start state,
6. qaccept ∈ Q is the accept state,
7. qreject ∈ Q is the reject state, where qreject != qaccept.
Theorem 3.1 A language is Turing-recognizable if and only if…
some multitape Turing machine recognizes it.
Theorem 3.2 For every multitape Turing machine M,
there exists a singletape Turing machine S that recognizes the same language.
Definition 3.13 (Nondeterministic Turing machine)
A nondeterministic Turing machine (NTM) is a 7-tuple, N = (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, Γ are all finite sets and
- Q is the set of states,
- Σ is the input alphabet not containing the blank symbol t
- Γ is the tape alphabet, where t ∈ Γ and Σ ⊆ Γ,
- δ : Q × Γ → P(Q × Γ × {L, R}) is the transition function,
- q0 ∈ Q is the start state,
- qaccept ∈ Q is the accept state.
- qreject ∈ Q is the reject state, where qreject != qaccept.
Definition 3.14 (Configuration of an NTM)
Let N = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a
nondeterministic Turing machine, u ∈ Γ∗, v ∈ Γ ω and q ∈ Q. The setting u q v is a configuration of the Turing machine, where
u is the current tape content to left of the head,
q is the current state, and
v is the current tape content below (v1) and to the
right of the head (being terminated by blanks t).
