Pogovor:Odločljiv problem

Iz MaFiRaWiki

V tem primeru je potrebno razumeti besedo algoritem v strogem smislu, kot računsko proceduro, ki se pri vsakem podatku zaustavi v končnem času. V nasprotnem primeru bi lahko rešili problem zaustavitve z univerzalnim Turingovim strojem.193.2.67.50 14:30, 2 oktober 2006 (CEST)

Dve vrsti nerešljivosti

Pravzaprav obstajata dve vrsti nerešljivosti.

  • Ker je vseh jezikov nad abecedo z vsaj dvema simboloma neštevno mnogo in je Turignovih strojev samo števno mnogo, obstaja precej jezikov, ki so pretežki za razpoznavanje s Turingovimi stroji.
  • Nerešljivost v strožjem smislu pa pomeni, da problema ne moremo rešiti z algoritmom (Turingovim strojem, ki se vedno zaustavi).

Problem zaustavitve lahko formuliramo kot problem razpoznavanja jezika. Tako formuliran problem zaustavitve sodi med rešljive probleme po prvi definiciji (reši ga univerzalni stroj), a nerešljive po drugi, strožji definiciji. TomazPisanski 09:25, 4 oktober 2006 (CEST)

Ne razumem, kje sta tu dve vrsti nerešljivosti. Navedel si dva različna razloga, zakaj obstajajo nerešljivi problemi: eden sledi iz kardinalnosti, drugi pa je bolj konkreten (namrec, da konkretno podan jezik ni odločljiv).

Tudi ne razumem, kako lahko univerzalni stroj karkoli reši. Univerzalni stroj samo simulira ostale Turingove stroje. Kaj si hotel povedati? AndrejBauer 18:09, 4 oktober 2006 (CEST)

Vzemiva problem:

Vhod: Jezik L, beseda w
Vprašanje: Ali pripada w jeziku L?

Naj bo T(L,w) rezultat računanja Turigovega stroja v tem primeru. Ta rezultat je lahko YES/NO/\infty.

Če je res (w \in L če in samo če T(L,w) = YES), je problem rešljiv v šibkejšem smislu.
Če je res (w \in L  če in samo če T(L,w) = YES in w \notin L 
če in samo če T(L,w) = NO) je problem rešljiv v strožjem smislu.


 Vhod: Turingov stroj T, beseda w
 Vprašanje: Ali se T ustavi pri w?

U(T,w) se ustavi če in samo če se T ustavi pri w. Ergo, problem je rešljiv v šibkejšem smislu.

Kaj je pri tem narobe?TomazPisanski 19:34, 4 oktober 2006 (CEST)

Odločljivost in semiodločljivost

Aha, zdaj razumem. To, čemur praviš šibka odločljivost se imenuje semiodločljivost (semidecidable). Strožja oblika pa je običajni pojem odločljivosti (decidable). Bom dodal semiodločljivost v wiki. AndrejBauer 22:23, 4 oktober 2006 (CEST)


Alternativna definicija

Mi smo pri Teoriji računskih postopkov (na FRI) definirali stvari malo drugače (izhajajoč iz Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation):

  • semiodločljivosti smo dejali kar odločljivost (oz. jezik problema je bil rekurziven)
  • odločljivosti smo dejali izračunljivost (oz. jezik problema je bil Turingov - angl. recursively enumerable)
  • neizračunljivi so bili problemi, za katere ni obstajal Turingov stroj, ki bi razpoznal njihov jezik (npr. diagonalni jezik)

--PrimozLuksic 23:47, 4 oktober 2006 (CEST)

Ok, moramo paziti na obstoječo terminologijo, čeprav me to, kar si povedal, zelo preseneča. Odločljiv in rekurziven bi moralo biti isto, semiodločljiv pa bi lahko bil isto kot prešteven ali rekurzivno enumerabilen. Ustaljena angleška terminologija je:

  • decidable: there exists an algorithm deciding membership
  • semidecidable: there exists a Turing machine which terminates iff the element is in the set
  • recursive = decidable
  • semirecursive = semidecidable
  • computable: refers to a computable function. A set is usually called computable when its characteristic function is computable, which is the same as the set being decidable.

AndrejBauer 00:29, 5 oktober 2006 (CEST)

Osebna orodja