Undecidability Of The Empty Language Problem (etm ) (8.1.3.3.1) - Undecidability and Introduction to Complexity Theory
Students

Academic Programs

AI-powered learning for grades 8-12, aligned with major curricula

Professional

Professional Courses

Industry-relevant training in Business, Technology, and Design

Games

Interactive Games

Fun games to boost memory, math, typing, and English skills

Undecidability of the Empty Language Problem (ETM )

Undecidability of the Empty Language Problem (ETM )

Introduction & Overview

Read summaries of the section's main ideas at different levels of detail.

Quick Overview

The **Empty Language Problem (ETM)** asks if the language accepted by a given Turing Machine (TM) is empty. This problem is **undecidable**. Its undecidability is proven by a many-one reduction from the Halting Problem (HALTTM). A reduction function takes an instance of HALTTM (\) and constructs a new TM, M', such that M' accepts no strings (i.e., L(M') is empty) if and only if M *does not* halt on w. Conversely, if M halts on w, M' accepts *all* strings. Since deciding if L(M') is empty effectively decides the Halting Problem, and the Halting Problem is undecidable, ETM must also be undecidable.