Turing Machines
A Turing Machine
Tape
...... ......
Read-Write head
Control Unit
Standard
Turing
Machine
(STM)
The Tape
No boundaries -- infinite length
...... ......
Read-Write head
The head moves Left or Right
...... ......
Read-Write head
The head at each transition (time step):
1. Reads a symbol
2. Writes a symbol
3. Moves Left or Right
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 Accept
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
(yields in one mode)
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
A computation
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
a a b b
q0
The Accepted Language
For any Turing Machine M
L( M ) = {w : q0 w x1 q f x2 }
Initial state Accept state
If a language L is accepted
by a Turing machine M
then we say that Lis:
•Turing Recognizable
Other names used:
•Turing Acceptable
•Recursively Enumerable
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 qf
initial state accept 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 here helps when we use
the result for other operations
x+ y
Finish 1 1 1 1 0
q f final state
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
Turing machine for function f ( x, y ) = x + y
Turing machine for function f ( x, y ) = x + y
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 → , L q2 1 → 0, L q3
→ , R
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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 2
1 → 0, L q3
→ , 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 accept 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 ) =
is computable 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
Comparator
x y Eraser 0
