Bài giảng Lý thuyết tính toán - Chương 5: Hàm đệ quy

1Lý thuyết tính toán
(Theory of Computation) i
PGS.TS. Phan Huy Khánh
khanhph@vnn.vn
Chương 5
Hàm đệ quy
2/32
Chương 5 Hàm đệ quy
 Recursive Function Theory
 Gödel's Incompleteness Theorem
 Zero, Successor, Projector Functions
 Functional Composition
 Primitive Recursion
 Proving Functions are Primitive Recursive
 Ackermann's Function
3/32
Maths Functions
An example function:
Domain Range
We need a way to define functions
We need a set of basic functions
N
3
N
10
f(n) = n2 + 1
f(3) = 10
4/32
Computation
 Get N a set of Natural Numbers :
N = { 0, 1, 2, … }
 Building the functions on N
For examples :
x + y
x * y
xy
x2 + y2
are computable functions
5/32
Complicated Functions
x  ( y + z)
 is complicated functions from the addition and 
multiplication function
 is computable:
there is a sequence of operations
of the addition and the multiplication
Attention :
There are also many functions that are not composed
from the basis functions
6/32
Factorial function:
n! = n  (n-1)  (n-2)  …  2  1
is computable :
there is a sequence of multiplication operations 
 The factorial function is not alone the composition of the 
addition and multiplication operations 
 The number of multiplication oprations depends on n
Function is computable
27/32
Factorial function is a recursive definition:
0! = 1
(n + 1) ! = (n + 1)  n !
Uses the recursivity to define some functions
f(n + 1)
is defined from: 
f(n)
Start at:
f(0)
Recursivity
8/32
Function is computable
Why is computable?
 Basic primitive recursive functions:
 Computation on the natural number N
 Primitive Recursive Function:
 Any function built from the basic primitive recursive 
functions
9/32
Computable functions
 Basic set of Recursive primitive functions
 Primitive Recursive Functions :
 Mechanism for composition of functions
by combining previously-defined functions
composition and/or recursive definitions
Clearly they are infinite in number
Some can have any arity (unary, binary, …)
f(n1, n2, …, nm), m  1
10/32
Gödel's Incompleteness Theorem
 “Any interesting consistent system must be incomplete; 
that is, it must contain some unprovable propositions”
 Hierarchy of Functions
1. Primitive-Recursive Functions
2. Recursive (-recursive) Functions
3. Interesting well-defined Functions but "unprovable"
 BB Function
11/32
Primitive Recursive Functions
 Defined over the domain I = set of all non-negative 
integers
 or domain I×I
 or domain I×I×I, etc.
 Definition:
Functions are said to be Primitive Recursive
if they can be built 
 from the basic functions (zero, successor, and projection) 
 using functional composition and/or primitive recursion
12/32
Zero, Successor, Projector Functions
 Zero function:
z(x) = 0, for all x  I
 Successor function:
s(x) = x+1
 Projector functions:
p1(x1, x2) = x1
p2(x1, x2) = x2 
313/32
Example of Primitive Recursives
 Constants are Primitive Recursive:
2 = s(s(z(x)))
3 = s(s(s(z(x))))
5 = s(s(s(s(s(z(x))))))
 Addition & Multiplication
 add(x, 0) = x
add(x, y+1) = s(add(x, y))
 mult(x, 0) = 0
mult(x, y+1) = add(x, mult(x, y))
14/32
Subtraction
 pred(0) = 0
pred(x+1) = x
 monus(x, 0) = x // called subtr in text
monus(x, y+1) = pred(monus(x, y))
 absdiff(x, y) = monus(x, y) + monus(y, x)
15/32
Other Primitive Recursive Functions
 Factorial & Exponentiation
 fact(0) = 1
fact(n+1) = mult(s(n), fact(n))
 exp(x, 0) = 1
exp(x, n+1) = mult(x, exp(x, n))
 Test for Zero (Logical Complement)
 test(0) = 1
test(x+1) = 0
16/32
Operators
 Relational Operators
 equal(x, y) = test(absdiff(x, y))
 geq(x, y) = test(monus(y, x))
 leq(x, y) = test(monus(x, y))
 gt(x, y) = test(leq(x, y))
 lt(x, y) = test(geq(x, y))
 Minimum & Maximum
 min(x, y) = lt(x, y)*x + geq(x, y)*y
 max(x, y) = geq(x, y)*x + lt(x, y)*y
17/32
 Division
 remaind(numerator, denominator) = rem(denominator, numerator)
 rem(x, 0) = 0
rem(x, y+1) = s(rem(x, y))*test(equal(x, s(rem(x, y))))
 div(numerator, denominator) = dv(denominator, numerator)
 dv(x, 0) = 0
dv(x, y+1) = dv(x, y) + test(remaind(y+1, x))
 Square Root
 sqrt(0) = 0
 sqrt(x+1) = sqrt(x) +
equal(x+1, (s(sqrt(x))*s(sqrt(x))))
18/32
 Test for Prime
 numdiv(x) = divisors_leq(x, x)
 divisors_leq(x, 0) = 0
divisors_leq(x, y+1)
= divisors_leq(x, y) + test(remaind(x, y+1))
 is_prime(x) = equal(numdiv(x), 2)
 { a  b mod c }
 congruent(a, b, c)
= equal(remaind(a, c), remaind(b, c))
419/32
Greatest Common Divisor
(can’t use Euclidean Algorithm—not P.R.)
 gcd(a, 0) = a
gcd(a, b+1) = find_gcd(a, b+1, b+1)
 find_gcd(a, b, 0) = 1
find_gcd(a, b, c+1) =
(c+1)*test_rem(a, b, c+1) +
find_gcd(a, b, c)*test(test_rem(a, b, c+1))
 test_rem(a, b, c) =
test(remaind(a, c))*test(remaind(b, c))
20/32
Functional Composition
 f(x, y) = h(g1(x, y), g2(x, y))
 from previously defined functions g1, g2, and h
 e.g.:
 min(x, y) = lt(x, y)*x + geq(x, y)*y
 h(x, y) = add(x, y)
 g1(x, y) = mult(lt(x, y), p1(x, y))
 h = mult(), g1=lt(), g2=p1()
 g2(x, y) = mult(geq(x, y), p2(x, y))
 h = mult(), g1=geq(), g2=p2()
21/32
Primitive Recursion
 Composition:
 f(x, 0) = g1(x)
 f(x, y+1) = h(g2(x, y), f(x, y))
 Note: Last argument defined at zero and y+1 only
 e.g.:
 exp(x, 0) = 1
exp(x, n+1) = x * exp(x, n)
 g1(x) = s(z(x))
 h(x, y) = mult(x, y)
 g2(x, y) = p1(x, y)
22/32
Ackermann's Function
 We can actually give an example of a total Turing-computable function 
that is not primitive recursive, namely Ackermann’s function:
 A(0, n) = n+1
 A(m+1, 0) = A(m, 1)
 A(m+1, n+1) = A(m, A(m+1, n))
 For example,
 A(0, 0) = 1
 A(0, 1) = 2
 A(1, 1) = A(0, A(1, 0)) = A(0, A(0, 1))
 = A(0, 1) + 1 = 3.
23/32
Ackermann's Function
 Theorem
 For every unary primitive recursive function f,
there is some m such that f(m) < A(m, m)
 So A cannot be primitive recursive itself
24/32
Ackermann's Function
Ackermann's Function is NOT Primitive Recursive
 Just because it is not defined using the "official" rules of 
primitive recursion is not a proof that it IS NOT primitive 
recursive
 Perhaps there is another definition that uses primitive 
recursion
 (NOT!) Proof is beyond the scope of this course…
525/32
"Meaning" of Ackermann's Function
(addition, multiplication, exponentiation, tetration)
A(1,0)  2; A(1,1)  3; A(1,2 )  4; A(1,n)  2  (n  3) 3
A(2,0)  3; A(2,1)  5; A(2,2)  7; A(2,n)  2 *(n  3)  3
A(3,0) 5; A(3,1) 13; A(3,2)  29; A(3,3)  61; A(3, 4) 125; A(3,n)  2
n3
 3
A(4,0)  13; A(4,1)  65531; A(4,2)  2
65534
3; A(4,n)  2
2
2
... 2
2{n  3 times}
 3
26/32
Rates of growth
Ackerman’s function and friends
Iterated exponentials
Exponential functions
• A(m.n)
• 3n • n!
Polynomial functions
• n3+3n2+2n+1• 2n+5
• nn
• n n
n
 Growth of Ackerman’s function:
A(0, n) = n+1 ; A(1, n) = n+2 ; A(2, n) = 2n+3
A(3, n) = 2n + 3 – 3 A(4, n) = 2 - 3 with n powers of 2
27/32
Countable Sets
 Countable if it can be put into a 1-to-1 correspondence
with the positive integers
 You should already be familiar with the enumeration 
procedure for the set of RATIONAL numbers 
[diagonalization, page 278]
 Quick review…
 You should already be familiar with the fact (and proof)
that the REAL numbers are NOT countable
 Quick review…
28/32
Recursively Enumerable Languages
 A language is said to be recursively enumerable
if there exists a Turing machine that accepts it.
 That is, if the accepting machine is started on a word
in the language, it will halt in qf
 This says nothing about what the machine will do
if it is presented with a word that is not in the language 
 (i.e. whether it halts in a non-final state or loops)
29/32
Recursive Languages
 A language, L, is recursive if there exists a Turing machine 
that accepts L and halts on every w in +
 That is, there exists a membership decision procedure for L
30/32
Existence of Languages that are not 
Recursively Enumerable
 Let S be an infinite countable set
Then its powerset 2S is not countable
 Proof by diagonalization
 Recall the fact that the REAL numbers are not countable
 For any nonempty , there exist languages that are not 
recursively enumerable.
 Every subset of * is a language
Therefore there are exactly 2* languages
 However, there are only a countable number of Turing 
machines
Therefore there exist more languages than Turing machines 
to accept them
631/32
Recursively Enumerable but not Recursive
We can list all Turing machines that eventually halted
on a given input tape (say blank) 
 Recall the enumeration procedure for TM’s from last period
 Once a string of 0’s and 1’s was verified as a valid TM,
we would simply run it (while non-deterministically continuing 
to list other machines). [Note how long this would take!]
 A halt on the part of the simulation (recall the Universal 
Turing Machine) would trigger adding the TM in question to 
the list of those that halted. (copying it to another tape?)
 However, we cannot determine (and always halt)
whether or not a given TM will halt on a blank tape
 Stay tuned for the unsolvability of the Halting Problem...
32/32
The hierarchy of functions
 Recall that a function f :
 Nk  N is total if f is defined on every input from Nk
 and is partial if we don’t insist that it has to be total.
All partial functions from Nk to N
The computable partial functions
The computable total functions
The primitive recursive functions
• ?
• n
• A(m,n)
• add(m,n)