In the ‘Turing machine as integer function’ section of the chapter ‘Extension of the Turing Machine’, different integer functions such as addition, subtraction, multiplication, remainder finding, square, etc. are constructed using the Turing machine. These are the basic functions. By combining these basic functions, complex functions are constructed. As the basic functions are computable, the complex functions are also computable.
Like the theory of the Turing machines, the recursive function theory is a way to make formal and precise the intuitive, informal, and imprecise notion of an effective method. Like the theory of the Turing machines, the recursive function theory also obeys the converse of the Church’s thesis. The base of the recursive function is some very elementary functions that are naturally effective. Then, it provides a few methods for constructing more complex functions from those simpler functions. The initial functions and the steps for building complex functions are very few in number, and very simple in character.
A function is a relation that associates each element of a set with an element of another set. Let a function f be defined between two sets A and B. There must be a relation between A and B such that for an element a ∈ A, there must be another element b ∈ B, such that (a, b) is in the relation.
The relation given by f between a and b is represented by the ordered pair <a, b> and denoted as f(a) = b, and b is called the image of a under f.
11.1.1 Different Types of Functions
22.214.171.124 One to One or Injective
A function from set A to set B is said to be one-to-one if no two elements of set A have exactly the same elements mapped in set B. In other words, it can be said that f(x) = f(y) if and only if x = y.
Example: f(x) = x + 4. Let x = 1, 2, 3, . . . . . . (set of all positive integer numbers). This is an injective function because f(1) = 5, f(2) = 6, f(3) = 7 . . . . . . , for no two elements of set A there is exactly the same value in set B.
Diagrammatically, it can be shown as follows.
But if there is a function f(x) = x2, where x is the set of real numbers then f(x) is not injective because for x = 2 and –2; in both cases, f(x) results in 4 which violates the condition of the injective function.
126.96.36.199 Onto or Surjective
A function f from set A to a set B is said to be surjective (or onto), if for every y ∈ Y, there is an x ∈ X resulting in f(x) = y. In other words, each element of the set B can be obtained by applying the function f to some element of A.
Example: f(x) = 2x from A → B, where A is the set of natural numbers and B is the set of non-negative even numbers. Here, for every element in B, there is an element in A.
Diagrammatically, it can be shown as follows.
A function f is said to be bijective if it is both injective and surjective.
Example: The example f(x) = 2x of surjective is also bijective.
Diagrammatically, it can be shown as follows.
Let us define a function f to be a bijection from a set A to set B. Suppose another function g is defined from B to A such that for every element y of B, g(y) = x, where f(x) = y. Then, the function g is called the inverse function of f, and it is denoted by f−1.
Example: If f(x) = 5x from the set of natural numbers A to the set of non-negative even numbers B, then g(x) = f−1(x) = 1/5 x.
188.8.131.52 Composite Function
Let f(x) be a function from a set A to set B, and let g be another function from set B to a set C. Then, the composition of the two functions f and g, denoted by fg, is the function from set A to set C that satisfies fg(x) = f(g(x)) for all x in A.
Example: f(x) = x2 and g(x) = (x + 2). Then, fg(x) = f(g(x)) = (x + 2)2
11.2 Initial Functions
For a set of natural numbers N, three types of functions can be defined.
- Zero function : A zero function returns 0 for all values. It is denoted as
The zero function is also called constant function.
- Successor function : A successor function takes one number as argument and returns the succeeding number. It can be denoted as
- Projection function:A projection function is an n-ary projection function denoted by , where n ≥ 1 and 1 ≤ i ≤ n, takes n arguments, and returns the ith element.
It can be denoted as (x1, x2, x3, ….. xn) = xi.
11.3 Recursive Function
We are familiar with the term ‘recursion’ at the time of doing computer programming using some middle level or high level programming languages such as C, C++ Java, etc. A function which calls itself and terminates after a finite number of steps is called a recursive function.
For every recursive, there must be a base condition using which the function terminates.
Example: fact(x) = x × fact(x – 1), where x is a positive integer number and fact(0) = 1.
If x = 4, then
184.108.40.206 Partial and Total Function
A partial function f from a set A to set B is defined as a function from A′ to B where A′ is a subset of A. For all x ∈ A, there may exist f(x) = y ∈ B or f(x) is undefined.
Example: Let A and B be two sets of positive integer numbers. A function f(x) is defined as . The relation A → B only exists if x ∈ A is a perfect square such as 4, 9, 16, 25, . . . etc. f(16) is defined but f(20) is undefined.
If A′ = A, then the function f(x) is called a total function.
Example: f(x) = x + 1, where x ∈ the set of integer numbers is a total function as f(x) is defined for all values of x.
220.127.116.11 Partial Recursive Function
A function computed by the Turing machine that need not halt for all input is called a partial recursive function. A partial recursive function is allowed to have an infinite loop for some input values.
18.104.22.168 Total Recursive Function
Partial recursive functions for which the Turing machine always halts are called the total recursive function. The total recursive function always returns a value for all possible input values.
From the discussion, it is clear that the total recursive function is a subset of the partial recursive function.
Example: Prove that the addition of two positive integers is a total recursive function.
Solution: f(x, y) = x + y, where x, y ∈ set of positive integer numbers.
f(x, 0) = x + 0 = x is the base condition.
Here, recursion occurs.
Thus, the function of the addition of two positive integers is recursive. The function is defined (returns a value) for all value of x, y, which proves it a total recursive.
22.214.171.124 Primitive Recursive Function
Primitive recursive functions are a subset of the total recursive function which can be obtained by a finite number of operations of composition and recursion from the initial functions (zero and successor function).
where g and h are primitive recursive functions.
Solution: The primitive recursive function consists of the initial function (zero function, successor function, and projection function), composition, and recursion. If there exists a Turing machine for all these, then there exists a Turing machine for the primitive recursive function.
- Turing machine for zero function
It is nothing but an eraser. There exists a Turing machine for an eraser.
- Turing machine for successor function
The function adds a ‘1’ with the value of x. If one blank symbol at the right hand side is replaced by ‘1’, then the machine can be easily designed.
- A projection function is denoted as (x1, x2, x3, . . . . . xn) = xi.
A Turing machine can be designed which takes input Bx1Bx2Bx3B . . . . . . BxnB and produces the output BxiB.
- A Turing Machine can be designed for composition of different functions by combining the respective Turing machines for each of the function in the order in which the functions appear.
- Turing machine for recursive functions can be designed by combining the Turing Machine designed for the simple function with multiple call and the Turing Machine designed for the Base function as termination point.
- A final TM can be designed using the TMs for steps (4) and (5).
Hence, it is proved that every primitive recursive function is Turing computable.
Prove that the function f(x, y) = x + y where x, y are positive integers is primitive recursive.
Let f(4, 3) be given.
Prove that the function f(x, y) = x – y, where x, y are positive integers, is primitive recursive.
The function can be obtained by composition and recursion from the zero and successor functions in a finite number of steps. Thus, it is primitive recursive.
Let f(4, 2) be given.
Prove that the function f(x, y) = x * y, where x, y are positive integers, is primitive recursive.
We have already proved that addition is primitive recursive, thus multiplication is primitive recursive.
Let f(3, 2) be given.
Prove that the function f(x, y) = xy, where x, y are positive integers, is primitive recursive.
We have already proved that multiplication is primitive recursive, thus exponential is primitive recursive.
Let f(4, 2) be given.
Prove that the function
where x is a positive integer which is primitive recursive.
If x is even, then x + 1 is odd.
If x is odd, then x + 1 is even.
The given function can be rewritten as
Hence, it is primitive recursive.
Prove that the function fact(x) is primitive recursive.
As the multiplication function is primitive recursive, fact is also primitive recursive.
Prove that the bounded addition of the primitive recursive function is also primitive.
Solution: If f(m, n) is a primitive recursive function, then we have to prove that is primitive recursive.
Thus, it is also primitive recursive.
(It can also be proved in the same way that the bounded product of primitive recursive functions is also primitive recursive.)
11.4 Gödel Number
In the late 19th century, two properties of a formal system were the cause of brainstorming for the logicians and mathematicians. The properties were completeness and consistency. Completeness is defined as the possibility to prove or disprove any proposition that can be expressed in the system. On the other hand, consistency is the impossibility to both prove and disprove a proposition in a system. Using the axioms of set theory, many mathematicians try to prove these properties of a formal system.
A British philosopher and logician Bertrand Arthur William Russell in 1901 discovered a paradox known as the Russell’s paradox.
11.4.1 Russell’s Paradox
S is defined as the set of all sets that are not members of themselves. Is S a member of itself?
From this paradox, two conditions appear for S.
- If S is an element of S, then S is a member of itself and should not be in S.
- If S is not an element of S, then S is not a member of itself, and should be in S.
In this context, Kurt Gödel, an Australian (later American), proposed a theorem in 1931 known as the Gödel Incompleteness Theorem. The theorem states that ‘if a formal theorem is consistent, then it is impossible to prove within the system that it is inconsistent.’
The concept of the Gödel number was used by Gödel in proving his famous incompleteness theorem. The Gödel numbering is a function that assigns each symbol and a well-formed formula of some formal language to a unique natural number. It can also be used as an encoding scheme that assigns a unique number to each symbol of a mathematical notation. The Gödel numbering encodes a sequence of numbers in a single value. The scheme of converting a sequence of natural numbers uses the factorization of a natural number into a product of prime numbers.
The Gödel number for a sequence x0, x1, . . . . . . xn − 1 for n natural numbers is defined as
where pn(n) is the nth prime number.
As an example, the sequence 2, 1, 0, 3 is encoded as 22 · 31 · 50 · 73 = 4116. The sequence 1, 0, 2, 1 is encoded as 21 · 30 · 52 · 71 = 350.
Decoding a Gödel number G to obtain the sequence is the reverse process. The steps are
- Prime factorize the given number.
- Arrange the obtained primes in sequence, starting from the least and raise appropriate power with the number of times they appear. If any prime number in between two does not appear, raise the power as ‘0’.
As an example, take a number 10780. The prime factorization of the number results in 2 × 2 × 5 × 7 × 7 × 11 = 22 × 51 × 72 × 111.
In the sequence ‘3’ is missing, though 3 is a prime number in between 2 and 5. Thus, the modified sequence with power raised to each prime is 22 × 30 × 51 × 72 × 111.
Hence, the sequence is (2, 0, 1, 2, 1).
The function for constructing a Gödel number is not one to one. Two different sequences may have the same Gödel number. These two sequences are different with the number of ‘0’ at last. As an example, the sequences (2, 0, 1) and (2, 0, 1, 0, 0) have the same Gödel number.
11.5 Ackermann’s Function
The German mathematician Wilhelm Friedrich Ackermann discovered a function which proves that all total computable functions are not primitive recursive. This function is named after him and known as the Ackermann’s function.
For two non-negative integers x and y, the Ackermann’s function is defined as
For every non-negative integer x and y, the function A(x, y) can be computed. So, it is a total function.
Here, we are not getting a zero function, which proves that it is not primitive recursive.
Example: Compute A(1, 3).
Example: Compute A(2, 2).
Suppose there is a function f(x) which has a least value of x which makes f(x) = 0. Now, it is told to find that least value. We shall consider x = 0, 1, 2, . . . . . and calculate f(x) correspondingly. Where f(x) = 0 is achieved, that value of x is the least value. The process will stop within a finite amount of time after a finite number of steps. Let g(x) be a function which computes the process of finding the least value of x such that f(x) = 0. So, g is computable. It is said that g is produced from f by minimization.
As an example, let f(x, y) = 2x + y – 5, where x and y are both positive integers (I).
This is a total function as for every positive integer value of x and y, there is a value of f(x, y).
We have to find the range of x for which y ∈ I.
Make f(x, y) = 0, i.e., 2x + y – 5 = 0
→ y = 5 − 2x
Consider this function as g(x, y). We can write
Let g be a k + 1 argument function. The unbounded minimalization of g is a k argument function f such that for every arguments n1, n2, . . . . . nk
But if such an f(x) is given for which it is not known whether there exists an x for which f(x) = 0, then the process of testing may never terminate. This is called unbounded minimalization. If g is produced by unbounded minimization, then it is not effectively computable as there is no surety of termination.
If the searching is set to an upper limit, then the function g can be made computable. The search process will find a value which makes f(x) = 0 and the function g will return that value if such a value is found. Otherwise, g will return 0. This is called bounded minimization as a boundary of search process is specified.
Bounded minimalization is defined by the search operator over the natural numbers ≤ y
It defines a function f which returns the least value of z satisfying p(x1, . . . , xn, z) or returns the bound. More precisely, it can be written as
11.7 μ Recursive
A function is said to be μ recursive if it can be constructed from the initial functions and by a finite operation of:
- Primitive recursion
- Unbounded minimalization (μ operation)
This type of function was first proposed by Gödel and Stephen Kleene.
It can be proved that ‘a function is computable by a Turing machine if it is μ recursive’.
11.7.1 Properties of a μ Recursive Function
- The zero function, successor function, and projection function are μ recursive.
- If f is a m variable μ recursive function and g is a n variable μ recursive function, then f(g1, g2, . . . gn) is also μ recursive.
- If f and g are n and n + 2 variable μ recursive functions, then a new function, say h constructed from f and g by primitive recursion, is μ recursive.
An interesting story of proof correction for printing is hidden in λ calculus. We are coming to the point but will first discuss the history of λ calculus. In 1900, a German mathematician David Hilbert gave a speech at the International Congress of Mathematicians in Paris. He pointed out 23 mathematical problems, and among them the 10th was to find an algorithm that tests whether a polynomial has an integral root and which will terminate within a finite number of steps. Church and Turing later on separately proved that the problem is undecidable.
Principia Mathematica, a book on the foundations of mathematics written by Alfred North Whitehead and Bertrand Russell in 1910–1913, depicted the function f(x) = 2x + 1 as · 2x + 1. At the time of proof correction, this became ^x · 2x + 1 and at the time of the final proof correction it became λ · 2x + 1 !
Should a function have a name? The λ calculus started from this point. Let there be a total function named ‘cube’ which calculates the cube of an integer. This can be defined as a cube: integer → integer, where cube(x) = x3 such that x ∈ integer.
There is no significance of the name ‘cube’ unless it is defined. Now the question comes, whether a function can be defined without a name?
Church used the notation λ (Originally ^, then modified to λ at the time of proof correction by others) to represent a function without a name. He used it as λx · x3, which maps each x ∈ integer set to x3 ∈ another integer set.
Let an expression be given as x2 + 2y. For the value of (2, 3), it gives two different results 10 and 13, because the order is not mentioned. Someone can take x = 2 and y = 3 whereas someone may take x = 3, y = 2. The λ notation resolves this ambiguity by specifying the order as λx · λy · x2 + 2y or λy · λx · x2 + 2y if x = 2 and y = 3 or x = 3, y = 2, respectively.
Let a function be defined as λx · λy · x2 + 2y. It can be redesigned to an equivalent function which accepts a single value and returns another function as output. The output function is the function of a single variable. This is called currying. As an example, the previous function can be redesigned as
where the value of y is given the input first. Let x = 5 and y = 2.
If currying is applied, the value is calculated as
To calculate the result of a function using λ calculus, we need to know the β reduction.
A β reduction is the process of calculating a result from the application of a function to an expression.
Let a function be given as λx · x2 + 2xy. Suppose we apply the function to value 7. For calculating the result, the value 7 is substituted for every occurrence of x. The resultant function becomes 49 + 14y.
It can be proved that a function N → N, where N is a set of natural numbers, is a computable function if and only if there exists a λ expression f such that for every pair of x, y in N, F(x) = y if and only if fx′ = β is reducible to y′, where x′ and y′ are the Church numerals corresponding to x and y, respectively.
11.9 Cantor Diagonal Method
Rational numbers are infinite. Let us represent all rational numbers by a set S1 containing infinite numbers. The decimal numbers are also infinite. Can the decimal number be represented by a set as rational number? The Cantor diagonal method answers this question. Rational numbers are said to be countable infinite, whereas decimal numbers are uncountable. (Consider all real numbers between 0 and 1 which can be represented as the terminating decimal (such as 0.345) or infinitely repeating decimal such as .345345345 . . . . . . . )
The diagonal principle uses the cardinality principle with contradiction.
Suppose the number of decimal numbers can be represented by a set as rational number and represented by a set S2. As the two sets (S1 and S2) have the same cardinality, there must exist a bijective relation between the elements of the two sets. Consider the decimal numbers between 0 and 1. Make a one to one correspondence with the rational numbers in S1 as shown in the following.
Now, consider a decimal number x = 0 · x1x2x3x4 . . . . . . . , where xi is any digit other than dii (the diagonal elements). X is a decimal number and located between 0 and 1. Thus, x must be in the previous list. X is not the first element, as its first position after the decimal point is not d11. x is not the second element, as its second position after the decimal point is not d22. By this process, it is not the nth element as its nth digit is not dnn. Thus, x is not in the list. A contradiction appears. It means that some decimal elements are left to be listed. This proves that ‘listing’ the decimal numbers is impossible, and so the infinity of decimal numbers is greater than the infinity of counting numbers.
11.10 The Rice Theorem
The Rice theorem states the following.
Let P be a non-trivial property of Turing recognizable languages. The problem ‘does L(M) has the property P?’ is undecidable.
In other words, it can be said that ‘any non-trivial property about the language recognized by a Turing machine is undecidable.’
Before discussing the theorem, we need to discuss two important definitions, namely ‘property’ and ‘non-trivial property’.
Non-Trivial Property: Let P be a property of Turing recognizable language. The property P is said to be non-trivial if there exists L1 and L2, two Turing recognizable languages such that L1 ∈ P but L2 ∉ P.
Trivial Property: A property P is called a trivial property if P is Ø or P = L, where L is a Turing recognizable language.
Proof of the Rice Theorem: The Rice theorem is proved by reducing this to halting problem. P is a non-trivial property of the Turing recognizable language. Thus, there exists some language L ∈ P. As L is Turing recognizable, there must exist a Turing machine ML accepting L.
Assume that P is decidable. So, there must exist a Turing machine MP which decides whether L(M′) ∈ P or not for any machine M′.
Design a pre-processor MPrep which takes <M, w> as input and generates a new machine M′ such that if M accepts w, then and only L(M′) ∈ L. This is represented by the following figure.
In this section, the internal operation of MPrep is discussed. MPrep takes <M, w> as input and generates M′ as output as discussed previously. We need to know what kind of machine M′ is. M′ simulates M using a fixed input w ignoring the actual input x. If M does not halt on w, M′ will surely not halt on x irrespective of what x is. But if M halts on w, then x is given input on ML and accepts if ML halts.
This means that on input w if M halts, then M′ accepts the same string as ML. This means that L(M′) = L as L ∈ P. On the other hand, if M does not halt on w, then M′ does not accept any input. This means L(M′) = Ø.
From the previous discussion, we are getting a solution to the halting problem. Already it is proved that the halting problem is undecidable. So, our assumption is wrong, which proves that MP cannot exist.
What We Have Learned So Far
- In an injective function, there exists a one to one relationship between the elements of two sets.
- A function is called surjective between two sets if each element of a set can be obtained by applying the function to some element of another set.
- A function is bijective if it is both injective and surjective.
- The initial functions are zero function, successor function, and projection function.
- A zero function returns a 0 for all values.
- A successor function returns the succeeding number of the argument taken as the input.
- A projection function takes n number of argument as the input and returns the ith element.
- A partial recursive function is allowed to have an infinite loop for some input values.
- The total recursive function always returns a value for all possible input values.
- Primitive recursive functions can be obtained by a finite number of operations of composition and recursion from the initial functions.
- Every primitive recursive function is Turing computable.
- The Gödel numbering is a function that assigns each symbol and a well-formed formula of some formal language to a unique natural number.
- A μ recursive function is constructed from the initial functions and by a finite operation of: composition, primitive recursion, and unbounded minimalization.
- The Cantor diagonal method proves that real numbers are uncountable.
- The Rice theorem says that ‘any non-trivial property about the language recognized by a Turing machine is undecidable.’
- The Fibonacci numbers are defined as follows
Show that FIB: N → N is primitive recursive.
Solution: The Fibonacci series is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . . .
Let us compute FIB(n).
Look into the lines in bold. The numbers associated with FIB are (1, 1), (2, 1), (3, 2), (5, 3), . . . . . . Introduce a helper function h such that h(y) = (FIB(n – 1), FIB(n)). From the previous sequence, it is clear that h(0) = (1, 1).h(y + 1) = ((left(h(y) + right(h(y)), left(h(y)))
To calculate FIB(n), we need to construct (n – 1) sequences [take FIB(6) or FIB(5)] to get the terminating conditions [FIB(0) and FIB (1)] · h(y) returns the sequence of coefficient of FIB(n – k) and FIB(n – k + 1), respectively, which ultimately ends on FIB(1) and FIB(0). Thus, FIB(n + 1) produce results after n number of steps with a finite number of operations of composition and recursion from the initial functions. This proves that FIB(n) is primitive recursive.
- Find the Gödel equivalent number of the sequence (3, 0, 2, 0, 1, 0, 1).
Solution: There are seven numbers in the sequence. The first five prime numbers are 2, 3, 5, 7, 11, 13, and 17. So, the Gödel equivalent number of the sequence is
- Find the sequence for the number 56208 using the Gödel principle.
Solution: The prime factorization of the number is 2 × 2 × 2 × 2 × 3 × 11 × 11.→ 24 × 31 × 112 = 24 × 31 × 50 × 70 × 112
Thus, the sequence is (4, 1, 0, 0, 2).
- Compute A(2, 1) using the Ackermann’s function.
Solution: The Ackerman’s function is defined as
Multiple Choice Questions
- The function where no two elements of one set have exactly the same elements mapped in another set is called
- The function where for every element of one set there is an element in another set is called
- Zero function always returns
- Find the true statement
- The partial recursive function always returns a value.
- The total recursive function may be in an infinite loop.
- In both of these cases, the Turing machine must halt.
- The partial recursive function may be in an infinite loop.
- Which is true for the Gödel number
- One number can have more than one Gödel sequence
- Two different Gödel sequences may produce the same number
- (a) and (b) are correct if two sequences are different with the number of ‘0’ at last.
- The Gödel sequence of a number is not unique.
- According to the Ackermann’s function, if x > 0 and y = 0, then A(x, y) is
- y + 1
- A((x – 1), 1)
- A((x – 1), A(x, (y – 1))
- x + 1
- A function is said to be μ recursive if it can be constructed from the initial functions and by a finite operation of
- Primitive recursion
- Unbounded minimalization (μ operation)
- All of these
- For (3, 2), the function λy · λx · x2 + 2y returns
- Prove that proper subtraction of two numbers defined as
is primitive recursive.
- Prove that the modulus operation is primitive recursive.
- A function f(n) is defined as
Check whether f(n) is primitive recursive or not.
- Prove that addition and multiplication of two positive integers is a total function.
- Show that a function Max defined as
is primitive recursive.
- Evaluate the Ackermann’s function for A (2, 2), A(3, 1).
- Calculate λy · λx · x3 + 2xy + y2 for (3, 1) and (3, 2)