State the following functions: Partial, Constant and Total.
(W-22)
Partial Function
A partial function is not defined for every input.
It gives output only for some inputs.
For other inputs, the result is undefined.
Example:
f(x) = 1/x
Not defined when x = 0 → So it is a partial function.
Constant Function
A constant function always gives the same output.
No matter what input you give, the output doesn’t change.
Example:
f(x) = 5
f(1) = 5, f(100) = 5 → Always same.
Total Function
A total function is defined for every input in the domain.
It gives a valid result for all inputs.
Example:
f(x) = x + 2
It works for all values of x → So it's a total function.
Describe: Recursive function. Prove that every recursive
function is computable.(W-22)
Recursive Function
A recursive function is a function that calls itself to solve a smaller version of a problem until it
reaches a base case (a stopping point).
It helps break a big problem into smaller, manageable parts.
Example:
To calculate factorial of a number n!:
factorial(n) = n * factorial(n-1)
Base case:
factorial(0) = 1
Characteristics of Recursive Function
1. Base Case – It defines when the recursion should stop.
2. Recursive Case – It calls itself with a smaller input.
3. Progress – Each step gets closer to the base case.
What is Computable?
A function is computable if we can write a step-by-step algorithm (or program) that gives an
answer for every valid input in finite time.
Proof: Every Recursive Function is Computable
Step-by-step Proof:
1. Recursive functions are defined using rules:
o Basic functions: zero function, successor function, and projection
function.
o Built using operations: composition, recursion, and minimization.
2. Every rule in recursive function can be translated into an algorithm:
o Algorithms can be implemented using machines like Turing
Machines or real programs.
3. Turing Machines can simulate recursive functions:
o Whatever a recursive function does, a Turing Machine can do.
o So, recursive function = computable function.
4. Therefore, every recursive function is computable because:
o We can design a program or machine that always gives an
answer in finite steps.
Write a note on Primitive Recursive functions.(S-24,S-22)
What are Primitive Recursive Functions?
Primitive recursive functions are a special kind of functions used in
computer science and math.
They always give an answer.
They never go into an infinite loop.
These functions always stop and give a result.
Key Features of Primitive Recursive Functions
Three Basic Functions
1. Zero Function: Always returns 0
Z(x) = 0
2. Successor Function: Adds 1 to a number
S(x) = x + 1
3. Projection Function: Picks one input from many inputs
P₂(x, y) = y
Main Operations Used
Composition: Combining functions together
Primitive Recursion: Defining functions using smaller inputs step-by-
step
Examples of Primitive Recursive Function: Addition
Base Case
add(x, 0) = x
(Adding 0 gives the same number)
Recursive Case
add(x, y+1) = add(x, y) + 1
(Add 1 step by step using previous result)
Example: add(2, 3)
add(2, 3) = add(2, 2) + 1
add(2, 2) = add(2, 1) + 1
add(2, 1) = add(2, 0) + 1
add(2, 0) = 2 (base case)
Now going back:
add(2, 1) = 2 + 1 = 3
add(2, 2) = 3 + 1 = 4
add(2, 3) = 4 + 1 = 5
Define: 𝜇-Recursive functions and show how all
computable functions are 𝜇 recursive.(S-23)
What are μ-Recursive Functions?
1. μ-recursive functions are used in computability theory.
2. They are more powerful than primitive recursive functions.
3. They can use loops and may not always stop.
4. They use the μ-operator to find the smallest value that satisfies a
condition.
Key Features
Can express all computable functions.
May run forever (not always guaranteed to stop).
Built using:
o Basic functions
o Composition
o Primitive recursion
o Minimization (μ-operator)
Examples of μ-Recursive Functions
1. Find smallest x such that x = 3
μx [x − 3 = 0]
Tries 0, 1, 2, 3 → stops at 3.
2. Find smallest x such that x + 2 = 5
μx [x + 2 − 5 = 0]
Checks 0,1,2,3 → stops at 3.
Why All Computable Functions Are μ-Recursive
1. Computable functions are those that can be solved by some step-by-step method
(algorithm).
2. μ-recursive functions are made using simple building blocks:
o Basic functions (like zero, adding 1)
o Combining functions (composition)
o Step-by-step definitions (primitive recursion)
o Searching for answers (μ-operator)
3. Some functions need searching (like loops) to find the answer.
4. The μ-operator helps search for answers.
5. So, all computable functions can be written as μ-recursive
functions.
Define: Bounded Minimalization and show that, if P is a
minimalization 𝑚𝑃 is a primitive recursive function.(S-23)
primitive recursive (𝑛 + 1) place predicate, its bounded
Bounded Minimization – Definition
Bounded Minimization means finding the smallest value of y such that a predicate P(x₁,
x₂, ..., xₙ, y) is true, within a fixed limit (y ≤ z).
It is written as:
μy ≤ z. P(x₁, x₂, ..., xₙ, y)
Here, μ denotes the smallest y for which the predicate holds true within the bound z.
Proof: If P is a Primitive Recursive (n+1)-place Predicate,
then its Bounded Minimization mP is a Primitive Recursive
Function
Step-by-step:
1. Assume P(x₁, x₂, ..., xₙ, y) is a primitive recursive predicate.
2. Define the bounded minimization function:
mP(x₁, ..., xₙ, z) = smallest y ≤ z such that P(x₁, ..., xₙ, y) is true
3. Since P is primitive recursive, we can check each y from 0 to z using a primitive
recursive process.
4. Build a function that:
o Scans y = 0 to z
o Returns the first y that satisfies P
o If no such y is found, return z + 1 (as a default value)
5. The entire search is bounded and uses finite steps only.
6. Therefore, the search function is also primitive recursive because:
o It uses simple loops
o It stays within the given limit z
Define and explain Bounded Quantification.(S-24)
Bounded Quantification – Definition & Explanation
Bounded Quantification means putting a limit (bound) on the types or values a variable can
take in a quantified statement (like "for all" or "there exists").
Pointwise Explanation:
o "For all" (written as ∀)
1. Quantification means using words like:
o "There exists" (written as ∃)
2. In bounded quantification, we restrict the variable to a certain set or type.
o ∀x ≤ 10, P(x) → Means "for all x less than or equal to 10,
3. It is written like this:
o ∀x ∈ Integer, P(x) → Means "for all x in integers, P(x) is
P(x) is true."
true."
4. In programming, bounded quantification is used in generic types:
o Example in Java:
o <T extends Number>
Means T can be any subtype of Number (like Integer, Float,
etc
Example 1 (∀ - For all):
∀x ∈ Σ*, |x| ≤ 3 ⇒ M accepts x
→ For all strings of length ≤ 3, machine M accepts x.
Example 2 (∃ - There exists):
∃x ∈ Σ*, |x| ≤ 5 ∧ M accepts x
→ There exists a string of length ≤ 5 that M accepts.
