Odločljiv problem

Iz MaFiRaWiki

(Preusmerjeno iz Nerešljiv problem)

Problem prepoznavanja podmnožice A \subseteq B je odločljiv ali rešljiv, če zanj obstaja algoritem ali Turingov stroj, ki ga reši, kar pomeni: algoritem, oziroma Turingov stroj, sprejme element x \in B in odgovori z "da", če je x \in A, in z "ne", če je x \not\in A.

Če tak ne algoritem obstaja, je problem nerešljiv ali neodločljiv.

Primeri

Primeri rešljivih problemov:

Primeri neodločljivih problemov, ki so semiodločljivi:

Glej tudi

Osebna orodja