DTS resici rozhodovaci problem P

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: DTS resici rozhodovaci problem P

Re: DTS resici rozhodovaci problem P

od Myshaak » 16. 8. 2010 23:17

Almer píše:Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?
Jak uz bylo receno (a jak uz je Ti doufam jasne), DTS se obecne rozhodne zastavit nemusi ( while(true){;} ). Nicmene v definici DTS resi problem P je pozadavek, ze DTS se na kazdem vstupu zastavi.
Mozna ale tusim, kde mohlo dojit trochu k nejasnostem - ono je vic (ekvivalentnich) definic TS, aspon pokud si to dobre pamatuju. Jedna, kde je proste mnozina koncovych stavu, kam kdyz se stroj dostane, tak skonci ("prijme", rekne ANO...), jinak treba nekde zacykli. Druha (ktera se spis pouzivala prave ve Slozitosti), kde jsou dva zvlastni stavy qy (jeden jediny, ne mnozina) pro prijimuti (ale POZOR, prijimuti ne v "automato-gramatickem" smyslu "rozeznal jsem, ze slovo patri do daneho jazyka", ale prijimuti ve smyslu "odpoved na zadani je ANO") a qn pro odmitnuti. I tento stroj se muze nekde zacyklit.
Je potreba si tento rozdil uvedomit - zatimco v Autogramech byl TS na testovani, zda je slovo z daneho jazyka, tady je na rozhodovani, jestli zadani spada do "kategorie ANO" nebo "kategorie NE". Je to sice ekvivalentni, ale musi se clovek nad tim zamyslet, na jaky jazyk bude kde testovat. :)

Definice rika, ze DTS M resi problem P <=> M vzdy zastavi a L(M) = L(P)y. Jo mimochodem byl tam takovy maly predpoklad, ze rozhodnout, zda x e P jde polynomialne (=preprocessing, ktery rekne, jesti x je zadani problemu, nebo jen nesmyslny retezec). Otazkou tedy neni, zda na vstupu x skonci TS v nejakem koncovem stavu (jako v "Autogramech"), ale v kterem z nich.
Kdybys za L(M) vzal ne vstupy, ktere skonci v qy, ale vstupy, ktere skonci bud v qy nebo v qy, tak bys s tim nemohl postavit definici pro stroj resici problem P. (Myslim ze treba stroj, ktery nehlede na vstup, osetreny preprocessingem, skoci hned do libovolneho z tech dvou koncovych stavu by pak "resil" libovolny problem [ pze v takovem pripade opravdu L(M) = L(P) = L(P)y U L(P)n ], coz nedava smysl ;) )

Re: DTS resici rozhodovaci problem P

od beaver » 16. 8. 2010 00:23

Almer píše:Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?
Ty michas jablka a hrusky. Turinguv stroj (a je celkem jedno jaky, protoze pokud neni linearne omezeny, tak jsou vsechny varianty stejne silne) je jen jinym modelem pro rekurzivne spocetne jazyky. Das stroji (funkci, necemu, ...) slovo a cekas, co ti na to odpovi. Bud rekne "ANO" a pak vis, ze slovo do jazyka patri, nebo bude divergovat.

Jestli je stroj deterministicky nebo ne je z hlediska halting problemu fuk. Zajimave je to jen kdyz uvazujeme casove slozitosti.

Mas v tom pekny hokej. Doporucuju zopakovat si Automaty a gramatiky a pak si precist Johanciny pohadky o vycislitelnosti. http://atrey.karlin.mff.cuni.cz/~johank ... lnost.html

Re: DTS resici rozhodovaci problem P

od cunav5am » 15. 8. 2010 20:10

Ne, DTS se opravdu nemusí zastavit. Halting problem je otázka zda se daný DTS zastaví na daném vstupu.
Totiž, co do výpočetní síly (vyčíslitelnosti) jsou DTS a NTS ekvivalentní, protože lze výpočet NTS simulovat na DTS (průchodem výpočetního stromu do šířky). Samozřejmě, rozdíl je v "délce výpočtu".

Re: DTS resici rozhodovaci problem P

od Almer » 15. 8. 2010 20:01

Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?

Re: DTS resici rozhodovaci problem P

od cunav5am » 15. 8. 2010 17:26

Ano, DTS se samozřejmě nemusí zastavit a potom je to to samé, jako by odpověděl NE. Někdy se proto taky odmítací stavy neřeší a stroj se prostě nechá cyklit. Problém je ale v tom, jak poznat, že stroj cyklí (halting problem).

Lépe řečeno, L(M) je množina slov na kterých se M zastaví v přijímacím stavu po konečně mnoha krocích (někdy se přidávají požadavky na počet kroků v závislosti na délce vstupu, jako pro P, apod.)

Re: DTS resici rozhodovaci problem P

od stviper » 15. 8. 2010 17:19

Almer píše:DTS se vzdy zastavi. Bud v koncovem stavu qy nebo qn cimz prijme nebo ne.

Nemusi se zastavit NTS, ktery neprijima bud koncovym staven qn nebo nezastavenim.
DTS sa nemusi vzdy zastavit, co ak ti zadefinujem prechodovu funkciu tak, ze sa ti DTS zacykli? Potom nikdy nedostanes odpoved ANO/ NE. Teda nevies o tom rozhodnut.

Re: DTS resici rozhodovaci problem P

od Almer » 13. 8. 2010 13:46

DTS se vzdy zastavi. Bud v koncovem stavu qy nebo qn cimz prijme nebo ne.

Nemusi se zastavit NTS, ktery neprijima bud koncovym staven qn nebo nezastavenim.

Re: DTS resici rozhodovaci problem P

od Myshaak » 13. 8. 2010 11:20

Almer píše:V definici mam napsano, ze DTS s programem M ma jazyk L(M), coz je seznam vstupnich ktere DTS s programem M prijima ( tedy pouze prijem nikoliv odmitnuti ). A pak dale, ze DTS s programem M resi rozhodovaci problem P , pokud se M vzdy zastavi a navic ze L(M) je L(P)y.

Neni resenim i neprijeti? tedy L(M) je L(P)y u L(P)n? nebo je zla definice toho L(M)? Nejak se mi nezda, ze se bere jenom odpoved ano, protoze ne by mela byt taky platna odpoved ( jakoze zastaveni v koncovem stavu je defacto uznani ze problem x je instane P a prijeti nebo odmitnuti je odpoved ANO / NE ).
Nemam u sebe poznamky a nechce se mi u toho dlouho premyslet, ale matne si vzpominam, ze byl u toho nejaky zadrhel kvuli "odmitnuti nekonecnym vypoctem" (ne jen "koncovym stavem"). Pak by to asi nefungovalo... :) (doufam, ze nerikam blbost, ale zkus se nad tim zamyslet)

DTS resici rozhodovaci problem P

od Almer » 12. 8. 2010 14:54

V definici mam napsano, ze DTS s programem M ma jazyk L(M), coz je seznam vstupnich ktere DTS s programem M prijima ( tedy pouze prijem nikoliv odmitnuti ). A pak dale, ze DTS s programem M resi rozhodovaci problem P , pokud se M vzdy zastavi a navic ze L(M) je L(P)y.

Neni resenim i neprijeti? tedy L(M) je L(P)y u L(P)n? nebo je zla definice toho L(M)? Nejak se mi nezda, ze se bere jenom odpoved ano, protoze ne by mela byt taky platna odpoved ( jakoze zastaveni v koncovem stavu je defacto uznani ze problem x je instane P a prijeti nebo odmitnuti je odpoved ANO / NE ).

Nahoru