Ustavljivost linearno omejenih avtomatov

no jaz sem še vedno mnenja da tak program obstaja (da ga je možno naredit). Navsezadnje so programi digitalni in sprejmejo končno število vhodov

Jeti, da ne bi o tem ta imaš lahko neskočno zanko, kjer se ti en counter stalno povečuje. Poj ti pa tisto kar si ti napisal nič ne pomaga

Kaj pa če ne bi imel števca v tistem programu za iskaneje perfektenge lihega števil, ampak while(true) in znotraj zanke na random generiram število, za katerega probavam če je perfektno. Pa ne se mi obesit na random, lahko ga generiram na takle način.

Ali pa kaj če napišem program, ki na začetku pogleda koliko pomnilnika je na voljo in ga začne vsega zasedati. Tik preden pa nima čisto nič na voljo pa se zacikla. Ko boš ti šel s svojim nadzornim programom gledat kaj se dogaja, boš tudi sam zasegel vedno več pomnilnika(zato, da boš iskal, če se katere vrednosti ponavljajo) in potem bo moj program crknil, ker ne bo imel na voljo toliko, kot si je želel zasečti. Torej se vsa zadeva obesi zaradi tvojega programa. Sicer se ne bi.

Verjemem, da se da napisat kar dober nadzorni program. Vendar pa za vse programe ne bi deloval.

Sicer pa izvoli, napiši tak program.

Pa ravno v randomu je hec. Turingov stroj namreč že po sami definiciji deluje popolnoma deterministično. Vhod (začetna vsebina traku) je znan, bralno-pisalna glava je na začetku nad prvo celico traku, s čimer je določen prvi videni simbol, začetno stanje je določeno, funkcija prehodov med stanji je tudi nedvoumno definirana, iz vsega tega pa sledi, da je prvi korak izvajanja (in tudi vsi ostali) 100% predvidljiv.

Nadzorni program ne bi nič odžiral pomnilnika vhodnemu programu, saj bi ga le simuliral, opažena stanja pa bi si zapisoval v svoj pomnilnik. Vhodni program ne bi prav ničesar vedel o tem, da se v resnici ne izvaja na dejanskem računalniku, ampak je samo simuliran. Skratka pomislek o odžiranju pomnilnika je čisto odveč.

No pa utemelji, zakaj po tvojem naj ne bi deloval za vse programe. Vedno znova pozabljaš, da imamo na voljo končno mnogo pomnilnika, se pravi da se programi dejansko izvajajo na linearno omejenem avtomatu in ne na Turingovem stroju.

No ja - se da narest, da je treba zlo mal pomnilnika. Nadzorni program sprejme na vhod program in ga pozene (simulira) na zacetku v zacetnem okolju (okolje 0). Po izvedbi vsake instrukcije v vhodnem programu dobimo novo okolje (1,2,...). Po izvedbi n-te instrukcije dobimo okolje n in ga shranimo. Potem zopet startamo program od zacetka v okolju 0 in ponovi vse istrukcije do (n-1) - cim je prvi od okolij (0,1,...,n-1) enak okolju (n) se program cikla - drugace se ne - nalozis okolje n in pozenes instrukcijo n+1 ter postopek preverjanja ponovis. Memorije rabis za 2 okolja in le se ene par bajtov vec, je pa casovno zadeva zelo potratna.

Psevdo random ne pomeni, da gre nujno za perodicna zaporedja stevil. Deterministično pomeni le, da se da iz prejsnjih izhodov generatorja ugotoviti nesljednji izhod generatorja. Ker so nekatere funkcije "zelo" komplicirane govorimo o psevdo randomu. Sej tut zaporedje a(n)=a(n-1)+1 ne da periodicnega zaporedja, ni pa ravno dober random. Dober pseudo random mora prestat se kar nekaj zahtevnih statisticnih testov. V praksi se najbolje pac izkazejo peridocna zaoredja (z zelo velikimi periodami). Med branjem tega odstavka si lahko ze ugotovil, da decimalke stevila Pi pac niso random, res pa je da niso periodicne.

Kaj pa če za za naključna števila vzamemo kar podzaporedja števila pi(pa naprimer vsakič za eno mesto večje podzaporednje), ki se dokazano ne začne ponavljati(pi je tudi zelo deterministično določen)? To se ne bo začelo ponavljati.

Glede razlike v uporabi true randoma in psevdo randoma si preberi poglavje 9. v dodatni snovi za tor2 na Vilfanovi domaci strani (link). Povzetek - nedeterministicni TS je ekvivalenten TS edino eden lahko NP probleme izracuna v P casu - drugi pa (verjetno) ne. Seveda nedeterministicnega TS ne znamo sestavt zato uporabljamo TS z random odlocitvijo. S tem lahko nekatere probleme z veliko verjetnostjo pravilno resimo v P casu (primer je iskanje prastevil). Razlika med true random odlocitvami in prevdorandom so lahko le v porabljenem casu pa se te so se vedno v P, tako da vpliva prakticno ni.

There is another caveat. The undecidability of the halting problem relies on the fact that algorithms are assumed to have potentially infinite storage: at any one time they can only store finitely many things, but they can always store more and they never run out of memory. However, computers that actually exist are not equivalent to a Turing machine but instead to a linear bounded automaton, as their memory and external storage of a machine is limited. In this case, the halting problem for programs running on that machine can be solved with a very simple general algorithm (albeit one that is so inefficient that it could never be useful in practice). It involves running the program and trying to find a cycle over the states of the machine's memory.

while (true) {
 int i=rand();
 if (i==10) break;
}

Cofko, torej ti se vedno trdis, da se problema ustavljivosti LOA programa ne da narediti z LOA programom.