Computing Functions
with
Turing Machines
Costas Busch - LSU 1
A function f (w) has:
Domain: D Result Region: S
f (w)
w∈ D f ( w) ∈ S
Costas Busch - LSU 2
A function may have many parameters:
Example: Addition function
f ( x, y ) = x + y
Costas Busch - LSU 3
Integer Domain
Decimal: 5
Binary: 101
Unary: 11111
We prefer unary representation:
easier to manipulate with Turing machines
Costas Busch - LSU 4
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
Costas Busch - LSU 5
In other words:
A function f is computable if
there is a Turing Machine M such that:
∗
q0 w f q f f ( w)
Initial Final
Configuration Configuration
For all w∈ D Domain
Costas Busch - LSU 6
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
Costas Busch - LSU 7
x y
Start ◊ 1 1 L 1 0 1 L 1 ◊
q0
initial state
The 0 is the delimiter that
separates the two numbers
Costas Busch - LSU 8
x y
Start ◊ 1 1 L 1 0 1 L 1 ◊
q0 initial state
x+ y
Finish ◊ 1 1 L 1 1 0 ◊
q f final state
Costas Busch - LSU 9
The 0 here helps when we use
the result for other operations
x+ y
Finish ◊ 1 1 L 1 1 0 ◊
q f final state
Costas Busch - LSU 10
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
Costas Busch - LSU 11
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
Costas Busch - LSU 12
Time 0 ◊ 1 1 0 1 1 ◊
q0
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 13
Time 1 ◊ 1 1 0 1 1 ◊
q0
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 14
Time 2 ◊ 1 1 0 1 1 ◊
q0
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 15
Time 3 ◊ 1 1 1 1 1 ◊
q1
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 16
Time 4 ◊ 1 1 1 1 1 ◊
q1
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 17
Time 5 ◊ 1 1 1 1 1 ◊
q1
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 18
Time 6 ◊ 1 1 1 1 1 ◊
q2
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 19
Time 7 ◊ 1 1 1 1 0 ◊
q3
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 20
Time 8 ◊ 1 1 1 1 0 ◊
q3
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 21
Time 9 ◊ 1 1 1 1 0 ◊
q3
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 22
Time 10 ◊ 1 1 1 1 0 ◊
q3
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 23
Time 11 ◊ 1 1 1 1 0 ◊
q3
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
q4
Costas Busch - LSU 24
Time 12 ◊ 1 1 1 1 0 ◊
q4
1 → 1, R 1 → 1, R 1 → 1, L
q0 0 → 1, R q1 ◊ → ◊, L q2 1 → 0, L q3
◊ → ◊, R
HALT & accept q4
Costas Busch - LSU 25
Another Example
The function f ( x) = 2 x is computable
x is integer
Turing Machine:
Input string: x unary
Output string: xx unary
Costas Busch - LSU 26
x
Start ◊ 1 1 L 1 ◊
q0 initial state
2x
Finish ◊ 1 1 L 1 1 1 ◊
q f accept state
Costas Busch - LSU 27
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
Costas Busch - LSU 28
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
Costas Busch - LSU 29
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
Costas Busch - LSU 30
Another Example
1 if x> y
The function f ( x, y ) =
is computable 0 if x≤ y
Input: x0 y
Output: 1 or 0
Costas Busch - LSU 31
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
Costas Busch - LSU
( x ≤ y) 32
Combining Turing Machines
Costas Busch - LSU 33
Block Diagram
Turing
input output
Machine
Costas Busch - LSU 34
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
Costas Busch - LSU 35