CSCI 471: Complexity and Computability

LECTURE 6
Today:
• Undecidable Languages

1
Meiram Murzabulatov
 A universal Turing Machine
• Since TMs and programs are equivalent, we can think of TMs as
programs.
• Since programs are strings, we can consider languages whose
elements are programs.
• 〈M〉denotes an encoding of a TM M as a string
Theorem. We can make a Universal TM, a TM that takes any TM
description〈M〉 and any string w as input and simulates the
computation of M on w. 〈M,w〉
〈M〉 encoding of M
FINITE
CONTROL
〈 w〉 tape contents 〈w〉= 〈w1,…,wn〉
〈 q 0〉 state
 Encodings of DFAs, NFAs, CFGs, etc

• We can encode DFAs, NFAs, regular expressions, PDAs, CFGs,

etc into strings (of 0s and 1s).
• We can define the following languages:
ADFA = { 〈D,w〉 | D is a DFA that accepts string w }

ANFA = { 〈N,w〉 | N is an NFA that accepts string w }

ACFG = { 〈G,w〉 | G is a CFG that generates string w }

EDFA = { 〈D〉 | D is a DFA that recognizes the empty language }

EQDFA = { 〈𝐷!, 𝐷"〉 | 𝐷!, 𝐷" are DFAs and 𝐿(𝐷!) = 𝐿(𝐷") }

ECFG = { 〈G〉 | G is a CFG that generates the empty language}

 EDFA is decidable

EDFA ={ 𝑫 ∣ D is a DFA and L(D)=∅}

Proof Idea: A DFA accepts a string iff reaches an accept
state from the start state.
A = “On input 〈𝑫〉, where 𝑫 is a DFA:
1. Mark the start state of 𝑫.
2. Repeat until no new states get marked:
3. Mark any state that has a transition coming into it
from any state that is already marked.
4. Accept if no accept state is marked; ow, reject.”
 EQDFA is decidable
EQDFA = { 𝑫𝟏 , 𝑫𝟐 ∣ 𝑫𝟏 , 𝑫𝟐 DFAs and 𝑳(𝑫𝟏 ) = 𝑳(𝑫𝟐 )}
Proof Idea: Construct a new DFA D3 that recognizes
the symmetric difference of 𝐿(𝐷! ) and 𝐿(𝐷" ).
B = “On input 〈𝑫𝟏 , 𝑫𝟐 〉, where 𝑫𝟏 and 𝑫𝟐 are DFAs:
1. Construct DFA 𝑫𝟑 , as described.
2. Run TM A on 〈𝑫𝟑 〉.
3. If A accepts, accept; ow, reject.”

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 6

 ECFG is decidable

ECFG ={ 𝑮 ∣ G is a CFG and L(G)=∅}

Proof Idea: Test whether the start variable can generate a
string of terminals.
C = “On input 〈𝑮〉, where 𝑮 is a CFG:
1. Mark all terminals in 𝑮.
2. Repeat until no new variables get marked:
3. Mark any variable V where 𝑮 has a rule V U1U2…Uk
and each of U1 ,U2 , … , Uk has already been marked.
4. Accept if the start variable is not marked; ow, reject.”

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 7

 Recall

ADFA = { 𝑫, 𝒘 ∣ D is a DFA that accepts w } ü

ACFG = { 𝑮, 𝒘 ∣ 𝑮 is a CFG that generates w }ü

EDFA ={ 𝑫 ∣ D is a DFA and L(D)=∅} ü
EQDFA = { 𝑫𝟏 , 𝑫𝟐 ∣ 𝑫𝟏 , 𝑫𝟐 DFAs and 𝑳(𝑫𝟏 ) = 𝑳(𝑫𝟐 )}ü
ECFG = { 𝑮 ∣ G is a CFG L(G)=∅} ü
ETM = { 𝑴 ∣ 𝑴 is a TM and 𝑳(𝑴) = ∅}
8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 8
 Problems in language theory

ADFA ACFG ATM

decidable decidable ?
EDFA ECFG ETM
decidable decidable ?

EQDFA EQCFG EQTM

decidable ? ?

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 9

Undecidability
We will prove that there are some undecidable languages:
• i.e., problems a computer cannot solve no matter how
long it computes

The proof idea is “simple:”

There are more languages than there are Turing

Machines.

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 10

Question:

Let ℕ= {1,2,…} be the natural numbers.

Let 𝔼 = {2,4,6,…} be the even natural numbers.

Let ℤ = {…,-2,-1,0,1,2,…} be the Integers.

Which is largest, |ℕ|, |𝔼|, or |ℤ|?

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 11

 Are there more blue or yellow dots?
● ●
● ●
●● ●
● ●
● ●
● ●
●● ●
● ●
● ●
● ●
● ●
●● ●
● ●
● ●
● ●
● ●
●● ●
● ●
● ●
● ●
● ●
●● ●
● ●
● ●
● ●
● ●
●
Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 12
Set Theory
Set A Set B A function 𝑓: 𝐴 → 𝐵 is
𝒇
• 1-to-1 (or injective) if
𝑓 𝑎 ≠ 𝑓(𝑏) for 𝑎 ≠ 𝑏.

• onto (or surjective) if for all 𝑏 ∈ 𝐵,

some 𝑎 ∈ 𝐴 maps to 𝑏: 𝑓 𝑎 = 𝑏.

• correspondence (or bijective) if

it is 1-to-1 and onto, i.e.,
each 𝑎 ∈ 𝐴 maps to a unique 𝑏 ∈ 𝐵,
and each 𝑏 ∈ 𝐵 has a unique 𝑎 ∈ 𝐴
mapping to it.
13
How to compare sizes of infinite sets?

• Two sets are the same size if there is a bijection

between them.
• A set is countable if it is
– finite
– or it has the same size as ℕ (the set of natural numbers)
– or it is a subset of a countable set

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 14

Examples of countable sets
Ø, {0}, {0,1}, {0,1, …, 255}
𝔼= {2,4,6,…}
𝕆 = {1,3,5,7,…}
SQUARES = {1,4,9,16,25…}
POWERS = {1,2,4,8,16,32…}

|POWERS| = |SQUARES| = |𝔼| = |𝕆| = |ℕ|

A bijection 𝑓: ℕ → 𝔼 𝐢𝐬 𝑓 𝑛 = 2𝑛
Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 15
Are there uncountable sets?

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 16

Theorem. There is no bijection from the positive
integers to the real interval (0,1)

Proof: Suppose f is such a bijection:

n f(n)
1 2
0.28347279…
2 8
0.88388384…
3 6
0.77635284…
4 1
0.11111111…
5 5
0.12345678…
: :
k b=0.𝒅𝟏 𝒅𝟐 𝒅𝟑 … 𝒅𝒌 … 𝒅𝒌 =?
Construct 𝒃 ∈ (𝟎, 𝟏) that does not appear in the table.
b=0.𝒅𝟏 𝒅𝟐 𝒅𝟑 … , 𝒘𝒉𝒆𝒓𝒆 𝒅𝒊 ≠ 𝒅𝒊𝒈𝒊𝒕 𝒊 𝒐𝒇 𝒇 𝒊 .
17
 Diagonalization

The process of constructing a counterexample by

“contradicting the diagonal” is called
DIAGONALIZATION

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 18

 Exercises
Prove that |(1,2)| = |(0,1)| = |ℝ|

Is there a set bigger than ℝ?

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 19

 Let L be any set and P(L) be the power set of L

Theorem: There is no onto map from L to P(L)

Example: L = {a, b} P(L) ={Ø, {a}, {b}, {a,b}}

P(L) has more elements!

An element of L: a
An element of P(L): {a} or {b} or {a,b}

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 20

 Let L be any set and P(L) be the power set of L

Theorem: There is no onto map from L to P(L)

Proof: Assume, for a contradiction, that
there is an onto map f : L ® P(L)
We construct a set S that cannot be equal to f(y)
for any y ÎL. an element of L a set of elements of L

Let S = { x Î L | x Ï f(x) }
L = {a, b} P(L) ={Ø, {a}, {b}, {a,b}}
f(a)={b} f(b)={a,b}
a is not an element of f(a)={b}, so S={a}
b is an element of f(b)={a,b}, so S={a} (b is not in S)
Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 21
 Let L be any set and P(L) be the power set of L

Theorem: There is no onto map from L to P(L)

Proof: Assume, for a contradiction, that
there is an onto map f : L ® P(L)
We construct a set S that cannot be equal to f(y)
for any y ÎL. an element of L a set of elements of L

Let S = { x Î L | x Ï f(x) }

If S = f(y) then y Î S if and only if y Ï f(y)=S

yÎL

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 22

 How is that diagonalization?

y1∈f(y1)? y2∈f(y2)? y3∈f(y3)? y4∈f(y4)? …

y1 Y
Y N Y Y
y2 N Y
Y N Y
y3 N N N N
y4 Y N N Y
Y
! "

(yi ∈ S) = Y iff (yi ∈ f(yi)) = N

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 23
 For all sets L,
P(L) has more elements than L

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 24

 {0,1}* is countable
list all strings of length 0, of length 1, …

{ 〈M〉 | M is a TM } is countable
strings of 0s and 1s

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 25

 Not all languages over {0,1} are decidable

TM Deciders Languages over {0,1}

Sets of strings of
Strings of 0s and 1s
0s and 1s

L P(L)
For all sets L, P(L) has more elements than L

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 26

 Not all languages over {0,1} are recognizable

Turing Machines Languages over {0,1}

Sets of strings of
Strings of 0s and 1s
0s and 1s

L P(L)
For all sets L, P(L) has more elements than L

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 27

 Theorem. ATM is undecidable.

ATM = { 𝑴, 𝒘 ∣ 𝑴 is a TM that accepts 𝒘}

Proof: For contradiction, suppose a TM H decides ATM.
𝐚𝐜𝐜𝐞𝐩𝐭 𝐢𝐟 𝑴 𝐚𝐜𝐜𝐞𝐩𝐭𝐬 𝒘
𝑯 𝑴, 𝒘 = +
𝐫𝐞𝐣𝐞𝐜𝐭 𝐢𝐟 𝑴 𝐝𝐨𝐞𝐬𝐧! 𝐭 𝐚𝐜𝐜𝐞𝐩𝐭 𝒘
Idea: Let D be a TM that on input 𝑴 runs H on 𝑴, 〈𝑴〉
and does the opposite of H, i.e., accepts if H rejects and
rejects if H accepts.

Run D on 𝑫 . Does it accept or reject?

If D rejects 𝑫 ⟹ H accepts 𝑫, 〈𝑫〉 ⟹ D accepts 𝑫

28
 Using reductions to prove
undecidability
We want to prove that language L is undecidable.

Idea: Use a proof by contradiction.

1. Suppose to the contrary that L is decidable.
2. Use a decider for L as a subroutine to construct a
decider for ATM (or some other undecidable
language).
3. But ATM is undecidable. Contradiction!

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 29

 Prove that the following language are
undecidable via reduction from ATM

HALTTM= { 𝑴, 𝒘 ∣ 𝑴 is a TM that halts on string 𝒘 }

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 30

 Prove that ETM is undecidable

ETM = { 𝑴 ∣ 𝑴 is a TM and 𝑳 𝑴 = ∅}
Proof: Suppose to the contrary that ETM is decidable,
and let R be a TM that decides it.
We construct TM S that decides ATM.
S = `` On input 〈𝑴, 𝒘〉, where 𝑴 is a TM and w is a string:
(We need to run TM R on some input, but which ???)

8/29/23 Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 31

 Prove that ETM is undecidable

ETM = { 𝑴 ∣ 𝑴 is a TM and 𝑳 𝑴 = ∅}
Proof: Suppose to the contrary that ETM is decidable,
and let R be a TM that decides it.
We construct TM S that decides ATM.
S = `` On input 〈𝑴, 𝒘〉, where 𝑴 is a TM and w is a string:
1. Construct TM 𝑀′.
𝑀′ = `` On input x,
1. If x≠w, reject.
2. If x=w, run TM M on input w.
3. If it accepts, accept.’’
2. Run TM R on input <𝑴′>.

8/29/23
3. If R rejects , accept. O.w. reject.’’
Meiram Murzabulatov; based on slides by Sofya Raskhodnikova
ü 32
The Halting Problem

HALTTM = { 𝑴, 𝒘 ∣ 𝑴 is a TM that halts on string 𝒘 }

Prove that it is undecidable

Meiram Murzabulatov; based on slides by Sofya Raskhodnikova 33