**Basics**

*. In general number - theoretic function in*

Consider only those functions whose arguments and values are natural numbers. Such functions are called

Consider only those functions whose arguments and values are natural numbers. Such functions are called

number - theoreticnumber - theoretic

n variable is considered as f

_{2,}...,x

_{n}>.

Any function f : N

On the other hand, if f: D ® N where D Í N

Any function f : N

^{n}® N is called**total**because it is defined for every n-tuple in N^{n}.On the other hand, if f: D ® N where D Í N

^{n}, then f is called**partial.**

Examples:

Examples:

- f
= x+y which is defined for all x, y N and hence is a total function. - g
= x-y which is defined for only those x, y N, which satisfy x > y.

Hence gis partial.

**Initial Functions:**

Consider a set of three functions called the initial functions, which are used in defining other functions by induction.

Z : Z(x) = 0 Zero function

S : S(x) = x+1 Successor function

The projection function is also called generalized identity function.

Examples:

Examples:

The operation of composition will be used to generate other functions. Composition of functions idea can be extended to

functions of more than one variable.

For example, let f

_{1}

_{2}

_{1}, and f

_{2}is a function h

given by h

_{2}

For h to be non-empty, it is necessary that the domain of g include where and are the ranges of f

_{1}and f

_{2}

respectively. Also the domain of h is where and are the domains of f

_{1}and f

_{2}respectively.

If f

_{1}, f

_{2 }and g are total, then h is also total. In general, let f

_{1}, f

_{2}, …, f

_{n}each be partial functions of m variables, and let g be a

partial function of n variables. Then the composition of g with f

_{1},f

_{2},…,f

_{n}produces a partial function h given by

h

_{2},....,x

_{m}> = g

_{2},…,x

_{m}>,…,f

_{n}

_{2},…,x

_{m}>>.

It is assumed that the domain of g includes the n - tuples , I

_{n}={1,2,.....,n} and

_{}denotes the range of f

_{i}. Also the

domain of h is given by ,where is the domain of f

_{i}. The function h is total iff f

_{1}, f

_{2},...,f

_{n}, and g are total.

Let f

_{1}

f

_{2}

^{2}and

g

Then, h

_{2}

= g

= (x+ y)(xy+y

^{2}).

Here h is total, because f

_{1}, f

_{2}, and g are all total.

Given a function f

_{2},...,x

_{n}> of n variables and consider n - 1 of the variables as fixed and vary only the remaining variable

over the set of natural numbers or over a subset of it. For example, fix x and vary y in f

f

Example:

Example:

If f

Solution:

Solution:

First evaluate f<2,1>, f<2,2> and finally f<2,3>. Each functional value is computed by adding 1 to the previous value until the

desired result is obtained.

The computation of f<2,3> is

f<2,3> = [(f<2,0>+1)+1]+1

= [(2+1)+1)+1

= [3+1]+1

= 4+1

= 5.

**Recursion:**

It is assumed that we have a mechanism by which we can determine the value of the function when an argument is zero and also

its value for the argument n + 1 from the value of the function when the argument is n.

*The arguments which are considered to*

be fixed are called.

be fixed are called

**parameters**, while the one which is assumed to vary is considered a**variable***f*

The following operation which defines a function

The following operation which defines a function

_{2},…,x

_{n},y>

*of n+1 variables by using two other functions*

g

_{2},…,x

_{n}>

*and*h

_{2},…,x

_{n},y,z>

*of n and n+2 variables, respectively, is called*

f

**recursion**._{2},...,x

_{n},0> = g

_{2},...,x

_{n}>

f

_{2},...,x

_{n},y+1> = h

_{2},...,x

_{n },y,f

_{2},...,x

_{n},y>>

In this definition, the variable y is assumed to be the inductive variable in the sense that the value of f at y +1 is expressed in terms

of the value of f at y. The variables x

_{1},x

_{2},…, x

_{n }are treated as parameters and are assumed to remain fixed throughout the

definition. Also it is assumed that both the functions g and h are known. We shall now impose restrictions on g and h which will

guarantee that the function f which is defined recursively, as above, can actually be computed and is total.

*
*

**4.1.2 Primitive Recursive Function**

A function f is called

of composition and recursion

A function f is called

**primitive recursive**iff it can be obtained from the initial functions by a finite number of operationsof composition and recursion

From the definition it follows that it is not always necessary to use only the initial functions in the construction of a particular

primitive recursive function. If we have a set of functions f

_{1},f

_{2},…,f

_{k}which are primitive recursive, then we can use any of these

functions along with the initial functions to obtain another primitive recursive function, provided we restrict ourselves to the

operations of composition and recursion only.

In the examples given here, first we construct some primitive recursive functions by using the initial functions alone, and then we

use these functions wherever required in order to construct other primitive recursive functions. All primitive recursive functions

are total.

Example 1:

Example 1:

Show that the function f

**x+(y+1) = (x+y)+1.**

Solution:

Solution:

Therefore f

f

Define f

f

f

Here the basic function is

g(x) = .

and the inductive step function is

h

For example using these definition, we can compute the value of f<2,> we have

f<2,> = 2.

f<2,> = S(f<2,>

= S(S(f<2,>))

= S(S(S(f<2,>)))

= S(S(S(S(f<2,>))))

= S(S(S(S(2))))

= S(S(S((3))))

= S(S(4)) = S (5) = 6

Example 2:

Example 2:

Using recursion, define the multiplication function * given by g

Solution:

Solution:

Since g

g

g(x, y + 1) = f < <>>,

**The following are some of the primitive recursive functions which are used frequently.**

Sign function or non zero test function, sg : - Zero test function, : (0) = 1, (y + 1) = 0.

- Predecessor function, P :

P(0) = 0 P(y+1) = y = (y, P(y)).

Note that

P(0) = 0 , P(1) = 0 , P(2) = 1 , P(3) = 2.

- Odd and even parity function, Pr :

Pr(0) = 0, Pr(y + 1) = (r (y)>))

P_{r}(0) = 0, P_{r}(1) = 1, P_{r}(2) = 0, P_{r}(3) = 1, ……

- Proper subtraction function,
__•__:

x__•__0 = x, x__•__(y + 1) = p ( x__•__y).

Note that x__•__y = 0 for x• y = x - y for x y.

- Absolute value function, | | :

|x – y| = (x__•__y) + (y__•__x)

- min (x , y) = minimum of x and y

min (x , y) = x__•__(x__•__y).

max= maximum of x and y

= y + (x__•__y).

- The square function, f(y) = y
^{2}

f(y) = y^{2 }= (y) * (y)

sg(0) = Z(0) sg(y+1) = S(Z(<>)).

Example 3:

Example 3:

Show that f

^{y}is primitive recursive function.

Solution:

Solution:

Note that x

^{0}= 1 for x 0 and we put x

^{0}= 0 for x = 0.

Also x

^{y+1}= x

^{y}

^{ }* x

^{ }; hence f<> = x

^{y}is defined as

f

f

= <>> * <>>

Example 4:

Example 4:

Show that if f

Solution:

Solution:

For y=0, f

Also the value of f

equal to 0 and the process continues.

We therefore build a function which increases by 1 each time y increases by 1, that is, S(f

Now we multiply this function by another primitive recursive function which becomes 0 whenever

S(f

Also this other function must be 1 whenever S(f

But S(f

__•__S(f

Thus the required definition of f

f

f

__•__S(f

Example 5:

Example 5:

Show that the function [x/ 2] which is equal to the greatest integer which is x/2 primitive recursive.

Solution:

Solution:

Now [0/2] = 0.

[1/2] = 0.

[2/2] = 1.

[3/2] = 1, etc., so that [x/2] = x/2 when x is even and [x/2] = (x-1)/2 when x is odd.

In order to distinguish between even and odd functions, we have defined the parity function, which is primitive recursive.

[0/2] = 0,

[(y+1)/2] = [y/2] + P

_{r}(y)

where P

_{r}(y) denotes the parity function which is 1 when y is odd and which is 0 when y is even.

**
**

4.1.3 Primitive Recursive Set

Any set R Í N

^{n}defines a number - theoretic n-ary relation.

The characteristic function of a relationThe characteristic function of a relation

*R can be now defined as*

Here R Í N1, x

A relation R is said to be

predicate is also called primitive recursive.

Here R Í N

^{n}and_{2}, . . ., x

_{n}> N

^{n}.

A relation R is said to be

**primitive recursive**if its characteristic function is primitive recursive. The corresponding

predicate is also called primitive recursive.

**Show that {**

Example 1:

Example 1:

Solution:

Solution:

Obviously f

f

Thus f

**Show that for any fixed k the relation given by {**

Example 2:

Example 2:

**sg(y**

Solution:

Solution:

__•__k) is the characteristic function of the required relation.

**Show that the function f**

Example 3:

Example 3:

_{2}, y> defined as

Is primitive recursive.

Solution:

Solution:

The required function can be expressed as

x

_{2}+ (x

_{1}* y) * (x

_{1 }

__•__y).

*
*

**4.1.4 Recursive Function**

**Regular Function:**

Let g <>1, x

g <>1, x

Let g <>1, x

_{2},…, x_{n}, y > be a total function. If there exists atleast one value of y, say Î N, such that the functiong <>1, x

_{2},…, x_{n}, > = 0 for all n - tuples <>1, x_{2},…,x_{n}> Î N^{n}then g is called a**regular function.**

Not all total functions are regular, as can be seen from g <> = | y

^{2 }– x |. g <> is total, but |y

^{2}–x| = 0 for only those

values of x which are perfect squares and not for all values of x. This fact shows that there is no value of y Î N such that

| y

^{2 }– x | = 0 for all x. On the other hand, the function y

__•__x is regular because for y=0, y

__•__x is zero for all x.

**Minimization:**

*A*

where m

**function f**1, x _{2},…, x

_{n}> is said to be defined from a total function

**g <>1, x**

m operationif_{2}, ..., x_{n}, y> by minimization orm operation

where m

_{y}means the least y greater than or equal to zero.From the definition it follows that f <>1, x

_{2}, … , x

_{n}> is well-defined and total if g is regular. If g is not regular, then the

operation of minimization may produce a partial function.

Recursive Function:

Recursive Function:

*A function is said to be*

the operations of composition, recursion, and minimization over regular functions.

**recursive**iff it can be obtained from the initial functions by a finite number of applications ofthe operations of composition, recursion, and minimization over regular functions

It is clear from the definition that the set of recursive function properly includes the set of primitive recursive functions. Also the

set of recursive functions is closed under the operations of composition, recursion, and minimization over regular functions.

**Partial Recursive Function:**

A function is said to be

applications of the operations of composition, recursion, and minimization.

A function is said to be

**partial recursive**iff it can be obtained from the initial functions by a finite number ofapplications of the operations of composition, recursion, and minimization.

Example 1:

Example 1:

Show that the function f (x) = x/2 is a partial recursive function

**Solution:**

Let g

The function g is not regular because |2y – x| = 0 only for even values of x.

Define f(x) = m

_{y}( | 2y – x| ), then f (x) = x/2 for x even.

Example 2:

Example 2:

Let [] be the greatest integer

_{ }. Show that [] is primitive recursive.

Solution:

Solution:

Observe that (y + 1)

^{2}

__•__x is zero for (y + 1)

^{2 }£ x and non-zero for (y + 1)

^{2}> x.

Therefore, ((y + 1)

^{2 }

__•__x) is 1 if (y + 1)

^{2}x and cannot be equal to zero.

The smallest value of y for which (y + 1)

^{2}> x is the required number [] , hence

[] = m

_{y}(((y + 1)

^{2}

__•__x)) = 0.

Note that [] is defined for all x and hence is a recursive function.

**
**

4.1.5 Recursive Sets

A set A is called recursive (partial recursive) if its characteristic function is recursive (partial recursive). For any two sets

A and B with characteristic function and , the characteristic functions of A

_{}B and A

_{}B can also be obtained.

Example 1:

Example 1:

Show that the sets of even and odd natural numbers are both recursive.

Solution:

Solution:

The parity function is the required characteristic function for the set E of even natural numbers. Hence E is primitive recursive.

Also the set of odd natural numbers is ~E (complement of E), hence ~E is also primitive recursive.

Example 2:

Example 2:

Show that set of divisors of a positive integer n is recursive.

Solution:

Solution:

A number x n is a divisor of n iff | x * i - n| is equal to zero for one fixed value of i, 1 £ i £ n.

This means that | x * i - n | is non zero for all 1 £ i £ n, if x is not a divisor.

Therefore, the characteristic function of the required set is

where B denotes the set of divisors of n.

Note:

Note:

A predicate whose extension is a set of integers is said to be a number-theoretic predicate. Such a predicate is primitive

recursive (recursive) iff its extension is primitive recursive (recursive). The characteristic function of a predicate is the

characteristic function of its extension. If A is the extension of predicate P and Y

_{P}denotes the characteristic function of the

predicate P, then Y

_{P}= Y

_{A }

For example, the predicates "is even" and "is a divisor of n" are recursive because their extensions are recursive sets.

If A and B are the extensions of predicates P and Q respectively, then by definition.

Y

_{P }

_{Ú}

_{Q}= Y

_{AÈ B}Y

_{P }

_{Ù}

_{ Q}= Y

_{A Ç B}Y

_{ù }

_{P}= Y

_{~}

_{ A }

It directly follows that if P and Q are recursive, then so are predicates P Ú Q, P Ù Q, and ù P.

Example 3:

Example 3:

Let D (x) denote " number of divisors of x". Show that D(x) is primitive recursive.

Solution:

Solution:

We have shown that the function which defines the remainder upon division of y by x is primitive recursive. We shall denote

such a function by rm

divisors of y is given by

This shows that D (y) is primitive recursive.

Example 4:

Example 4:

Show that the predicate "x is prime" is primitive recursive.

Solution:

Solution:

A number x is a prime iff it has only two divisors 1 and x, also if it is not 1 or 0. Therefore, the characteristic function of the

extension of "x is not a prime" is

Note:

Note:

In our discussion we considered only one induction variable in the definition of recursion. It is possible to consider two or more

induction variables. Note that in the definition of f

_{2},…,x

_{n},y> using recursion, x

_{1},x

_{2},…,x

_{n}were treated as parameters and

only y was treated as the induction variable. Now we define a function in which we have two induction variables and no

parameters.

Consider Ackermann's function. The function A

A<> = y + 1.

A<> = A <>.

A <> = A <>>.

A

Example 5:

Example 5:

Evaluate A <2,2> using the above definitions.

Solution:

Solution:

A<> = A<>>

A<> = A<>>

A<2,> = A<>

A<> = A<> >

= A<>>

A<> = 2

A<> = A<>

= 3

A<> = A<>

= A<>>

A<> = A<>>

= A<>

= 4

A<> = A<>

= 5

A<> = A<>

= A<>>

A<> = A<>>

A<> = A<>>

= A<>

= 5

A<> = A<>

= 6

A <> = A <>

= 7.

Algorithm Prime:

Algorithm Prime:

Given an integer i greater than 1, this algorithm will determine whether the integer is a prime number. Note that the only divisors

of a prime number are 1 and the number itself.

- Set j ¬ 2.
- If j ³ i then output " i is prime" and Exit.
- If j / i then output " i is not prime" and Exit.
- Set j ¬ j + 1, goto step 2.

Algorithm Perfect:

Algorithm Perfect:

This algorithm decides whether there exists a perfect number greater than some integer i. Consider the set of all divisors of a

number except the number itself. A perfect number is one whose sum of all such divisors equals the number. The number 6 is a

perfect number since 1 + 2 + 3 = 6.

- Set k ¬ i.
- Set k ¬ k + 1.
- Set SUM ¬ 0.
- Set j ¬1.
- If j <>
- If SUM = k then output k and Exit, otherwise go to step 2.
- If j / k then set SUM ¬ SUM + j. Set j ¬ j + 1 and go to step 5

## 1 comment:

Here is another definition of function as-A function is a special relationship between values: Each of its input values gives back exactly one output value.It is often written as "f(x)" where x is the value you give it.Example:

f(x) = x/2 ("f of x is x divided by 2") is a function, because for every value of "x" you get another value "x/2", so:

=> f(16) = 8.

bay s theorem

Post a Comment