Ustavljivost linearno omejenih avtomatov

Ravno danes smo po vajah asistenta vprašali, kaj in kako, prišli smo tudi na LOA, pri katerih se dejansko da ugotoviti, ali se program na njih zacikla (mora pa biti LOA determinističen), no, po vsem skupaj mi je pa Cofko potem na hitro omenil, kaj točno ga pri celi stvari še vedno bega. Sem potem malo razmislil in veste, v čem je hec? Program, ki bi ugotovil, ali se nek program na nekem LOA zacikla, je sicer možno napisati, problem pa je, da ga v nekaterih primerih (pri nekaterih vhodih) enostavno ne moreš pognati - ker imaš na voljo premalo pomnilnika, s katerim bi izvedel simulacijo!

Nic nisi prikrajsan za odgovor - program se nikoli ne zacikla in to je tista bistvena razlika proti TS. V kocno mnogo casa bos za vsak program p in njegov vhod v dobil odgovor - program p se na vhod v zacikla ali pa program p se na vhod v konca (magar z napako -premalo pomnilnika).

Cofko, torej ti se vedno trdis, da se problema ustavljivosti LOA programa ne da narediti z LOA programom. Je dokaz iz strani je lep in sploh preprost ampak velja za TS. Na tej isti strani pise kar dvakrat da problem ustavljivosti ni neresljiv ce omejimo pomnilnik (takoj nad dokazom in se poglavje nizje - "Common pitfalls"). Malo razmisli, kako se mora program troble simulirat pa ti bo kmal jasno, da zmanjka memorije.

Torej moj simulator potrebuje tocno toliko rama kot ga potrebuje program p v svojih maksimalno moznih korakih, da se ustavi. Torej za k=1, s=2 (binarno) in n=8 (1 byte) se mora program ustaviti najkasneje v 2048 korakih ali pa se cikla. Seveda je pa ze 64202 povedal koliko moznih stanj ima 10MB program.

Torej vsi programi, ki imajo prostorsko zahtevnost vecjo od O(n) niso primerni za LOA.

To se ne pomeni, da se jih na LOA ne da izvajati - pomeni le da moramo imete dovolj majhen vhod, da so potrebe po memoriji manjse od k*n.

Ja porabi vec pomnilnika ampak neodvisno od programa p pac pa odvisno od velikosti vhoda v (ne pa vsebine vhoda)-> LOA princip. Se bolj realno moj program za preverjanje bo porabil priblizno 2 krat toliko pomnilnika kot tvoj program p za vhod v.

Ne bo samo meni zmanjkalo pomnilnika, ce tak program pozenes na realnem racunalniku mu bo tudi zmanjkalo pomnilnika. Program o katerih govoris so cisti TS in ne LOA in za take program je LOA presibek. Ce take pozenes na realnem racunalniku ti bo pri določenem vhodu zmanjkalo pomnilnika. Tocno to situacijo simulator ugotovi in se ne zacikla sam.

Zopet: Trdim, da se da napisati program halt(p,i), ki za vsak program in vsak vhod pove ali se program p zacikla ali ne glede na vhod i ce je pognan na realnem racunalniku in se hkrati sam ne zacikla. Program Trouble ni LOA in za njega halt(p,i) vrne : Program nima neskocnega cikla - se konca z rezultatom OUT OF MEMORY na simuliranem racunalniku.

Itak, da ima OS neskoncno zanko v sebi in ce od zunaj ne spremenimo nobenega bita vhoda, se ne bo nikoli koncal. Ce bi OS simularal bi pri danem vhodu ugotovil da se cikla. Podobno velja tudi za vse serverje, ki cakajo na input. (while(true) { process_input(); sleep(delay); } - ce to ni neskoncen cikel potem res nic ni. Vazno dejtvo si spregledal -ugotoviti moras, ce se cikla na podani vhod, ne da se vhod med delovanjem spreminja.

Ja porabi vec pomnilnika ampak neodvisno od programa p pac pa odvisno od velikosti vhoda v (ne pa vsebine vhoda)-> LOA princip. Se bolj realno moj program za preverjanje bo porabil priblizno 2 krat toliko pomnilnika kot tvoj program p za vhod v.

Ne bo samo meni zmanjkalo pomnilnika, ce tak program pozenes na realnem racunalniku mu bo tudi zmanjkalo pomnilnika.

Nikakor pa ne bo simulatorju zmanjkalo pomnilnika, ce ga je ze na zacetku dost, da se zazene.

Ce tvoj program p za podani vhod nima dost rama potem mu ga bo zmanjkalo tudi v simulatorju. NE bo pa zmankalo simulatorju rama v kolikor, ga poganjas na 2x toliko pa se mal rama.

Zopet: Trdim, da se da napisati program halt(p,i), ki za vsak program in vsak vhod pove ali se program p zacikla ali ne glede na vhod i ce je pognan na realnem racunalniku in se hkrati sam ne zacikla. Program Trouble ni LOA in za njega halt(p,i) vrne : Program nima neskocnega cikla - se konca z rezultatom OUT OF MEMORY na simuliranem racunalniku.

Ko tvoj halt(znotraj mojega trouble) vrne OUT OF MEMORY potem jaz vse skupaj zaciklam z while(true) in pride do protislovja. Ker tvoj halt je namreč rekel, da mi zmanjka spomina.

Ti sploh zastopis kaj je to LOA avtomat: Velikost traku je linearno odvisna od velikosti vhoda. Enako velja za racunalnik - rama imam le toliko, da velja linearna odvisnost glede na velikost vhoda.

2. Omenjeni nacin realizacije halt(p,i) pri vhodu halt(t,t) pac na navideznem racunalniku pozene trouble(t), ta zopet pozene halt(t,t), ta zopet trouble(t), ... neskoncna rekurzija na TS ... na LOA pa pride do tega da trouble(t) enkrat pac ne more pognati halt(t,t), ker ta pravi, da nima dovolj pomnilka za zagon. Takrat se zadnji trouble verjetno razsuje, zadnji pognani halt to ugotovi in vrne true (trouble se ustavi), zunanji troble to vidi in se zacikla, zunanji halt to ugotovi in vrne false, zunanji trouble se konca, zunanji halt to vidi in vrne true, .... do zadnjega halt, ki pac vrne true ali pa false glede na to kako globoko je vsa stvar sla - odvisno od rama - vsekakor pa ne neskoncna.

Moje delo je da pokazem, da tak program obstaja ne da zagotovim ram za njegov zagon. Povem ti le koliko ga potrebujes, ce zelis na njem simulirati ustavljanje programa p na vhodu v. V kolikor, ga nimas toliko zmanjsaj vhod. O programih o katerih ti govoris imajo itak neskoncne potrebe po pomnilniku in so kot taki neprimerni za racunalnik. Vendar ce bi jih ze pognal bi se na racunalniku prej kot slej ustavili - isto bi se zgodilo na simulatorju - in torej dela pravilno.

Kot ze receno LOA automat se v teoriji prilagaja vhodu - racunalnik pa ne - torej ima neko fiksno kolicino rama, ki zadostuje za izracun vhodov, dokler so dovolj majhni.

Jest trdim, da je problem ustavljivosti resljiv za vsak program p za vsak vhod v na LOA.

Povem ti le koliko ga potrebujes, ce zelis na njem simulirati ustavljanje programa p na vhodu v. V kolikor, ga nimas toliko zmanjsaj vhod.

To, da se ustavi še ne pomeni, da dela pravilno. More pravilno odgovoriti ali se program zacikla ali ne. In če je možno, da pri nekem vhodu za nek program reče tako ja kot ne, je vsaj ena izmed obeh napačna. In to pomeni, da program ne deluje pravilno. Kajti ti dve stvari se izključujeta. Ali se zacikla ali pa ne, oboje pa ne. S čem se pri tem razmisleku ne strinjaš?

1) se da napisat program za LOA, ki na vhodu sprejme program in ugotovi, ali se podani program konca (magar z napako) ali pa se zacikla (je pa neprakticen) ne da bi se sam zaciklu.

Kaj pa je računanje pi? Ker je dokazano neperiodičen in tudi neskočen boš porabil vso kapaciteto, ki ti jo vesolje ponuja, če želiš pi natačno izračunat. Pa še ti ne rata. Pa računanje pi-ja je vsekakor program za LOA, saj ga veliko superračunalnikov računa dan in noč

Kaj se zgodi, ko v trouble pokličemo halt?

Točno to sem želel. Ne moreš preverit za vse, vendar le za dovolj majhne. Pa tudi npr. za OS tega ne moreš prevert, ker nimaš podanih vseh vhodov na začetku. Vendar kot sem napisal, to ni čisto z definicijo problema ustavljivosti, saj imaš tam vse vhode podane. Gleda naslova pa: kaj pa je računalnik drugega kot LOA. Ustavljivost računalika je samo poseben primer ustavljivosti LOA. Čeprav sem začel rahlo dvomit v to, kot sem že napisal:

Kaj pa če je vhod tolikšno število ničel, kot želimo imeti decimalk pi-ja? To je linearno, pa vseno porabi poljubno veliko pomnilnika. In tudi konča se.

No z lahkoto dam kakšne try-catch okoli if stavka. Karkoli že halt odgovori ne dela prav. V primeru, da odgovori true ali false, se ne prepriča, če je tisto kar odgovir prav. Pa v tem primeru, to pomeni, da ga u trouble jaz spet spravim v protislovje. Če pa odgovoriš error pa tudi ne bo v redu. Na vprašanje ali se program zacikla ali ne mi odgovoriš z error.

halt(p, i) {
 n=sizeof(i);
 size_ram=k*n+m;
 ram=get_ram(size_ram);
 if (ram==null) return error;
 load_in_ram(ram,i); 
 vm=make_init_virtual_machine(ram);
 p.state==run;
 for (step=0;step<k*n*2^n+1;step++) {
   execute_one_step(vm,p);
   if (p.state==terminated) return true; //program se ustavi 
 }
 return false; //program se cikla
}

Na vprašanje ali se program zacikla ali ne mi odgovoriš z error.

1) se ne da napisat program za LOA, ki na vhodu sprejme program in ugotovi, ali se podani program pr nekem vhodu konca (magar z napako) ali pa se zacikla

Kolikokrat ti moram napisat: to je vse kar sem hotel slišat. V določenih primerih mi ne moreš povedat ali se ustavi ali zacikla, ker imaš premalo rama. Poglej si kaj trdiš ti in kaj trdim jaz, oboje je odebeljeno. Kot vidiš se strinjava. Pa ker si napisal ker ne laufam na LOA sklepam da računalnik != LOA. Torej, za LOA tak program obstaja, za računalnik pa ni nujno. Kar že cel čas trdim, mene samo računalnik zanima.

Glede tvoje psevdokode: sploh nikjer nimaš definirano kaj sta k in m, zato se ti usuje

Če reče tvoj halt true ali false pride v protislovje, v tem se strinjava?

Zunajni halt reče, da se zaciklam, notranji pa, da je bil error. Vrneš mi dva različna rezultata na istih vhodnih podatkih

Parametra k in m sem enkrat ze definiral - sta konstantna - velika kolikor ces le ta velikost ne sme biti odvisna od vhoda. Lahko je seveda od programa. Recimo, da program vhod 3 krat spravi v notranji buffer in ima svoje kode in notranjih stanj za 5MB potem je k=4 in m=5MB al je tko tezko zastopt.

Vhodni podatki so ze isti samo prvic stvar zazenes na LOA, drugic na ne, ker ugotovi, da ima premalo pomnilnika glede na zahtevan vhod.

V teoriji pa kar naj obstaja tak program, meni tak program v praksi nič ne koristi, ker ga ne morem uporabljat.

Sklep je pa (vsaj z moje strani)takle: v teoriji vse lepo in prav ampak v praksi ne štima. Tebi je bolj pomembna teorija meni pa praksa. In takole ne bova nikoli prišla do skupnega sklepa. Razen če tudi ti priznaš, da je v teoriji vse lepo in prav v praksi(natančneje računalniku) pa ne.

Teorija ti samo pove, da je omejeno število stanj, ne pove ti pa kako to določit. Problem tegale je, da moraš iti najprej moj program izvajat, da sploh vidiš koliko sta k in m(npr.kot si sam dal primer: kako ti veš, kolikokrat jaz vhod shranim v buffer). In ob tem izvajanju se lahko tvoj halt zacikla. Tega v tvoji psevdo kodi ni. Ti kar rečeš to imam. Ampak to ni res. Tako, da prosim, da dopolniš tvojo psevdo kodo, da vidim kako ju določiš.

size_ram=p.k*n+p.m; 

To, da ima premalo pomnilnika pa je tako tvoja krivda, ker mi ga premalo dodeliš. Sam praviš, da točno veš koliko največ ga lahko porabi, potem pa se ti zgodi to, da mi ga daš premalo.

Strinjam se, da je trouble za na TS, toda še vedno je računalniški program. In če hočeš za vse programe imet halt, ga moraš imeti tudi za tega.

Tu bi dopolnil: za vsak program p, ki je LOA.

Napišeš ga, vendar ne bo vedno počel tisto kar ti hočeš. Zdaj ali rečeš, da program ne deluje prav ali pa da to pride zaradi pomanjkanja pomnilnika je konec koncev vseeno. Dejstvo je, da rešitve za nekatere primere nimaš.

Za nekatere primere k-ja ne moreš določit brez izavajanja programa, npr. iskanje perfektnih lihih števil. Tudi programer ne ve kdaj, če sploh se tisto ustavi. Zato moraš to iti nujno izvajat, da bi ugotovil k. Pri tem prevejanju pa imaš problem, če imaš program, ki ima lahko neskončno stanj(zdaj lahko rečeš, da jih ima neskočno, ali pač toliko, da porabi ves pomnilnik. Vednar v obeh primerih moraš izvajat, da to ugotoviš). Če se še s tem strinjaš potem smo zaključili.

Saj, če ima neskončno stanj niti turningov ni. Ampak dejstvo je, da tudi taki programi obstajajo.

The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an unlimited paper tape, which is divided into squares that can contain one of a finite set of symbols.