Turing Machines

The Language Hierarchy

n n n
a b c ? ww ?

Context-Free Languages
n n R
a b ww
Regular Languages
a* a *b *
 Languages accepted by
Turing Machines
n n n
a b c ww

Context-Free Languages
n n R
a b ww
Regular Languages
a* a *b *
 A Turing Machine
Tape
...... ......

Read-Write head
Control Unit
 The Tape

No boundaries -- infinite length

...... ......

Read-Write head

The head moves Left or Right

 ...... ......

Read-Write head

The head at each time step:

1. Reads a symbol
2. Writes a symbol
3. Moves Left or Right
Example:
Time 0
...... a b a c ......

Time 1
...... a b k c ......

1. Reads a
2. Writes k
3. Moves Left
 Time 1
...... a b k c ......

Time 2
...... a f k c ......

1. Reads b
2. Writes f
3. Moves Right
 The Input String

Input string Blank symbol

......   a b a c    ......

head

Head starts at the leftmost position

of the input string
 Input string Blank symbol

......   a b a c    ......

head

Remark: the input string is never empty

 States & Transitions

Read Write
Move Left

q1 a  b, L q2

Move Right

q1 a  b, R q2
Example:
Time 1
......   a b a c    ......

q1
current state

q1 a  b, R q2
 Time 1
......   a b a c    ......

q1

Time 2
......   a b b c    ......

q2

q1 a  b, R q2
Example:
Time 1
......   a b a c    ......

q1

Time 2
......   a b b c    ......

q2

q1 a  b, L q2
Example:
Time 1
......   a b a c    ......

q1

Time 2
......   a b b c g   ......

q2

q1   g, R q2
 Determinism
Turing Machines are deterministic

Allowed Not Allowed

a  b, R q2 a  b, R q2

q1 q1
q3 a  d, L q3
b  d, L

No lambda transitions allowed

 Partial Transition Function
Example:

......   a b a c    ......

q1

a  b, R q2 Allowed:

q1 No transition
for input symbol c
b  d, L q3
 Halting

The machine halts if there are

no possible transitions to follow
Example:

......   a b a c    ......

q1

a  b, R q2
No possible transition
q1
HALT!!!
b  d, L q3
 Final States

q1 q2 Allowed

q1 q2 Not Allowed

• Final states have no outgoing transitions

• In a final state the machine halts

 Acceptance

If machine halts
Accept Input
in a final state

If machine halts
in a non-final state
Reject Input or
If machine enters
an infinite loop
 Turing Machine Example

A Turing machine that accepts the language:

aa *

a  a, R

  , L
q0 q1
Time 0   a a a  

q0

a  a, R

  , L
q0 q1
Time 1   a a a  

q0

a  a, R

  , L
q0 q1
Time 2   a a a  

q0

a  a, R

  , L
q0 q1
Time 3   a a a  

q0

a  a, R

  , L
q0 q1
Time 4   a a a  

q1

a  a, R Halt & Accept

  , L
q0 q1
Rejection Example

Time 0   a b a  

q0

a  a, R

  , L
q0 q1
Time 1   a b a  

q0

No possible Transition
a  a, R Halt & Reject

  , L
q0 q1
 Infinite Loop Example
A Turing machine
for language aa * b( a  b) *

b  b, L
a  a, R

  , L
q0 q1
Time 0   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1
Time 1   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1
Time 2   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1
Time 2   a b a  
q0
Time 3   a b a  

Infinite loop
q0

Time 4   a b a  
q0

Time 5   a b a  
q0
Because of the infinite loop:

•The final state cannot be reached

•The machine never halts

•The input is not accepted

Formal Definitions
for
Turing Machines
 Transition Function

q1 a  b, R q2

 (q1, a )  (q2 , b, R)
 Transition Function

q1 c  d, L q2

 (q1, c)  (q2 , d , L)
Turing Machine:

Input Tape
alphabet alphabet
States

M  (Q, , ,  , q0 , , F )

Transition Final
function states
Initial blank
state
 Configuration

  c a b a  

q1

Instantaneous description: ca q1 ba
 Time 4 Time 5
 x a y b    x a y b  

q2 q0

A Move: q2 xayb  x q0 ayb

 Time 4 Time 5
 x a y b    x a y b  

q2 q0

Time 6 Time 7
 x x y b    x x y b  

q1 q1

q2 xayb  x q0 ayb  xx q1 yb  xxy q1 b

q2 xayb  x q0 ayb  xx q1 yb  xxy q1 b


Equivalent notation: q2 xayb  xxy q1 b
Initial configuration: q0 w

Input string
w

 a a b b  

q0
 The Accepted Language

For any Turing Machine M


L( M )  {w : q0 w  x1 q f x2 }

Initial state Final state

 Standard Turing Machine

The machine we described is the standard:

• Deterministic

• Infinite tape in both directions

•Tape is the input/output file

Computing Functions
with
Turing Machines
A function f (w) has:

Domain: D Result Region: S

f (w)
w D f ( w)  S
A function may have many parameters:

Example: Addition function

f ( x, y )  x  y
 Integer Domain

Decimal: 5

Binary: 101

Unary: 11111

We prefer unary representation:

easier to manipulate with Turing machines

Definition:

A function f is computable if
there is a Turing Machine M such that:

Initial configuration Final configuration

 w   f (w) 

q0 initial state q f final state

For all w D Domain

In other words:

A function f is computable if
there is a Turing Machine M such that:


q0 w  q f f ( w)

Initial Final
Configuration Configuration

For all w D Domain

 Example

The function f ( x, y )  x  y is computable

x, y are integers

Turing Machine:

Input string: x0 y unary

Output string: xy 0 unary

 x y

Start  1 1  1 0 1  1 

q0
initial state

The 0 is the delimiter that

separates the two numbers
 x y

Start  1 1  1 0 1  1 

q0 initial state

x y

Finish  1 1  1 1 0 

q f final state
 The 0 helps when we use
the result for other operations

x y

Finish  1 1  1 1 0 

q f final state
Turing machine for function f ( x, y )  x  y

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
Execution Example: Time 0
x y
x  11 (2)
 1 1 0 1 1 
y  11 (2)
q0

Final Result
x y
 1 1 1 1 0 

q4
 Time 0  1 1 0 1 1 

q0

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 1  1 1 0 1 1 

q0

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 2  1 1 0 1 1 

q0

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 3  1 1 1 1 1 

q1

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 4  1 1 1 1 1 

q1

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 5  1 1 1 1 1 

q1

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 6  1 1 1 1 1 

q2

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 7  1 1 1 1 0 

q3

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 8  1 1 1 1 0 

q3

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 9  1 1 1 1 0 

q3

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 10  1 1 1 1 0 

q3

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 11  1 1 1 1 0 

q3

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
q4
 Time 12  1 1 1 1 0 

q4

1  1, R 1  1, R 1  1, L

q0 0  1, R q1   , L q 1  0, L q3
2

  , R
HALT & accept q4
 Another Example

The function f ( x)  2 x is computable

x is integer

Turing Machine:

Input string: x unary

Output string: xx unary

 x

Start  1 1  1 

q0 initial state

2x

Finish  1 1  1 1 1 

q f final state
Turing Machine Pseudocode for f ( x)  2 x

• Replace every 1 with $

• Repeat:
• Find rightmost $, replace it with 1

• Go to right end, insert 1

Until no more $ remain

Turing Machine for f ( x)  2 x

1  $, R 1  1, L 1  1, R

q0   , L q1 $  1, R q2
  , R   1, L
q3
 Example
Start Finish
 1 1   1 1 1 1 
q0 q3
1  $, R 1  1, L 1  1, R

q0   , L q1 $  1, R q2
  , R   1, L
q3
 Another Example

1 if x y
The function f ( x, y ) 
0 if x y
is computable
Turing Machine for

1 if x y
f ( x, y ) 
0 if x y

Input: x0 y

Output: 1 or 0
Turing Machine Pseudocode:

• Repeat

Match a 1 from x with a 1 from y

Until all of x or y is matched

• If a 1 from x is not matched

erase tape, write 1 ( x  y)
else
erase tape, write 0 ( x  y)
Combining Turing Machines
 Block Diagram

Turing
input output
Machine
 Example: x  y if x  y
f ( x, y ) 
0 if x  y

x, y
Adder x y
x, y x y
Comparer

x y Eraser 0
Turing’s Thesis
Turing’s thesis:

Any computation carried out

by mechanical means
can be performed by a Turing Machine

(1930)
Computer Science Law:
A computation is mechanical
if and only if
it can be performed by a Turing Machine

There is no known model of computation

more powerful than Turing Machines
Definition of Algorithm:

An algorithm for function f (w)

is a
Turing Machine which computes f (w)
Algorithms are Turing Machines

When we say:
There exists an algorithm

We mean:
There exists a Turing Machine
that executes the algorithm