Semiodločljiv problem

Iz MaFiRaWiki

Problem prepoznavanja podmnožice A \subseteq B je semiodločljiv ali semirešljiv, če obstaja tak Turingov stroj, ki sprejme element x \in B in se ustavi, če je x \in A, in divergira, če je x \not\in A.

Primeri

Primeri semiodločljivih problemov:

Glej tudi

Osebna orodja