Chapter 6
Computability
Recursive Functions
• In automata theory, recursive functions come from computability theory and
are used to formally describe what can be computed by machines such as finite
automata, pushdown automata, and Turing machines.
• A recursive function is a function from natural numbers to natural numbers
that can be computed using a finite set of rules.
• Formally, recursive functions are built from basic functions using construction
rules.
Initial Functions in Recursive Function
To start the discussion on Recursive functions, we will see the initial functions. These are the
foundational functions in recursive function theory, and there are three of them
• Zero function
• Successor function
• Projection function
Zero Function
• The first initial function is the zero function, which we represent with the letter Z. The zero function is simple: It always
returns zero, regardless of the input value. If any variable is given, the result will always be zero.
• For instance, if we represent the zero function as Z(x), then Z(5) = 0 and Z(70) = 0. This function sets the value of any
variable to zero, making it a basic part of recursive function theory.
Z(x)=0
Con..
• looks trivial on the surface, but conceptually it is very deep and
foundational in automata theory and computability.
The zero function represents the constant function.
•Zero function = constant base
•It does not depend on input
•Foundation of recursion
•It maps every natural number to the same value
•Ensures termination
Formally:
•Defines “nothingness” in computation
∀x∈N, Z(x)=0
This shows an important idea: •Lower bound of all computable functions
Computation does not require using the input. •Makes complex computation possible
A function can be valid even if it ignores all information provided to it.
Con..
Successor Function
• The next type of function is the successor function, this is represented by
the letter S. This function gives the next value of any variable by adding 1
to it.
• For example, if you want to find the successor of 6, you simply
calculate S(6) = 6 + 1 = 7. Similarly, S(70) = 70 + 1 = 71. The successor
function is straightforward but important in defining other functions.
S(x)=x+1
Con..
The successor function represents the idea of “next”.
It is the smallest possible change in computation.
•No decisions
•Just progress
Successor = the engine of growth in computation
Without it:
•You can never move beyond zero
•No counting
•No iteration
•No time steps
The successor function is a basic recursive function that generates all natural
numbers from zero. It models incremental computation and forms the basis of
iteration and counting.
Con..
Projection Function
• The third initial function is the projection function. This function is used to select a
particular value from a set of natural numbers. If you have a set of numbers and we
want to get a specific one, we use the projection function.
The projection function is represented as pin , where n is the total number of values, and i
is the position of the value you want to select.
For example −
•p42 selects the first number from the set {3, 7, 8, 9}, giving an output of 3.
•p32 selects the second number from the set {7, 9, 12}, giving an output of 9.
• p64selects the fourth number from the set {1, 2, 3, 4, 5, 6}, giving an output of 4.
Composite Functions in Recursive Function Theory
▪ After understanding the initial functions, the next concept is composite functions. In a composite function, we combine two or more
functions by substituting one function into another. This allows us to create more complex functions from simpler ones.
A composite function is defined when one function is substituted into another. For example, let us consider two functions −
f(x)=3x+2
g(x)=x+5
If we want to compose these functions as f(g(x)), we substitute g(x) into f(x). So,
f(g(x))=3(x+5)+2=3x+17
We can also reverse the composition and create g(f(x)), which means substituting f(x) into g(x). So,
g(f(x))=(3x+2)+5=3x+7
▪ In recursive function theory, composite functions allow us to build complex operations by combining simpler ones, extending the
range of possible computations.
Recursive Functions
• Recursive Function is a function that repeats or uses previous term to calculate subsequent terms. This forms a
sequence of terms. Usually, we get this function based on the arithmetic-geometric sequence, which has terms with a
common difference between them.
• Recursive functions are useful because they allow us to define operations that can continue indefinitely or until a
specific condition is met.
Primitive Recursive Functions
• A primitive recursive function is a special type of recursive function. It is defined as a function that can be obtained
from initial functions through a finite number of composition and recursive steps.
• In other words, a primitive recursive function is created by applying composition and recursion to the initial
functions. The zero, successor, and projection functions. This type of function is useful in computation theory because
it is both predictable and well-defined within a finite number of steps.
Con..
Examples of Primitive Recursive Functions
In this section, let's take a look at some basic examples of primitive recursive functions.
Zero Function
The zero function Z(x) = 0 for all x N (where N is the set of natural numbers) is a basic
primitive recursive function. It essentially erases its input and returns zero.
Example
A Turing machine can be designed to simulate this function by moving through the input
and replacing every symbol with zero.
Con…
Partial Recursive Functions
Then the next type of function is partial recursive functions. A function is said to be partial recursive
if it is defined only for some of its arguments, not all.
For example, consider the subtraction of two positive numbers M and N −
f(M,N)=M−N
This function is defined only when M ≥ N. If M is less than N, the result would be negative, and the function would not be
defined. Therefore, this function is a partial recursive function because it does not cover all possible inputs.
Total Recursive Functions
The next type is total recursive functions. A total recursive function is defined for all possible arguments. For example,
addition −
f(M,N)=M+N
This function is defined for any positive numbers M and N, and the result is always positive. Therefore, it is a total recursive
function because it covers all input possibilities.
Con…
Partial Recursive Functions
Then the next type of function is partial recursive functions. A function is said to be partial recursive
if it is defined only for some of its arguments, not all.
For example, consider the subtraction of two positive numbers M and N −
f(M,N)=M−N
This function is defined only when M ≥ N. If M is less than N, the result would be negative, and the function would not be
defined. Therefore, this function is a partial recursive function because it does not cover all possible inputs.
Total Recursive Functions
The next type is total recursive functions. A total recursive function is defined for all possible arguments. For example,
addition −
f(M,N)=M+N
This function is defined for any positive numbers M and N, and the result is always positive. Therefore, it is a total recursive
function because it covers all input possibilities.
Recursive Languages (Decidable Languages)
A recursive language (also called a decidable language) is a language for which there exists a
Turing Machine (TM) that:
•Accepts every string in the language, and
•Rejects every string not in the language,
•Always halts on every input.
Recursive language = TM halts on all inputs
Example 1: Regular Languages Example 2: Context-Free Languages
All regular languages are recursive. All CFLs are recursive.
Example: Example:
L={w∣w has even number of 0s} L={anbn∣n≥0}
A DFA: A PDA:
•Always halts •Always halts
•Accepts or rejects every string •Membership is decidable
Recursively Enumerable Language (RE)
(also called Turing-recognizable or semi-decidable languages)
A language L⊆Σ is recursively enumerable (RE)
if there exists a Turing Machine (TM) such that:
If w∈L→ the TM accepts www (and halts)
If w∉L→ the TM may reject or loop forever
👉 Halting is guaranteed only for accepted strings.
Con..
Feature Recursive Language (Decidable) Recursively Enumerable Language (RE)
Definition TM halts on all inputs TM halts only on accepted inputs
Decision Always gives Yes / No Gives Yes or may loop forever
Halting Guaranteed for every string Guaranteed only for members
Rejection Explicitly rejects non-members May not reject non-members
Computation type Complete decision procedure Recognition procedure
Also called Decidable language Turing-recognizable / Semi-decidable
Complement closure ✅ Closed ❌ Not closed
Relationship Proper subset of RE Proper superset of Recursive
Examples Regular languages, CFLs Halting problem
Power Less powerful More expressive