Decidability
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@gmail.com
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Thursday 13th November, 2025

kr chowdhary

TOC

1/ 10

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Decision Problems

We may be interested in following
questions:
“Is a number number perfect
square?”
“Is number prime?”
“Does a graph has cycle?”
“Does the computation of TM
halt before 25th transition?”
Each of these general question
describe a decision problem. A
decision problem PP is a set of
related questions pi , each of which
has es/no answer. For example:

kr chowdhary

p0 : Is 0 a perfect square?
p1 Is 1 a perfect square?
p2 is 2 a perfect square?
...
Each of the pi is an instance of the
problem P. The solution of a
decision problem P is an algorithm
that determines the answer of every
question p ∈ P. A decision problem
is decidable, if it has a solution.

TOC

2/ 10

Decision Problems

An algorithm that solves decision
problem should be:
Complete: correct answer is
given for every problem
instance
Mechanistic: finite sequence
of instructions, each can be
carried out without
requirement of insight,
ingenuity, or guesswork.

kr chowdhary

Deterministic: With identical
input, the same computation
is carried.
A procedure having the properties
of complete, Mechanistic, and
deterministic, is called effective
procedure. A standard TM is an
effective algorithm if it is,
Mechanistic, deterministic, and
complete. However, it is complete
only if, it halts on every input.

TOC

3/ 10

Decidable languages
Decidable language-3
AEQDFA = {⟨A, B⟩| A and B are DFAs and L(A) = L(B) }
Equivalence problem: Test whether two DFAs recognize the same
language.
Theorem: AEQDFA is decidable languages
F = “On input ⟨A, B⟩, where A and B are DFAs:
1

2
3

construct DFA L(C ) = (L(A) ∩ L(B)) ∪ (L(B) ∩ L(A))
(A = B ⇒ C = φ )
Run TM T for deciding AEQDFA on input ⟨C ⟩
if T accepts, Accept; otherwise reject. ”

Acceptance problem:ATM
Input: A TM’s description ⟨M⟩ and a string w for input to M.
Output: Yes/No indicating if M eventually enters qaccept on input w.
Acceptance of language consisting of tuples: ⟨M, w ⟩,
ATM = {⟨M, w ⟩|M is a Turing description and M accepts input w }.
Is ATM Turing recognizable?
Defn. Turing Recognizable: A language ATM is “Turing
recognizable”if there exists a TM M such that for all w:
- If ⟨M, w ⟩ ∈ ATM then M eventually enter qaccept
- If ⟨M, w ⟩ ∈
/ ATM then M eventually enter qregect or M loops for ever.
kr chowdhary

TOC

4/ 10

Halting Problem
Theorem: ATM is Turing recognizable.
U = “On input ⟨M, w ⟩, where M is a TM and w is a string:
Simulate M on input w
If M ever enters accepts state, then U accepts; if M enters its reject
state, U rejects”
- U is universal TM
- U keeps looping if M neither accepts or rejects
- However, if U ≡ M, ATM is unsolvable (i.e.,undecidable)

1
2

A problem is decidable if some TM decides (solves) it.
Halting problem: Given a TM M and input string ⟨W , ⟨m⟩⟩, decide
whether M halt on ⟨⟨M⟩, w ⟩?
The instance of the problem is : en (M)en (w ). Halting =
{en (M)e(w )|M halts on w } is not recursive.

kr chowdhary

TOC

5/ 10

Undecidability of ATM
Proof by contradiction:
Assume that ∃ some TM H that decides ATM . That is, H accepts if
M accepts w, and H rejects if M rejects w.
Now we construct a TM D with H as subroutine. This calls H and
determine what M does when the input to M is its own description
< M >. However, after determining this, it outputs the opposite.
That is, it rejects if M accepts, and vice-versa. Call this as H ′ .
Define D(< M >) =
1 Construct a TM D (having input < M >) that outputs the opposite
of the result of simulating H on input ⟨⟨M⟩, M⟩.
2 Output the opposite of what H outputs, i.e., if H accepts, then
reject, and if H rejects, then accept.
The above can be rewritten as:
If M accepts its own description < M >, then
H(< M >) accepts and ∴ D(< M >) rejects
If M rejects its own description < M >, then
H(< M >) rejects and ∴ D(< M >) accepts
What happens if we run D on its own description < D >?
From above: (substitute D for M), we have (see next slide)
kr chowdhary

TOC

6/ 10

Proving Undecidability of ATM
If D accepts < D >:
H(D, < D >) accepts and D < D > rejects
If D rejects < D >:
H(D, < D >) rejects and D < D > accepts
Which can be further simplified:
If D accepts < D >:
D < D > rejects
If D rejects < D >:
D < D > accepts
Hence, whatever is done, it must do the opposite. So there is a
contradiction. So, D cannot exist. But, if H exists, we know how to
make D. H cannot exist; so there is no TM that decides ATM .

kr chowdhary

TOC

7/ 10

Proving Undecidability of ATM

kr chowdhary

TOC

8/ 10

A different approach for ATM as undecidable
Preceding proof uses self-reference and diagonalization.
To obtain table for diagonalization argument, consider that every
v ∈ {0, 1}∗ represent a TM. If v does not have form R(M), a
one-state TM with no transition is assigned to v. Thus, TMs can be
listed as M0 , M1 , M2 , M3 , M4 , M5 , M6 , M7 , . . . corresponding to
ε, 0, 1, 00, 01, 10, 11, 000.
Consider a table that lists TMs along the horizontal and vertical
axes. The i, jth entry in table is:


1
0

if Mi halts when run with input R(Mj )
if Mi does not halt when run with input R(Mj )

Diagonal elements are answers to the self-referential questions: Does Mi
halt when run with itself?
Undecidable, decidable, recognizable, Unrecognizable:
ACFG is decidable
ATM is undecidable
L ∈ P(Γ∗ ) is unrecognizable, where P(Γ∗ ) is uncountable
¯ = {w | M is a TM and M does not accept w}
ATM
kr chowdhary

TOC

9/ 10

Bibliography

Chowdhary, K.R. (2025). Decidability, Undecidability, and
Unsolvability. In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_12

kr chowdhary

TOC

10/ 10

