Epätyhjyysongelma

Epätyhjyysongelmalla tarkoitetaan kysymystä siitä, hyväksyykö jokin mielivaltainen Turingin kone yhtään syötemerkkijonoa.Malline: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)\ne \mathrm{\varnothing }\}$