Epätyhjyysongelma

Wikipedia

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


Tämä tietotekniikkaan liittyvä artikkeli on tynkä.
Voit auttaa Wikipediaa laajentamalla artikkelia.