Chapter SIX
COMPUTABILITY (10hr)
Mr. Getasew Nibretu
Outline
6.1. Recursive Function
Primitive Recursive Functions and Computability
Ackerman’s Function
6.2. Recursive Languages and
Recursively Enumerable Languages
Objectives
By the end of this chapter, students will be able to:
Define primitive recursive functions
Construct functions using composition and primitive recursion
Explain why the Wilhelm Ackermann function is computable but
not primitive recursive
Differentiate between Recursive (REC) and Recursively
Enumerable (RE) languages
Analyze closure properties of REC and RE languages
Solve GATE-style problems on computability theory
Introduction
Is the following a function? Why or why not?
f(x) = ±√x
A function is a rule that associates domain with ranges (Codomain).
For example: f(n) = n² + 1, This function is defined as “given any value for the argument
n, multiply that value by itself and add 1”.
To complete the definition of the function “f”, we must specify its domain.
For example: we take the domain to be the set of all integers, then the range of “f” will
be some subset of positive integers.
6.1. RECURSIVE FUNCTION
What is primitive recursive functions?
A PRF is a function that can be computed by a computer
program/Turing Machine.
A PRF takes a fixed number of arguments, each a natural number
(non-negative integers: 0,1,2,3,…), and returns a natural number.
PRFs can be defined in terms of basic, composition, and primitive
recursion.
PRFs also known as computable functions.
6.1. RECURSIVE FUNCTION
Can we build addition using only successor?
Basic PRFs: There are 3 basic primitive recursive functions.
These are:
1) Zero Function: know as constant function.
A function f(x1,x2,x3,…xi) is PRF, if either:
“f” is the function that is always 0,
i.e., f(x1, … , xn) = 0.
6.1. RECURSIVE FUNCTION
2) Successor: Successor is a total function (i.e., returns an
output for every single possible input.)
f is the successor function, i.e., f(x1, … , xn) = xi + 1;
6.1. RECURSIVE FUNCTION
3) Projection: 𝑃 )X1,X2,X3,…,Xn) = 𝑋 .
f is the projection function, i.e., f(x1, …. , xn) = xi; This is
denoted by πᵢ when the number of arguments is understood.
This rule for deriving a primitive recursive function is called the
Projection rule.
6.1. RECURSIVE FUNCTION
4) Composition:
“f” is defined by the composition of primitive recursive
functions,
i.e., if g1(x1, … ,xn), g2(x1, … ,xn), … , gk(x1, … , xn)
are primitive recursive and h(x1, … , xk)
is primitive recursive,
then f(x1, ... ,xn) = h(g1(x1, ... , xn), ... , gk(x1, .... , xn)),
is primitive recursive.
6.1. RECURSIVE FUNCTION
5) Primitive Recursion
f is defined by recursion of two primitive recursive functions,
i.e., if
g(x1, … ,xn-1) and h(x1, … ,xn+1) are primitive recursive then
the following function is also primitive recursive.
f(x1, …, xn-1, 0) = g(x1, … , xn-1)
f(x1, … , xn-1, m + 1) = h(x1, … , xn-1, m, f(x1, … , xn-
1, m))
6.1. RECURSIVE FUNCTION
Question:
1) Can you describe how the functions, f(x) = x+5 can be written as a primitive recursion
function?
i. S(x) = x+1, is primitive recursive by the successor rule.
ii. S(S(x)), is composite recursive by the composition rule.
iii.S(S(S(x))) is primitive recursive by the composition rule.
iv.S(S(S(S(x)))) is primitive recursive by the composition rule.
v. S(S(S(S(S(x))))) is primitive recursive by the composition rule.
f(x) = S(S(S(S(S(x))))) is primitive recursive by successor and several applications of
composition.
6.1. RECURSIVE FUNCTION
2) Can you describe how the functions, f(x, y, z) = y+2 can be written as a
primitive recursion function?
i. π (x, y, z) = y, is primitive recursive by the projection rule.
ii. S(π (x, y, z)), is composite recursive by the composition rule.
iii. S(S(π (x, y, z))), is primitive recursive by the composition rule.
f(x) = S(S(π (x, y, z))) is primitive recursive by successor and several
applications of composition.
6.1. RECURSIVE FUNCTION
Summary
Any function that can be written as a combination of the basic
functions (π, S and Z), composition and primitive recursion is a
primitive recursive function, which can be computable also.
6.1. RECURSIVE FUNCTION
Ackermann Function
Function f(3,3)
Addition ?
Multiplication ?
Exponential ?
Ackermann ?
Which grows fastest?
6.1. RECURSIVE FUNCTION
Ackermann's function:
The only Non-Primitive Recursive but Computable
Function.
In computability theory, the Ackermann function, named
after Wilhelm Ackermann, is one of the simplest and
earliest-discovered examples of a total computable function
that is not primitive recursive.
6.1. RECURSIVE FUNCTION
Remember:
All primitive recursive functions are total and
computable, but the Ackermann function illustrates
that not all total computable functions are primitive
recursive.
It’s a function with two arguments each of which can
be assigned any non-negative integer.
6.1. RECURSIVE FUNCTION
Definition: Ackermann function
6.1. RECURSIVE FUNCTION
Definition: Ackermann function
6.1. RECURSIVE FUNCTION
Definition: Ackermann function
6.1. RECURSIVE FUNCTION
Activity:
Define Addition, Multiplication, Exponentiation, and Factorial Using only:
Zero function 𝑍 𝑥 = 0
Successor function 𝑆 𝑥 = 𝑥 + 1
Projection function 𝜋
Composition
Primitive recursion
Hint:
Addition → using Successor
Multiplication → using Addition
Exponentiation → using Multiplication
Factorial → using Multiplication
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
What is Recursive Languages?
A language L is REC if there exists a Turing Machine (TM) that:
Accepts and halts for strings in L
Rejects and halts for strings not in L
Knowns Turing Decidability.
What is Recursively Enumerable Languages?
A language L is RE if there exists a Turing Machine (TM) that:
Accepts and halts for strings in L
May loop forever for strings not in L
RE languages are also called Turing-recognizable languages.
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
Chomsky Hierarchy of Formal Languages Diagram
Regular ⊂ CFL ⊂ CSL ⊂ RE
Which class corresponds to:
Type 0 → ?
Type 1 → ?
Type 2 → ?
Type 3 → ?
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
Comparisons of RE and REC
Properties RE REC
Halts on Accept Yes Yes
Alway
Halts on Reject Not Always
s
Closed Under Complement
Closed Under Others
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
1) Is L1 = {aⁿbⁿcⁿ} recursive?
A) RE only
B) Recursive
C) CFL
D) Regular
2) L2 = {w∈{a,b,c}∗∣#a(w)=#b(w)=#c(w)} recursive?
3) Is L1 and L2 are REL?
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
Classic Examples of REC Languages
6.2. RECURSIVE LANGUAGES AND
RECURSIVELY ENUMERABLE LANGUAGE
Classic Examples of RE Languages
HALT
ATM
PCP
Thank you!!