Epätyhjyysongelma

Epätyhjyysongelmalla tarkoitetaan kysymystä siitä, hyväksyykö jokin mielivaltainen Turingin kone yhtään syötemerkkijonoa.^lähde? Kyseessä on pysähtymisongelman tavoin ratkeamaton ongelma. Ongelman voi esittää myös formaalina kielenä seuraavasti: $NE=\{c\in \{0,1\}^{*}|L(M_{c})\neq \emptyset \}$