Rice’s Theorem
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Thursday 13th November, 2025

kr chowdhary

TOC

1/ 17

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

Reductions re-visited
Formally, reduction from P to Q is a TM that takes as instance of P on
its tape and halts with an instance of Q written on its tape.

Theorem
If there is a reduction from P to Q, then (1) if P is undecidable then so
Q, (2) if P is non-R.E, the so is Q.

Proof.
(1) Suppose P is undecidable. If it is possible to decide Q,then we can
combine the reduction from P to Q with the algorithm that decides Q to
construct an algorithm that decides P. If given an instance p1 of P,
apply algorithm to convert it to an instance r (p1 ) (r is reduction TM) of
Q, then apply the algorithm that decides Q to decide r (p1 ). If that
algorithm says “yes”, then P is decidable. The sequential execution of
reducer TM and algorithm (i.e., TM) Q, solves P. (2) can be proved in
same lines as (1).

kr chowdhary

TOC

2/ 17

TM that accepts empty languages

Let Le (empty language) and Lne (not empty language)are
languages based on {0, 1}∗ strings. If L(Mi )) = 0,
/ Mi does not
accept any input. However, w ∈ Le . We define Le as language
consisting of strings of all TMs whose language is empty
If L(Mi ) is not empty language, then w is in Lne . Lne is language of
all the codes of TM that accept at least one string.
Le = {R⟨M⟩|L(M) = 0}
/
lne = {R⟨M⟩|L(M) ̸= 0}
/
we will show that Lne is RE but not Recursive. Le is non-RE.

kr chowdhary

TOC

3/ 17

Lne is RE
Theorem
Lne is RE.

Proof.
We have only to show that a TM M accepts Lne .

The operation of M is: M takes input < Mi >; guesses input w
which Mi might accept; M tests whether Mi accepts w. For this Mi
simulates UTM U. If Mi accepts w, then M accepts its own input
< Mi >. Hence, if Mi accepts even one string, M accepts Mi . ∴,
L(M) = Lne , and Lne is RE since it is accepted by TM. 2
kr chowdhary

TOC

4/ 17

An arbitrary TM halts for all inputs is undecidable.

Theorem
An arbitrary TM halts for all inputs is undecidable

Proof.
Let TM A halts for input v ∈ {0, 1}∗ . Input is accepted if v = R(M)
for some TM M, that halts for all the inputs strings. Input is
rejected if either v is not the representation of a TM or it is
representation for some TM that does not halt for some input string.

continued . . .

kr chowdhary

TOC

5/ 17

An arbitrary TM halts for all inputs is undecidable . . .

Reduction: is used to create a solution to the halting problem from
machine A.
First action of reduction R is find out if i/p has format of R(M),
followed by w. If no, R erases i/p and leaves tape blank.
When i/p is in correct format, (R(M)w), R constructs the R(M´) of
M´, that when run with i/p y:- erases y from tape, writes w on tape, and runs M on w.
∴, R(M´) = erase original input of tape+ write w on tape +R(M).
(R(M´) is designed to ignore the i/p w).
M´halts iff computation of M with i/p w halts.

kr chowdhary

TOC

6/ 17

An arbitrary TM halts for all inputs is undecidable . . .

If i/p is not of the form R(M)w, R produces null o/p, which is
rejected by A. Otherwise R generates R(M´). ∴, i/p is accepted iff
it is of the form R(M)w, where M halts on input w. Since halting
problem is undecidable, there is no TM A that solves the halt for all
strings w. 2

kr chowdhary

TOC

7/ 17

Non-trivial properties
Rice’s theorem after Henry Rice, states that if S is a non-trivial
property of Turing-recognizable languages, then the problem, Given
a TM M , “does L(M) have the property S?”is undecidable.
An example of a property of Turing-recognizable languages: the
property of being a regular language, is undecidable.
A property S of Turing-recognizable languages is non-trivial if some
recognizable languages have the property and others do not.
Definition: Let S be a property of Turing-recognizable languages.
We say that S is non-trivial if there exist Turing-recognizable
languages L1 and L2 such that L1 ∈ S but L2 ∈
/ S. If a property of
Turing-recognizable languages is not non-trivial, we call it trivial.
Example 1: The class of languages
SREGULAR = {L|L is regular}
is a non-trivial property of Turing-recognizable languages, since the
language L1 = {an |n ≥ 0} is a member of SREGULAR (and therefore
also recognizable, as SREGULAR is a property), whereas the language
L2 = {an b n |n ≥ 0} is also recognizable, but not a member of
SREGULAR , as it is a non-regular language.
kr chowdhary

TOC

8/ 17

Language problem
Example 2: There are only two ways of violation the conditions for
being non-trivial. The properties
Sall = {L|L is Turing-recognizable}

(1)

Snone = φ

(2)

are both trivial, and they are the only such properties. Sall is trivial,
since there does not exist a Turing-recognizable L2 such that
L2 ∈
/ Sall . Snone is trivial, since there does not exist a
Turing-recognizable L1 such that L1 ∈
/ Snone .
We know that there is no algorithm that decides whether a TM
halts for all the inputs w. ∴ LΣ∗ is undecidable.
Language of property P is, LP = {R(M)|L(M) satisfies the property
P}. In fact Lε , L0/ , Lreg , LΣ∗ are language properties.
A property P of RE set is trivial if: there are no RE sets L(M) (i.e.,
empty) satisfying P, or every RE set L(M) (i.e., all R(TM)) satisfies
P. Otherwise it is nontrivial.
Rice’s theorem: Any property that is satisfied by some (not all, and
not empty) sets is undecidable. I.e., any nontrivial of a language
accepted Turing machine
is undecidable.
kr chowdhary
TOC
9/ 17

Examples of non-trivial properties
Let L={all ASCII character sequences s1 , s2 , . . . |si is a C program ci
with the property that each ci when run on input x ∈ {0, 1}∗ accepts
iff x is Regexp}
Rice’s theorem says that languages such as L above are not
decidable, i.e., it is impossible to classify all C programs (or
equivalently TMs) into those whose languages are regular and those
whose languages are not regular.
Mathematically, given the property P, let
L = {< M > | M is TM and P(Lang(M))}
Example 3: The following are examples of non-trivial properties of
Turing-recognizable languages:
The class {φ } whose only member is the empty language (not to be
confused with the empty property Snone
The class {Σ∗ } whose only member is the language of all strings
over alphabet Σ.
The class of languages that have the empty string ε as an element.
The class of context-free languages
The class of Turing-decidable languages
kr chowdhary

TOC

10/ 17

Examples of non-trivial properties
Definition: Let S be a property. Then the language STM is defined
as
STM = {⟨M⟩|L(M) ∈ S}.
The result that we shall now state and prove, states that STM is
undecidable whenever S is non-trivial.
Exmaple Consider the property SREGULAR defined above. Then,
STM = {⟨M⟩|L(M) is a regular language }
We show that if S is a non-trivial property of Turing-recognizable
languages, then we can reduce ATM to STM .
In other words, we show that, given ⟨M, w ⟩ we can construct the
description of a machine a ⟨M ′ ⟩ such that M accepts w if and only
if L(M ′ ) ∈ S.

kr chowdhary

TOC

11/ 17

Rice’s Theorem
Theorem
If P is nontrivial property of of r.e. language then LP is non
recursive(Undecidable)

Proof.
Let P is nontrivial property that is not satisfied by empty language.
We will show that LP = {R(M)|L(M) satisfies P} is not recursive.
Since, LP is nontrivial, ∃L, L ∈ LP . L cannot be 0.
/ Let TM ML
accepts L.
we design R (reducer) to transform R(M)w to R(M’). The M’ runs
on y as:
- write w to right of y, producing ByBwB;
- run M on w; (acts as gate keeper), (1st tm)
- if M halts when run with w, then run ML with i/p y. (2nd tm).
Contd. next slide . . .

kr chowdhary

TOC

12/ 17

Rice’s Theorem proof continued . . .

In this case result of computation of M´with i/p y is exactly that of
computation by ML with y. ∴, L(M´) = L(ML ) = L, and L(M´)
satisfies P.
If M does not halt with i/p w, then M´never halts regardless of y.
∴, no string is accepted by M´, and L(M´) =0.
/ (does no satisfy P)
∴, M´accepts 0,
/ when M does not halt with i/p w, and M´accepts L
when M halts with w. Since L satisfies P and 0/ does not, L(M´)
satisfies P iff M halts when run with i/p w.

kr chowdhary

TOC

13/ 17

Rice’s Theorem proof continued . . .

Assume that Lp is recursive. Then there is a machine MP that
decides membership in LP . The machines R and MP combine to
produce a solution to halting problem. ∴, the property P is not
decidable.

2

kr chowdhary

TOC

14/ 17

Problem of determining whether a language accepted by
TM is CFL, is undecidable

By rice’s theorem, it is sufficient to show that property “is CF”, is
nontrivial property of RE language. It is accomplished by one RE
language that is CF and another not. The 0/ and {ai b i c i |i ≥ 0} are
both RE and former as CF and latter as not.
Applications of Rice’s theorem: We now have any number of
undecidable questions about TM’s:
- Is L(M) a regular language?
- Is L(M) a CFL?
- Does L(M) include any palindromes?
- Is L(M) empty?
- Does L(M) contain more than 1000 strings? Etc., etc.

kr chowdhary

TOC

15/ 17

Some Conclusions from Rice’s Theorem

Undecidability: whether a TM accepts a particular string;
whether a TM recognizes a particular language
whether a languages recognized by TM can be recognized by a
simpler machine, like FA.
Rice’s theorem does not say any thing about those properties of
functions or programs, which are not properties functions or
languages. E.g., whether the machine will run for 100 steps; whether
machine has five or more states; no general purpose computer can
solve general problem of determining whether or not a program is
virus free - is undecidable.

kr chowdhary

TOC

16/ 17

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

17/ 17