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 q
y (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 q
n 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 q
y, ale vstupy, ktere skonci
bud v q
y nebo v q
y, 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
)