ITEC 420  Section 3.1  Turing Machines
Turing Machine: Introduction
 Turing Machines can recognize all computable languages
 We will leave the notion of computable language as intuitive
 We will see welldefined languages that are NOT computable with a TM (or
in any other known way)
 We will see that all known ways of computing have the same power
as the TM (or less)
 Implementation: TM = FSM + Tape!
A Turing Machine's Tape
 Tape is infinite (in one direction)
 Tape is initialized with input at left end
 Rest of tape has blanks
 Blank not in input alphabet
 Tape has R/W head:
 Reads and writes the symbol under the head at each transition
 Moves one symbol left or right at each transition
 Attempts to move past left end of tape leave tape at
left end of tape
 Machine can NOT tell where on the tape the head is
Example Turing Machine
 A = {w#w  w ∈ {
0,1
}*}
 Algorithm intution: ... (p 139)
Turing Machine: Halting a Computation
 Computation can do one of three things:
 End (immediately) by entering a special Accept state
 End (immediately) by entering a special Reject state
 Continue forever (ie never enter Accept or Reject state)
 For comparison, consider the halting conditions for these machines:
Turing Machine Accepts a String
 Machine M accepts string w if w takes
M to the Accept State of M
Turing Machines: More Examples
 A = {w#w  w ∈ {
0,1
}*}
 Formal specification of machine: (Example 3.9, p. 145)
 B = {ww  w ∈ {
0,1
}*}
 Algorithm: How would we find the center of the string? ...
 C =
{
a
^{n}b
^{n}c
^{n}  n ≥ 0}
 D = {0^{2n}  n ≥ 0} (Example 3.7, p 143, 144)
Formal Definition of a TM
 Must define seven items:
 Q is the set of state
 Σ is the input alphabet (does not include
the blank symbol)
 Γ is the tape alphabet, blank ∈ Γ
and Σ ⊆ Γ
 δ: (state, tape symbol) →
(state, tape symbol, L/R)
 Start state
 Accept state
 Reject state (different from start state)
 Transition function: δ(q,b) →
(r,c,D) means
the machine is in state q and the tape head is over a
b. The machine then writes an c onto the tape
(erasing the
b), goes into state r, and moves direction D
on the tape.

Shorthand notation: a → D means to read and write and a
and to move direction D
 Deterministic or nondeterministic?
Configuration of a TM
 Show tape head position by writing current state to left of symbol
it is over:
 Example:
1011
q_{7}01111
 Tape contents are
101101111
, tape head is over rightmost 0, and machine is in state q_{7}
 tape head is over rightmost 0, and machine is instate q_{7}
 machine is in state q_{7}
 Accepting/Rejecting Configuration
 Machine halts when machine enters Accept or Reject State!
 Tape head can be anywhere!
TM Computation: Formal Definition
 A computation is a sequence of configurations of machine M
in which
 First configuration in the sequence has M in the
start state with M's head at the left of the tape
 Each step in the sequence moves M to the next configuration
with a single read, a single write, and a single move
TM Accepts a String: Formal Definition
 Machine M accepts string w iff there is a computation that
 Starts with the start configuration of w on M (ie
w written on left end of tape and R/W head at left end)
 M takes each configuration in the computation to the next
configuration
 The computation ends in an accepting configuration (ie in the accept
state)
 No surprises here, but remember the head can be anywhere at the end of the
computation
Recognizing a Language
 The language recognized by machine M
is the collection of strings accepted by M
A Turing Recognizable Language
 A language that is recognized by a machine is called a Turing
Recognizable language
 Later we'll see that there is some subtlety here
 For now, remember that language L is TR,
if there is a TM M for which
all strings in L put M in its accept state.
 So, how do we prove that a language is TR?
 Question: What about strings that are not in L?