Computability
Module 5
Amity School of Engineering and Technology
Amity University Uttar Pradesh, Noida
March 14, 2026
Outline
1 Turing Machine Halting Problem
2 Undecidable Problems for Recursive enumerable language
3 Post Correspondence Problem
4 Modified Post Correspondence Problem
5 Undecidable Problem for CFL
6 Partial and Total Functions
7 Primitive Recursive functions
8 Recursive functions
Computability March 14, 2026 2/26
Turing Machine Halting Problem
Some basic definition
When a Turing machine reaches a final state, it halts.
We can also say that a Turing machine M halts when M
reaches a state q and a current symbol a to be scanned so
that δ(q, a) is undefined.
There are TMs that never halt on some inputs in any one of
these ways.
So we make a distinction between the languages accepted by
a TM that halts on all input strings and a TM that never
halts on some input strings.
Recursively Enumerable: A language L ⊆ Σ∗ is recursively
enumerable if there exists a TM M, such that L = T (M).
Recursive: A language L ⊆ Σ∗ is recursive if there exists some
TM M that satisfies the following two conditions:
1 If w ∈ L then M accepts w , that is. reaches an accepting state on
processing w and halts.
Computability March 14, 2026 3/26
Turing Machine Halting Problem
Some basic definition
2 If w ∈
/ L then M eventually halts, without reaching an accepting
state.
Decidable:A problem with two answers (Yes/No) is decidable
if the corresponding language is recursive. In this case, the
language L is also called decidable.
Undecidable:A problem/language is undecidable if it is not
decidable.
A decidable problem is called a solvable problem and an
undecidable problem an unsolvable problem by some authors.
ADFA = {(B, w )|B accepts the input string w }
ACFG = {(G , w )| The context-free grammar G accepts the
input string w }
ACSG = {(G , w )| The context-sensitive grammar G accepts
the input string w }
Computability March 14, 2026 4/26
Turing Machine Halting Problem
Some basic definition
ATM = {(M, w )| The TM M accepts w }
ADFA is decidable.
ACFG is decidable.
ACSG is decidable.
ATM is undecidable.
Computability March 14, 2026 5/26
Turing Machine Halting Problem
Turing machine halting Problem
The reduction technique is used to prove the undecidability of
halting problem of Turing machine
We say that problem A is reducible to problem B if a solution
to problem B can be used to solve problem A.
If A is reducible to B and B is decidable then A is decidable.
If A is reducible to B and A is undecidable, then B is
undecidable.
Theorem HALTTM = {(M, w )| The Turing machine M halts
on input w } is undecidable.
Proof: We assume that HALTTM is decidable, and get a
contradiction. Let M1 be the TM such that
T (M1 ) = HALTTM and let M1 halt eventually on all (M, w ).
We construct a TM M2 as follows:
1 For M2 , (M, w ) is an input.
2 The TM M1 acts on (M, w ).
Computability March 14, 2026 6/26
Turing Machine Halting Problem
Turing machine halting Problem
3 If M1 rejects (M, w ) then M2 rejects (M, w ).
4 If M1 accepts (M, w ), simulate the TM M on the input string w
until M halts.
5 If M has accepted w , M2 accepts (M, w ); otherwise M2 rejects
(M, w ).
When M1 accepts (M, w ) (in step 4), the Turing machine M
halts on w .
In this case either an accepting state q or a state q ′ such that
δ(q ′ , a) is undefined till some symbol a in w is reached.
In the first case (the first alternative of step 5) M2 accepts
(M.w ).
In the second case (the second alternative of step 5) M2
rejects (M, w ).
It follows from the definition of M2 that M2 halts eventually.
TM2 = {(M, w )| The Turing machine accepts w } = ATM
This is a contradiction since ATM is undecidable.
Computability March 14, 2026 7/26
language
Decidability and Undecidability
Recursive Language
A language L is said to be recursive if there exists a turing
machine which will accept all strings in L and reject all strings
not in L.
The turing machine will halt everytime and give answer
(accepted or rejected) for each and every string input.
Computability March 14, 2026 8/26
language
Decidability and Undecidability
Recursive Language
A language L is said to be recursive if there exists a turing
machine which will accept all strings in L and reject all strings
not in L.
The turing machine will halt everytime and give answer
(accepted or rejected) for each and every string input.
Recursive Enumerable Language
A language L is said to be recursively enumerable language if
there exists a turing machine which will accept (and halt) for
all input strings which are in L.
May or may not halt for all input strings which are not in L.
Computability March 14, 2026 8/26
language
Decidability and Undecidability
Decidable Language
A language L is decidable if it is recursive language. All
decidable languages are recursive language and vice-verse.
Computability March 14, 2026 9/26
language
Decidability and Undecidability
Decidable Language
A language L is decidable if it is recursive language. All
decidable languages are recursive language and vice-verse.
Partially Decidable Language
A language L is partially decidable if L is a recursively
enumerable language.
Computability March 14, 2026 9/26
language
Decidability and Undecidability
Decidable Language
A language L is decidable if it is recursive language. All
decidable languages are recursive language and vice-verse.
Partially Decidable Language
A language L is partially decidable if L is a recursively
enumerable language.
Undecidable Language
A language L is undecidable if it is not decidable.
An undecidable language may sometimes be partially
decidable but not decidable.
If a language is not even partially decidable, then there exists
no turing machine for that language.
Computability March 14, 2026 9/26
Post Correspondence Problem
Post Correspondence Problem
Post Correspondence Problem is a popular undecidable
problem that was introduced by Emil Leon Post in 1946.
It is simpler than Halting Problem
In this problem we have N number of Dominos (tiles). The
aim is to arrange tiles in such order that string made by
Numerators is same as string made by Denominators.
In simple words, lets assume we have two lists both containing
N words, aim is to find out concatenation of these words in
some sequence such that both lists yield same result.
Computability March 14, 2026 10/26
Post Correspondence Problem
Post Correspondence Problem
Post Correspondence Problem is a popular undecidable
problem that was introduced by Emil Leon Post in 1946.
It is simpler than Halting Problem
In this problem we have N number of Dominos (tiles). The
aim is to arrange tiles in such order that string made by
Numerators is same as string made by Denominators.
In simple words, lets assume we have two lists both containing
N words, aim is to find out concatenation of these words in
some sequence such that both lists yield same result.
Let we have two lists A=[aa, bb, abb] and B=[aab, ba, b]
Computability March 14, 2026 10/26
Post Correspondence Problem
Post Correspondence Problem
Post Correspondence Problem is a popular undecidable
problem that was introduced by Emil Leon Post in 1946.
It is simpler than Halting Problem
In this problem we have N number of Dominos (tiles). The
aim is to arrange tiles in such order that string made by
Numerators is same as string made by Denominators.
In simple words, lets assume we have two lists both containing
N words, aim is to find out concatenation of these words in
some sequence such that both lists yield same result.
Let we have two lists A=[aa, bb, abb] and B=[aab, ba, b]
Now for sequence 1, 2, 1, 3 first list will yield aabbaaabb and
second list will yield same string aabbaaabb. So the solution
to this PCP becomes 1, 2, 1, 3.
Computability March 14, 2026 10/26
Post Correspondence Problem
Post Correspondence Problem
Post Correspondence Problems can be represented in two ways:
Domino’s Form
Table Form
Computability March 14, 2026 11/26
Modified Post Correspondence Problem
Modified PCP
If the first substring used in PCP is always x1 and y1 then the
PCP is known as the Modified Post Correspondence Problem.
MPCP = [D] — D is instance of PCP starts with first domino
Computability March 14, 2026 12/26
Partial and Total Functions
Partial and Total Functions
A Partial Function f from X to Y (f : X → Y ) is a rule which
assigns to every element of X at most one element of Y .
Example: if R denotes the set of all real numbers, the rule f
√
from R to R given by f (r ) = + r ; is a partial function since
f (r ) is not defined as a real number when r is negative.
A Total Function f from X to Y is a rule which assigns to
every element of X a unique element of Y .
Example:The rule f from R to R given by f (r ) = |r | is a total
function since f (r ) is defined for every real number r .
We consider total functions f from X k to X , where
X = {0, 1, 2, 3, . . . } or X = {a, b}∗ .
We denote {0, 1, 2, . . . } by N and {a, b} by Σ.
X k is the set of all k-tuples of elements of X .
Computability March 14, 2026 13/26
Partial and Total Functions
Partial and Total Functions
For example, f (m, n) = m − n defines a partial function from
N to itself as f (m, n) is not defined when m − n < 0.
But g (m, n) = m + n defines a total function from N to itself.
A partial or total function f from X k to X is also called a
function of k variables and denoted by f (x1 , X2 , . . . , Xk ).
For example, f (x1 , x2 ) = 2x1 + x2 is a function of two
variables: f (1, 2) = 4; 1 and 2 are called arguments and 4 is
called a value.
g (w1 , w2 ) = w1 w2 is a function of two variables
w1 , w2 ∈ Σ∗ : g (ab, aa) = abaa, ab, aa are called arguments
and abaa is a value.
Computability March 14, 2026 14/26
Primitive Recursive functions
Primitive Recursive functions
The initial functions over N are given as:
1 Zero function Z defined by Z (x) = 0
2 Successor function S defined by S(x) = x + 1
3 Projection function Uin defined by Uin (x1 , . . . , xn ) = xi
4 As U11 (x) = x for every x in N. U11 is simply the identity function.
So Uin is also termed a generalized identity function.
The initial functions over Σ are given as:
1 nil(x) defined by nil(x) = ∧
2 cons a(x) defined by cons a(x) = ax
3 cons b(x) defined by cons b(x) = bx
Computability March 14, 2026 15/26
Primitive Recursive functions
Primitive Recursive functions
Example:
Z (7) = 0
S(4) = 5
U23 {2, 5, 7} = 5
nil(aabb) = ∧
cons a(aabb) = aaabb
cons b(aabb) = baabb
Computability March 14, 2026 16/26
Primitive Recursive functions
Primitive Recursive functions
Composition of a function: If f1 , f2 , . . . , fk are partial functions
of n variables and g is a partial function of k variables, then
the composition of g with f1 , f2 , . . . , fk is a partial function of
n variables defined by
g (f1 (x1 , x2 , . . . , xn ), f2 (x1 , x2 , . . . , xn ), . . . , fk (x1 , x2 , . . . , xn ))
The composition of g with f1 , f2 , . . . , fn is total when
g , f1 , f2 , . . . , fn are total.
Example: Let f1 (x, y ) = x + y , f2 (x, y ) = 2x, f3 (x, y ) = xy
and g (x, y , z) = x + y + z be functions over N. Find the
composition of g with f1 , f2 , f3
Solution: The composition of g with f1 , f2 , f3 is given by
h(x, y ) = g (f1 (x, y ), f2 (x, y ), f3 (x, y )) = (x + y ) + (2x) + (xy )
= x + y + 2x + xy
Computability March 14, 2026 17/26
Primitive Recursive functions
Primitive Recursive functions
A function f (x) over N is defined by recursion if there exists a
constant k (a natural number) and a function h(x, y ) such
that f (0) = k, f (n + 1) = h(n, f (n)
Example: Define n! by recursion.
Solution: Let f (0) = 1 and f (n + 1) = h(n, f (n)), where
h(x, y ) = S(x) ∗ y .
So f (n) will be
f (n) = h(n − 1, f (n − 1)) = S(n − 1) ∗ f (n − 1) = n ∗ f (n − 1)
A function f of n + 1 variables is defined by recursion if there
exists a function g of n variables, and a function h of n + 2
variables, and f is defined as follows:
f (x1 , x2 , . . . , xn , 0) = g (x1 , x2 , . . . , xn )
f (x1 , x2 , . . . , xn , y + 1) =
h(x1 , x2 , . . . , xn , y , f (x1 , x2 , . . . , xn , y ))
Computability March 14, 2026 18/26
Primitive Recursive functions
Primitive Recursive functions
A total function f over N is called primitive recursive
(i) if it is anyone of the three initial functions, or
(ii) if it can be obtained by applying composition and recursion
a finite number of times to the set of initial functions.
A total function is primitive recursive if it can be obtained by
applying composition and recursion a finite number of times
to primitive recursive functions f1 , f2 , . . . , fm . Each fi is
obtained by applying composition and recursion a finite
number of times to initial functions.
Computability March 14, 2026 19/26
Primitive Recursive functions
Primitive Recursive functions
A function f (x) over Σ is defined by recursion if there exists a
’constant’ string w ∈ Σ∗ and functions h1 (x, y ) and h2 (x.y )
such that
f (∧) = w
f (ax) = h1 (x, f (x))
f (bx) = h2 (x, f (x))
h1 and h2 may be functions in one variable.
Computability March 14, 2026 20/26
Primitive Recursive functions
Primitive Recursive functions
A function f (x1 , x2 , . . . , xn ) over Σ is defined by recursion if
there exists a function g (x1 , x2 , . . . , xn−1 ),
h1 (x1 , x2 , . . . , xn+1 ), h2 (x1 , x2 , . . . , xn+1 ) such that
f (∧, x2 , . . . , xn ) = g (x2 , . . . , xn )
f (ax1 , x2 , . . . , xn ) = h1 (x1 , x2 , . . . , xn , f (x1 , x2 , . . . , xn ))
f (bx1 , x2 , . . . , xn ) = h2 (x1 , x2 , . . . , xn , f (x1 , x2 , . . . , xn ))
h1 and h2 may be functions of m variables, where m < n + 1.
A total function f over Σ is primitive recursive
(i) if it is anyone of the three initial functions, or
(ii) if it can be obtained by applying composition and
recursion a finite number of times to the initial functions.
Computability March 14, 2026 21/26
Recursive functions
Recursive functions
Let g (x1 , x2 , . . . , xn , y ) be a total function over N. The
function g is a regular function if there exists some natural
number y0 such that g (x1 , x2 , . . . , xn , y0 ) = 0 for all values
x1 , x2 , . . . , xn ∈ N.
Example: g (x, y ) = min(x, y ) is a regular function since
g (x, 0) = 0 for all x ∈ N.
But f (x, y ) = |x − y | is not regular since f (x, y ) = 0 only
when x = y , and so we cannot find a fixed y such that
f (x, y ) = 0 for all x in N.
Computability March 14, 2026 22/26
Recursive functions
Recursive functions
A function f (x1 , x2 , . . . , xn ) over N is defined from a total
function g (x1 , x2 , . . . , xn , y ) by minimization if
(a) f (x1 , x2 , . . . , xn ) is the least value of all y ’s such that
g (x1 , x2 , . . . , xn , y ) = 0 if it exists. The least value is denoted
by µy (g (x1 , x2 , . . . , xn , y ) = 0).
(b) f (x1 , x2 , . . . , xn ) is undefined if there is no y such that
g (x1 , x2 , . . . , xn , y ) = 0
In general, f is partial. But, if g is regular then f is total.
A function is recursive if it can be obtained from the initial
functions by a finite number of applications of composition,
recursion and minimization over regular functions.
A function is partial recursive if it can be obtained from the
initial functions by a finite number of applications of
composition, recursion and minimization.
Computability March 14, 2026 23/26
Recursive functions
Recursive functions
Example: Show that f (x) = x/2 is a partial recursive function
over N.
Solution: Let g (x, y ) = |2y − x| where 2y − x = 0 for some y
only when x is even. Let f1 (x) = µy (|2y − x| = 0). Then
f1 (x) is defined only for even values of x and is equal to x/2.
When x is odd, f1 (x) is not defined f1 (x) is partial recursive.
As f (x) = x/2 = f1 (x) is a partial recursive function.
Exercise: Show that f (x, y ) = x 2 y 4 + 7xy 3 + 4y 5 is primitive
recursive.
Computability March 14, 2026 24/26
Questions?
Thank you.