Emptiness Problem

The Emptiness problem is a decision problem asks if a given machine model rejects every word. It is decidable for DFAs and NFAs

Problem Specification(s) §

General §

Given a machine $M$, does $M$ reject (not accept) every string $w$?

Decidability §

The decidability of the problem requires a restructuring. Let $L$ be a language given by the TM encoding of $M$

$${\text{EMPTY}}_k=\{⟨M⟩|\text{M is a machine of type k where L(M)=∅}\}$$

Then, we need to check if $L$ is T-decidable.

The FSA Emptiness Problem is decidable ^theorem-fsa

That is,

$${\text{EMPTY}}_{FSA}=\{⟨M,w⟩|\text{M is a FSA that accepts w}\}\text{ is T-decidable}$$

Proof

Surprisingly straightforward (a somewhat causal proof by TM Simulation):

• We can use any exhaustive graph search algorithm (such as BFS or DFS) to check if there is a path from the initial state of $M$ to any accept state.
• By the Church-Turing Thesis, this algorithm can be run on a Turing Machine, $T$.
• If such a path exists, reject (because it must accept some $w$ given by the path, hence non-empty). Else accept.
• $T$ will always halt because $M$ will have finite number of states, and consumes one character from the input string at every step. At some point, the entire (finite) input string is consumed, so we can stop.

The TM Emptiness Problem is undecidable ^theorem-tm

$${\text{EMPTY}}_{TM}=\{⟨M,w⟩|\text{M is a TM that accepts w}\}\text{ is recognisable, but not decidable}$$

Proof

This is a proof by reduction that depends on R1:

• The acceptance problem reduces to the emptiness problem.
• The acceptance problem is undecidable
• Therefore, the emptiness problem is undecidable.

Reductions §

R1: TM Emptiness reduces to TM Equivalence

That is,

$${\text{EMPTY}}_{TM}\le E{Q}_{TM}$$

Proof

Assume $H$ is the decider to the TM equivalence problem, it takes in $⟨M,N⟩$ and decides f $L(M)=L(N)$. We now construct a new TM $S$ the decides ${\text{EMPTY}}_{TM}$:

• $S$ needs to take in an input $⟨M⟩$ and decide if $M$ is empty
• First, create a new TM decider called $T_{\varnothing }$ which rejects everything. This can be easily achieved by making a ‘dead state’. Then $L(T_{\varnothing })=\varnothing$
• Then, run $H$ on $⟨M,T_{\varnothing }⟩$. Since $H$ is a decider, it will accept if $M\sim T_{\varnothing }$ (and then $M$ is ‘empty’) and rejects if $M$ is not empty.

Thus, we have a decider that determines if $L(M)=\varnothing$ for a given $M$. Hence, we have proven the reduction.