» »

Ustavljivost linearno omejenih avtomatov

Ustavljivost linearno omejenih avtomatov

1
2
»

JerKoJ ::

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 Cof ::

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!:))


Jeti ravno to sem ti že cel čas hotel povedat. Na žalost se mi je mudilo na vlak, lahko pa naslendji teden podebatirava na to temo. Slivnik je rekel, da bo malo razmislil, me zanima kaj bo povedal. Sicer si bom pa sposodil tiste knjige, ki jih je priporočil, ker ta debata v zvezi z ekvivalenco človek in TS me precej zanima. Torej, če hočeš imeti program, ki ti za vsak podani program in vhod v ta program pove ali se ta program pri tem vhodu ustavi ne bo uspelo. Edino, če ga izvajaš na TS, ki ima neskočen pomnilnik.

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).


Tvojemu programu za preveranje precej hitreje zmanjka pomnilnika kot meni, saj ga potrebuješ vsaj 2x toliko kot jaz(zaradi shranitve 2 stanj sistema, med tem ko jaz hranim samo trenutno stanje). Tako kot je že Jeti rekel, tudi če obstaja tak program, ne bo deloval vedno. Ker mu zmanjka 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.


Ja, ko pomislim kako se more program simulirat, res vem, da zmanjka memorije. Vedar ne meni, temveč tebi. Tam samo piše, da je v primeru LOA ta problem rešljiv ni pa nobenega dokaza. In dokler ne ovržeš mojega dokaza(oz. samo malo razširjenega iz wikipedie) se nimava kaj zgovarjat. Razen če ti priložiš svoj dokaz in ga meni ne uspe ovreč.
Ars longa,vita brevis.

Zgodovina sprememb…

JerKoJ ::

Preprost dokaz:
http://www.everything2.com/index.pl?node_id=1394039

Something of some intrest to people is that the halting problem is solveable for linear bounded automata. This is because there is a finite number of possible states that an lba can be in. This value is k*n*(s^n) - where s is the size of the alphabet, n is the length of the tape, and k is the number of states. One can then observe an lba for this number of iterations. If the lba has not halted by that time, it must be in a loop and will never halt.


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.

Se glede porabe pomnilnika - LOA ima rama na volju linearno glede na velikost vhoda, pri cimer je faktor neodvisen od vhoda. Ce program rabi vec pomnilka kot linearno glede na vhod potem to ni program za LOA amapak za TS. 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.

Cofko Cof ::

Za začetek samo vprašanje: ali tvoj program, za preverjanje mojega programa p nad mojim vhodom i, porabi več pomnilnika, kot če bi jaz sam izvedel p nad vhodom i?

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.


Stanj imaš 2^(stevilo bitov pomnilnika v računalniku) * (število stanj procesorja) * (število pixlov na zaslonu) pa še veliko drugih stvari bi lahko dal v ta račun. To koliko je program velik sploh nima zveze s tem. Res pa je, da vsi pogrami ne speminjajo vseh bitov/pixlov..., in jih zato ni potrebno preverjati. Pa zakaj se more ustaviti v določenem številu korakov? Poglej si OS, ki lahko (teoretično) deluje poljubno dolgo, pa se še vseeno ne zacikla.

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


Je mar važno ali so primerni ali ne? Dejstvo je, da obstajajo, in če hočeš imeti program, ki bo deloval za vse programe, mora delovati tudi za njih.

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.


Torej mi praviš, da ne smem pisat programov, za katere tebi zmanjka pomnilnika? Oz. ti dati dovolj velikih vhodov? Pa ravno take programe hočem, kjer se to zgodi.

Pa še vseeno drži tisti dokaz:
Ti trdiš, da obstaja pogram halt(p, i) ki za vsak program in vsak vhod, ki mu ga podaš pove ali se ta program na vhodnih podatkih zacikla ali ne. Pri tem se sam ne zacikla in mu tudi nikoli ne zmanjka pomnilnika. Predpostavimo, da ga imamo.

Spet napišemo program trouble. Torej halt(s, s) v vsakem primeru vrne TRUE ali FALSE, to je ena izmed predpostavk. Po tem pa po istem razmišljanju kot je na linku od wikipedie pridemo v protislovje.

Kot kaže se bomo morali zmenit ali se bomo prerekali o LOA ali o računalniku. Ker mene samo za računalnik zanima ali tak program obstaja ali ne. In trdim, da za računalnik tak program ne obstaja.
Ars longa,vita brevis.

JerKoJ ::

Za začetek samo vprašanje: ali tvoj program, za preverjanje mojega programa p nad mojim vhodom i, porabi več pomnilnika, kot če bi jaz sam izvedel p nad vhodom i?


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. Torej ce zelimo pognati program p nad vhodom v (velikost = n) rabimo k*n pomnilnika v racunalniku. Pravim, da se da isto simulirati na racunalniku, ki ima 2*k*n+m pomnilnika, kjer je m nekaj malega pomnilnika, ki ga simulator porabi sam zase (in ga je konstantno mnogo neodvisno glede na program p in vhod v). Glede na dokaz s stetjem korakov je jasno, da je zadost tudi le k*n+m pomnilnika kolikor ga potrebujemo za simuliranje programa p. Po k*n*2^n korakih se mora najkasneje simulirani program zakljuciti ali pa se cikla. In po toliko korakih lahko odgovorimo z DA ali pa NE na vprasanje ali se podani program p na vhod v cikla.

Stanj imaš 2^(stevilo bitov pomnilnika v računalniku) * (število stanj procesorja) * (število pixlov na zaslonu) pa še veliko drugih stvari bi lahko dal v ta račun. To koliko je program velik sploh nima zveze s tem. Res pa je, da vsi pogrami ne speminjajo vseh bitov/pixlov..., in jih zato ni potrebno preverjati. Pa zakaj se more ustaviti v določenem številu korakov? Poglej si OS, ki lahko (teoretično) deluje poljubno dolgo, pa se še vseeno ne zacikla.


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.

Je mar važno ali so primerni ali ne? Dejstvo je, da obstajajo, in če hočeš imeti program, ki bo deloval za vse programe, mora delovati tudi za njih.


Torej mi praviš, da ne smem pisat programov, za katere tebi zmanjka pomnilnika? Oz. ti dati dovolj velikih vhodov? Pa ravno take programe hočem, kjer se to zgodi.


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.

Ti trdiš, da obstaja pogram halt(p, i) ki za vsak program in vsak vhod, ki mu ga podaš pove ali se ta program na vhodnih podatkih zacikla ali ne. Pri tem se sam ne zacikla in mu tudi nikoli ne zmanjka pomnilnika. Predpostavimo, da ga imamo. Spet napišemo program trouble. Torej halt(s, s) v vsakem primeru vrne TRUE ali FALSE, to je ena izmed predpostavk. Po tem pa po istem razmišljanju kot je na linku od wikipedie pridemo v protislovje.


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.

Kot kaže se bomo morali zmenit ali se bomo prerekali o LOA ali o računalniku. Ker mene samo za računalnik zanima ali tak program obstaja ali ne. In trdim, da za računalnik tak program ne obstaja.


Deterministicni LOA je ekvivalen model realnega racunalnika. Torej vse kar lahko izracuna LOA lahko izracuna tudi racunalnik in obratno. Se vedno trdim, da obstaja LOA program halt(p,i), ki za vsak program p (ali LOA ali TS) odgovori z DA ali NE na podani vhod i. Kot ze nakazo pa v kolikor testiramo ne-LOA (cisti TS) program potem pridemo do OUT OF MEMORY situacije. Vendar takega programa tudi na nobenem racunalniku ne moremo pognati ne da bi dobili isti odgovor. In tako je odgovor, da se program konca pravilen - konca se z napako.

Eto dokaz je na tebi. Napisi program, ki porabi le koncno mnogo rama (linearno glede na velikost vhoda - O(n)), in se ne konca v k*n*2^n korakih in se hkrati ne cikla. Ali pa program, ki bi povzrocil ciklanje simulatorja, za katerega velja, da ima na voljo O(n) pomnilnika. Ali pa program, ki sam potrebuje le O(n) pomnilnika, simulator pa nujno vec kot O(n) pomnilnika.

Cofko Cof ::

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.


Ok jaz napišem program, ki mu zmanjka pomnilnika pri nekem vhodu(lahko je to tudi program trouble, lahko tudi kak drug program). Potem pa dam tebi ta program in vhod. In tebi ga bo zmanjkalo še prej kot meni ko boš to začel simulirat. Torej do tega, da ga meni zmanjka sploh ne pride. Sicer bi mi ga, vendar ti tega ne moreš preverit, kre se tvoj program že prej obesi. Se mi zdi, da sva z Jetijem zdaj istega mnenja glede tega?

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.


Tu priznaš, da ti zmanjka pomnilnika. In to je v nasprotju s predpostavko. Ni važno je ali je LOA prešibek ali ne. Pač lahko napišeš tak program in želiš, da tudi zanj znaš reči da ali ne. Ker če take programe zavržeš ne moreš reči, da lahko za vsak program rečeš da ali ne. Se tudi v tem strinjamo?

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.

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.


Ok tole priznam, da ni čist skladno z defnicijo ustavljivosti, ker mu moraš na začetku podat vse vhode. Ampak, če bi hotel imet program, ki mi za vsak program pove ali se le ta ustavi ali zacikla bi ga le težko naredil. Ker bi to pomenilo, da bi moral nadzorovat vse udarce metuljev s krili, ljudi, stvari v njihovih glavah, vse atome, ... da bi lahko povedal, če bo prišel kdo in izklopil računalnik. In spet pridemo do tega, da za vse programe ti to ne bo uspelo.
Ars longa,vita brevis.

JerKoJ ::

Ma se zmer ne vem kaj glede rama mutis. Recimo da za k vzamemo 1 - torej ima LOA na voljo tocno tok celic kot lih zasede vhod (vseeno je koliko vzames k, le da je neodvisen od n). 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.

Ce zelis ti programu p podati vhod velikosti 10 MB potem mu bo simulator zagotovil 10MB rama (ali k*10 MB) sam, ga pa potrebuje 20 MB (ali k*20MB). V kolikor toliko rama pri zagonu ni na voljo (predpostavimo, da celoten ram zasede takoj, sam mora non stop preverjati stanja (po 10MB med seboj) potem pac rece - ni dovolj rama, da bi se pognal za dani vhod (in je to neodvisno od programa). V kolikor je rama zadosti, ga bo simulator zasedal le 20 MB (k*20MB) tvoj simulirani program pa bo zacel teci. Cim bo program ves razpolozljivi ram porabil (10 MB ali k*10MB) bo simulator to ugotovil, saj le simulira dodeljevanje pomnilnika programu, in rekel - program p se za vhod v konca - pride do napake out of memory. Nikakor pa ne bo simulatorju zmanjkalo pomnilnika, ce ga je ze na zacetku dost, da se zazene.
Se vedno trdim - taksen simulator se ne obesi in ne zacikla.

Tu priznaš, da ti zmanjka pomnilnika. In to je v nasprotju s predpostavko. Ni važno je ali je LOA prešibek ali ne. Pač lahko napišeš tak program in želiš, da tudi zanj znaš reči da ali ne. Ker če take programe zavržeš ne moreš reči, da lahko za vsak program rečeš da ali ne. Se tudi v tem strinjamo?


Ne se ne strinjamo - za vsak program lahko reces DA ali NE - vendar s predpostavko, da se tak program izvaja na LOA - o tem govorimo. Ce se tak program izvaja na TS potem tega ne mores reci za vsak program - tu se strinjamo. Simuliras lahko vse programa nobenih ni treba zavzt. Rezultat je DA - program se uspesno ali neuspesno izvede na LOA in se ustavi ali pa NE - program se na LOA ne ustavi.

Ampak, če bi hotel imet program, ki mi za vsak program pove ali se le ta ustavi ali zacikla bi ga le težko naredil. Ker bi to pomenilo, da bi moral nadzorovat vse udarce metuljev s krili, ljudi, stvari v njihovih glavah, vse atome, ... da bi lahko povedal, če bo prišel kdo in izklopil računalnik. In spet pridemo do tega, da za vse programe ti to ne bo uspelo.


No to zdej pa mal pade ven iz konteksa. Jest trdim, da je problem ustavljivosti resljiv za vsak program p za vsak vhod v na LOA. Prakticno je stvar neizvedljiva saj bi trajal ogromno casa, da se preveri - amapak ta cas je se vedno koncen. Za razliko od TS, kjer takega programa sploh ne mores narediti.

Cofko Cof ::

Fant lepo se zjasn al ti zmanjka rama al ne, samo nekaj citatov tvojih prejšnjih postov:

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.


Če ga meni zmanjka in ga ti porabiš 2x več kot jaz ga tebi tud zmanjka. Simpl logika?

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


Se pravi ti ga zmanjka?

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


Se pravi, da ti ga ne zmanjka? Kaj pa če ga že na začetku nimaš dovolj, da bi karkol štartov?

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.


1. Povej mi od kod ti pravica, da ima tvoj simulator 2x več rama kot moj računalnik? Kaj pa če jaz rečem, da ga imam jaz 2x več? Konec koncev mi ti, s tem ko mi dodeliš koliko pomnilnika imam na voljo lahko določaš kako se program zaključi. Če mi daš 0 pomnilnika lahko za vsak program rečeš, da se ustavi, ker mu takoj zmanjka pomnilnika. In če to narediš za vsak program na tem svetu lahko ugotoviš, da sploh ni programa, ki se zacikla. Ali, ki bi deloval pravilno.

2. Pozabljaš, da halt izvajaš tudi v trouble, to se pravi na navideznem računalniku, ki si ga ti ustvaru. In tu nimaš dovolj prostora. Pa ne smeš kar rečt, ker jaz nimam dovolj prostora za simulacijo to pomeni, da ga ta program tudi ne bo imel, da bi se izvedel.

3. Poglej, tvoj simulator ima tudi končno pomnilnika, je tako? Recimo, da ga imaš n, kaj pa če ti dam jaz program in pa vhod, ki je dolg 2n. Potem pa takoj pogoriš. Ti zmanjka pomnilnika še preden bi lahko vhod prbral, kar pa ga moraš. Pri tem nimaš izbire.

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.


Tega se še vedno izogibaš.
Ars longa,vita brevis.

JerKoJ ::

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.

To pomeni, da ce na vhodu podam stevilko N potem je velikost rama lahko le k*[ceil(log2(N))+1]+m (toliko bitov rabimo, da stevilko N zapisemo). Faktorja k in m sta lahko poljubeno velika amapak konstantna - torej neodvisna od stevila N. Torej ce recem k=10MB in m=10MB potem ima automat na voljo pri vhodni stevilki 1 20MB pomnilnika pri vhodni stevilki 2^(100000) pa 1000010 MB. To prakticno pomeni Linearna odvisnost velikosti rama.

Ce ga dolocen program porabi vec glede na vhod potem pac ni LOA program -> torej ga ne moremo poganjati za poljuben vhod na LOA avtomatu. Se primerjava LOA in racunalnikov. Ce zelis pac, da LOA programu ne bo zmanjkalo rama mu mores zagotoviti linearno veliko rama glede na vhod. V praksi imas rama konstantno to pa pomeni, da tudi na racunalniku ne mores zagotoviti, da se bo LOA program izvedel za vsak vhod, vendar lahko ram se vedno dokupis in ce ga povecas za 2 lahko vnasas 2x vecje vhode. Obicajno je tega rama veliko vec kot ga za vhod potrebujes - to pa pomeni, da na racunalniku lahko izvajas tudi ne-LOA programe za dolocene (majhne) vhode.

Fant lepo se zjasn al ti zmanjka rama al ne, samo nekaj citatov tvojih prejšnjih postov:


Ti zastopis, da racunalnik simuliras (poglej si vmware) - dolocis mu koliko rama ima program, ki ga simuliras na voljo. Sam simulator seveda lahko zaseda mal vec rama kot ga simulirani program potrebuje. In ce simulirani program zahteve vedno vec rama mu simulator enkrat rece stop - dosegel si mejo, ki sem ti jo postavil - koncal si se z napako. Sam simulator glede na OS ne zahteva vedno vec rama - ampak vsega zasede ze na zacetku. Ce ga na zacetku seveda ni dovolj se simulator sploh ne bo zagnal in OS sporocil - nimam dovolj pomnilnika. Tocno isto dela OS - programom dodeljuje ram dokler je na voljo - ko ga ni vec jim rece NO MORE in se programi sami koncajo in vrnejo napako - OS se seveda ne razsuje. Se enkrat: RAMA lahko zmanjka tvojemu programu ne pa simulatorju !.

1: Simulator je nad programom in zato lahko zasede vec rama. Tvojemu programu, ga lahko dodelim le linearno glede na zahtevani vhod - pri cimer si lahko ti sam zmislis faktorja k in m. Zagotovi moras se, da ima racunalnik, ki poganja simulator vsaj 2x toliko rama, kot ga naj bi najvec porabil program za dani vhod. Ce imas vhod velikosti n bitov ti ne smem dati 0 bitov rama ampak k*n+m bitov na voljo v simulatorju.

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.

3. Pravim, da zavzame koncno mnogo pomnilnika, vendar linearno gleda na velikost vhoda. V kolikor ti zelis podati 2x vecji vhod rabis 2x vec rama, da simulator sploh pozenes za podani vhod.

Tega se še vedno izogibaš.

Glej točko 2.

Cofko Cof ::

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.


Mene predvsem zanima računalnik, in ti ne moreš zagotoviti tvojemu simulatorju dovolj pomnilnika, da bi sprejel vse moje vhode. Ker si vedno lahko zmislim enako velikega kot je tvoj pomnilnik. Ti pa rabiš vsaj 2x tako velikega. In rama imaš vnaprej podano, ne boš ga šel kar dodajat ko boš videl, da ti ga zmanjka. Pa ni na meni, da zagotovim dovolj rama, to je tvoje delo.

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.


No pa si malo poglej kaj si napisal, vsaj enkrat ti halt(t, t) vrne true, in vsaj enkrat pa false. In še vedno trdiš, da tvoj program pravilno deluje? Čeprav nad istim vhodom, daje različne rešitve? Da ne bi o tem, da čisto zunanji halt odgovarja true ali false na podlagi tega koliko rekurzivnih klicev je bilo(kar pa je odvisno od količine pomnilnika).

Kaj več nimam dodat.
Ars longa,vita brevis.

Zgodovina sprememb…

JerKoJ ::

Za poljubne vhode imas omejitev vesolje. Poljubni vhod je lahko le koncno dolg in za tak vhod rabis racunalnik, ki ima tok in tok rama. V kolikor racunalnik nima tok rama vhoda ne more sprejet - simple as that. V kolikor program potrebuje najvec k*n+m rama za vhod velikosti n in poljubnih konstantah k in m potem je tak program LOA in je izracunjiv na LOA avtomatu (tudi raculnalniku) - v kolikor potrebuje vec rama ni vec LOA program in ni izracunljiv na LOA avtomatu. 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.
Za primerjavo: TS ima neskoncno rama ne glede na velikost vhoda - ki pa mora tudi biti omejen ( wiki).

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.

No pa si malo poglej kaj si napisal, vsaj enkrat ti halt(t, t) vrne true, in vsaj enkrat pa false. In še vedno trdiš, da tvoj program pravilno deluje? Čeprav nad istim vhodom, daje različne rešitve? Da ne bi o tem, da čisto zunanji halt odgovarja true ali false na podlagi tega koliko rekurzivnih klicev je bilo(kar pa je odvisno od količine pomnilnika).

Trdim da deluje pravilno, saj ce bi halt(t,t) zagnal na racunalniku z isto kolicino rama kot, ga halt dodeli programu trouble bi se zgodilo isto - trouble bi se zaciklu ali pa se ne bi. Saj simulacija ne dela drugega kot simulira LOA - ce le ima dovolj pomnilnika glede na k,n in m za zagon.

Ponavljam - napisi program, ki:
- porabi le koncno mnogo rama (linearno glede na velikost vhoda - O(n)), in se ne konca v k*n*2^n korakih in se hkrati ne cikla.
- ki bi povzrocil ciklanje simulatorja, za katerega velja, da ima na voljo O(n) pomnilnika.
- sam potrebuje le O(n) pomnilnika, simulator pa nujno vec kot O(n) pomnilnika.

Tvoj program trouble ne ustreza nobeni tocki.

Cofko Cof ::

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.


Moje delo pa je, da pokažem, da tudi če ti tak program uspe napisat na računalnikih ne bo deloval. Ker ne bo imel dovolj pomnilnika. Tak simulator pa ne dela pravilno na računalnikih. 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š? Kot si rekel je omejitev vesolje. Če je končno potem ti jaz za vhod podam kar celo vesolje, pa ti zmanjka pomnilnika. Če pa je neskočno pa lahko izberem poljubno velik vhod za tvoj računalnik(ki more imet fiksno določen pomnilnik).

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.


Torej LOA in računalnik ni čisto isto?

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.


Tvoji zgornji dve trditvi si zopet nasprotujeta. Me ne zanima koliko pomnilnika rabiš, zanima me ali se ustavi ali ne.
Ars longa,vita brevis.

Matevžk ::

Joj, Cofko ;((.

LOA in "računalnik" je z vidika teorije izračunljivosti eno in isto. Razlika je povsem praktične narave: teorija zahteva, da se avtomatu da toliko pomnilnika, kolikor ga za dani vhod potrebuje (seveda izračunljivo in končno količino!). Računalniki v praksi nimajo fleksibilne količine pomnilnika, zato ne moreš poganjati LOA programa na prevelikem vhodu, če ne dodaš več pomnilnika. Torej moraš za večje vhode dodati pomnilnik, vendar še vedno je količina pomnilnika za izvedbo programa na točno določenem vhodu KONČNA (kar za TS ne velja!!!).

In zdej ti hočeš, da ti posimuliramo, če se LOA program izvede na avtomatu A (ki ima a bitov pomnilnika). In mi pravmo, da ni problema, ampak za to rabimo avtomat B (ki je še vedno čisto navaden LOA, le več pomnilnika ima, ker se na njem izvaja drug program (naš simulator, ne tvoj program) -- a količina pomnilnika, ki ga simulator porabi, je KONČNA, prav tako se bo simulator zagotovo končal v končnem času (in mi to vemo, nič ne ugotavljamo, kako je s tem pri simulatorju)).
Ta avtomat B pa mora imeti 2*a+m pomnilnika (kjer je m neko znano končno število).
Torej, ja, za simulacijo rabimo več pomnilnika, vendar je njegova količina predvidljiva, izračunljiva in KONČNA!
lp, Matevžk

Cofko Cof ::

No v glavnem se ne strinjamo v dveh točkah:

1. Pomnilnik
Tudi, če je končno, v praksi ne boš mogel za vse programe in vhode preverit ali se ustavi ali ne. In verjetno zaradit tiste razlike med LOA in računalniki prihaja do nasprotnih mnenj. Kajti LOA pač daš toliko pomnilnika kot ga rabi, je pač teoretični model in te ta pomnilnik ne skrbi preveč(no tud v praksi ga narediš, potem pa ti začne pomnilnik delat probleme). Računalnik pa je nekaj konkretnega in tega pomnilnika mu ne moreš kar tako dat.

2. Program trouble
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š?
Ars longa,vita brevis.

Zgodovina sprememb…

Matevžk ::

PCji niso ravno pravi model za razmišljanje o izračunljivosti. Trenutno smo pač na nekaj giga (rama), čez nekaj let bomo bogvekje. Teoretično je omejitev sama pomnilniška kapaciteta vesolja, vendar tako ali tako ne bi mogel dobiti tako velikega problema za LOA program, da bi toliko pomnilnika porabil ...
lp, Matevžk

JerKoJ ::

OK pa poglejmo, kar sem trdil na zacetku:

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.


Nadaljne se dodajam, da tak program lahko uspesno pozenes na LOA avtomatu, ki mu dodelis ~ 2x vec pomnilnika kot simuliranemu LOA avtomatu - to je se vedno OK, saj imas na vhodu kako p kot v. Torej vse sranje glede fizicnih omejitev racunalnika in kolicine pomnilnika odpadejo. Ce pa se omejimo na racunalnik pa dodajam - program obstaja vendar sprejme le tako velike vhode kolikor imas rama (v ustreznem linearnem razmerju). Happy zdej glede rama? Itak pa glej naslov teme - ustavljivost linearno omejenih avtomatov.

Glede trouble sem ze vse napisu kar je napisat treba: Torej glede na kolicino rama, ki ga namenimo simulaciji pride do odgovora DA - konca se ali NE - se cikla. Ce se malo bolj razmiljam potem je mozno da pride le do : pozenemo halt(t,t) - simulirati se zacne trouble(t) - hoce se pognati halt(t,t) - zmanjka pomnilnika, saj ga zahteva isto kot, ga dobi dodeljen ze prvi halt(t,t) (torej ga je na voljo vsaj pol premalo znotraj simulacije trouble(t)) - simulirani trouble se konca z napako - pognani halt to zazna in tako vedno odgovori DA - program trouble se konca, vendar z napako.

Se vedno cakam na tvoj program. Ker ze cel thread operiras mal cudn - najprej s papirnatimi programi, potem z random stevili, potem z metulji in kaosom, zdej z vesoljem. Napis program ali pa ovrzi predlozeni dokaz o koncno moznih stanjih LOA avtomata.

Cofko Cof ::

PCji niso ravno pravi model za razmišljanje o izračunljivosti. Trenutno smo pač na nekaj giga (rama), čez nekaj let bomo bogvekje. Teoretično je omejitev sama pomnilniška kapaciteta vesolja, vendar tako ali tako ne bi mogel dobiti tako velikega problema za LOA program, da bi toliko pomnilnika porabil ...


Jaz se nisem spraševel o izračunljivosti. Moje vprašanje je bilo ali obstaja računalniški program, ki za vsak program in vhod, ki mu ga podamo pravilno pove, če se ta program zacikla ali ne. Pa kako da nimaš tako velikega problema? 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č :D

Ce se malo bolj razmiljam potem je mozno da pride le do : pozenemo halt(t,t) - simulirati se zacne trouble(t) - hoce se pognati halt(t,t) - zmanjka pomnilnika, saj ga zahteva isto kot, ga dobi dodeljen ze prvi halt(t,t) (torej ga je na voljo vsaj pol premalo znotraj simulacije trouble(t)) - simulirani trouble se konca z napako - pognani halt to zazna in tako vedno odgovori DA - program trouble se konca, vendar z napako.


Saj tole sem ti pa že zgoraj nakazal:
2. Pozabljaš, da halt izvajaš tudi v trouble, to se pravi na navideznem računalniku, ki si ga ti ustvaru. In tu nimaš dovolj prostora. Pa ne smeš kar rečt, ker jaz nimam dovolj prostora za simulacijo to pomeni, da ga ta program tudi ne bo imel, da bi se izvedel.


Sedaj edino nerešeno vprašanje je še tole. Kaj se zgodi, ko v trouble pokličemo halt?
- troublu verjetno ne zmanjka pomnilnika ob klicu, klic funcije z dvema parametroma ne porabi tistega kar ima na voljo. Ker če bi ga, potem to pomeni, da si mi že na začetku dal premalo za izvajanje.
- halt se začne izvajat in mu zmanjka pomnilnika. Torej halt ne deluje pravilno.
- halt ugotovi, da ima premalo pomnilnika. Samo kaj sedaj? Ne sme kar rečt, da tudi troublu zmanjka pomnilnika, ke lahko se že takoj zacikla. Pa tudi nihče ne pravi, da mogoče se mu pa ne bi uspelo izvest in ustavit. Zato nimaš pravega odgovora v tem primeru. Lahko se zacikla, lahko pa ne.

Ce pa se omejimo na racunalnik pa dodajam - program obstaja vendar sprejme le tako velike vhode kolikor imas rama (v ustreznem linearnem razmerju). Happy zdej glede rama? Itak pa glej naslov teme - ustavljivost linearno omejenih avtomatov.


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:
In verjetno zaradit tiste razlike med LOA in računalniki prihaja do nasprotnih mnenj. Kajti LOA pač daš toliko pomnilnika kot ga rabi, je pač teoretični model in te ta pomnilnik ne skrbi preveč(no tud v praksi ga narediš, potem pa ti začne pomnilnik delat probleme). Računalnik pa je nekaj konkretnega in tega pomnilnika mu ne moreš kar tako dat.


Se vedno cakam na tvoj program. Ker ze cel thread operiras mal cudn - najprej s papirnatimi programi, potem z random stevili, potem z metulji in kaosom, zdej z vesoljem. Napis program ali pa ovrzi predlozeni dokaz o koncno moznih stanjih LOA avtomata.


Programa se ne bom spravil pisat.

S papirnatimi programi si začel ti:
- nekdo me simulira s svincnikom na papirju


Pri tem mi ni blo všeč, ker si tudi stroka ni na čistem glede tega, ali je človek sposoben kaj več kot TS ali ne. In v slučaju, da je, potem človek, ki je sposoben nekaj več kot TS, ne sme reševati ustavljivosti le-tega.

Random je bil čist trenutni navdih, pač se mi je zdel, da te zna hudo zmest. In ugani kaj, to je stvar, ki zmede tudi strokovnjake na tem področju. Kot je že jeti napisal:
P.S.: Tisto prej o kvantnem Turingovem stroju... vzemite za vsak slučaj malo z rezervo. Kot je asistent razložil, si trenutno tu stroka še zdaleč ni enotna. Pa še edu link, če koga zanima kaj o tem.


Metulji, kaos in vesolje so pa še kako povezani. Beri wikipedio. Če bi hotel preverit ali se OS ustavi ali ne bi moral upoštevati kar celo vesolje. Pa še ti mogoče ne bi uspelo(odvisno od tega kakšno vlogo igra zavest in inteligenca pri človeku, oz. ali se da ob dovolj velikem in natančnem opazovnaju človeka napovedovati njegova dejanja).
Ars longa,vita brevis.

JerKoJ ::

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č

Ocitno program ni za LOA, saj porabi linearno vec rama kot je vhoda - vhoda je celo 0. Torej lahko porabi je m rama. Ko tega pokuri se ustavi z napako out of memory - seveda N binarnih decimalk stevila Pi zavzama le N bitov torej lahko giga rama izracunamo Pi na 8589934592 binarnih mest natancno - lahko pa stvar damo na disk, ki tudi steje kot pomnilnik in imas se vec mest na voljo. Amapak kot si ze reku decimalk je neskoncno - izracun se nikoli ne konca -> torej stvar ni LOA.

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

Tvoja tocka tri se zacne pravilno - halt ugotovi, da nima dovolj pomnilnika in se neha izvajati - kaj vrne je odvisno od implementacije- lahko true, lahko false, lahko error (kar bi bilo najbolj prav). Kako stavek if v trouble to interpetira je zdej vprasanje - lahko se razsuje (ker ni error handlinga), lahko uposteva true in se posledicno zacikla, lahko pa uposteva false in se konca - v vsakem primeru je odlocitev deterministicna in odvisna od implenetacije. In ce bi trouble(t) pognal direktno na LOA (ali racunalniku z isto rama) bi dobil isti rezultat - vedno.

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:


Lahko preveris za vse vhode le dovolj rama mores zagotovit. V teoriji ga LOA za posamezni vhod pac tok ma, v realnosti ga mores pa tok dodat racunalniku. V kolikor racunalnik nima tok rama potem ne mores govort o LOA. V teoriji torej vhod doloca kolicino rama v praksi pa kolicina rama doloca velikost vhoda ker je bolj prakticno. Racunalniki so racunsko enako mocni kot LOA, dokler imajo zadosti rama za posamezni vhod. Ce tega rama nimajo, potem ne mores govort o LOA. Mora biti pa vhod seveda koncen - ne sme biti neskoncen (tak se za TS ne sme bit).

Ce verjames, da ima LOA za podani vhod lahko le k*n*2^n moznih stanj potem mi prosim povej v katekem novem stanju se LOA nahaja po toliko korakih, da se prej nikoli ni. Kajti deterministicni LOA se glede na stanje v katerem se nahaja vedno odloci enako. V kolikor se neko stanje ponovi imamo torej cikel. Ovzi najprej ta dokaz o ustavljivosti pa ti oprostim pisanje programa.

Cofko Cof ::

Ocitno program ni za LOA, saj porabi linearno vec rama kot je vhoda - vhoda je celo 0. Torej lahko porabi je m rama. Ko tega pokuri se ustavi z napako out of memory - seveda N binarnih decimalk stevila Pi zavzama le N bitov torej lahko giga rama izracunamo Pi na 8589934592 binarnih mest natancno - lahko pa stvar damo na disk, ki tudi steje kot pomnilnik in imas se vec mest na voljo. Amapak kot si ze reku decimalk je neskoncno - izracun se nikoli ne konca -> torej stvar ni LOA.


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.

Tvoja tocka tri se zacne pravilno - halt ugotovi, da nima dovolj pomnilnika in se neha izvajati - kaj vrne je odvisno od implementacije- lahko true, lahko false, lahko error (kar bi bilo najbolj prav). Kako stavek if v trouble to interpetira je zdej vprasanje - lahko se razsuje (ker ni error handlinga), lahko uposteva true in se posledicno zacikla, lahko pa uposteva false in se konca - v vsakem primeru je odlocitev deterministicna in odvisna od implenetacije.


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.

To je vse kar sem hotel, nimam več kaj povedat na to temo:

Ce pa se omejimo na racunalnik pa dodajam - program obstaja vendar sprejme le tako velike vhode kolikor imas rama (v ustreznem linearnem razmerju). Happy zdej glede rama?
Ars longa,vita brevis.

JerKoJ ::

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.

Ce pa stvar sestavis tako potem pa seveda ni problema - al kje ga ti vidis ? Zelim izracunati Pi na 10 mest - eto ti ga v koncnem casu.
Zopet mal zasel okrog glavne teme.

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.


Lej se enkrat - trouble(t) na TS pride v protislovje na LOA pa v vsakem primeru porabi vec rama kot ga ima glede na omejitve LOA na voljo - zato se ne izvaja v nedogled trouble(t) - halt(t,t) - trouble(t) - .... ampak se nekje (mozna da ze pri prvem halt(t,t) ce je stvar tako nastimana) to ciklanje konca in se zacne vracat - vrne izmenicno true ali false (edin za prvi prmer z napako rama se je treba zment amapak stvar na nic ne vpliva) pac pravilno, ker je tako trouble sestavljena - na tocno dolocen vhod (t) ce pri podani kolicini rama vcasih zacikla - vcasih pa ne. Ce pa predpostavimo, da se ze prvi halt sploh ne pozene potem je pa stvar implenetacije trouble ali se trouble(t) na pomilnik, glede na LOA, ustavi ali ne - in to situacijo opisani halt(p,v) za vhod (t,t) in pripadajoco kolico rama cist lepo zazna.

Zdej mi pa ti povej kaj naj vrne trouble(t) na omejenem ramu - ali pa jo implenetiraj - sam prilagam prevdokodo halt(p,i), da bos lahko s cim opereru:

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
}


Eto za to prevdokodo napisi trouble, ki vodi v protislovje ali pa eno vrsto izmed prej omenjenih programov.

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


Halt(p,i) nikoli za simulirani program ne odgovori error na vprasanje ali se p na vhodu i ustavi - cim mu zagotovis dovolj rama za izvajanje simulacije - glej zgornjo kodo. Ce ga seveda pozenes na premalo rama bo pa rekel - sorry ne morem ti povedat, ker ne laufam na LOA in imam posledicno premalo rama.

Zgodovina sprememb…

  • spremenil: JerKoJ ()

Cofko Cof ::

Ce pa stvar sestavis tako potem pa seveda ni problema - al kje ga ti vidis ? Zelim izracunati Pi na 10 mest - eto ti ga v koncnem casu.

Nisem zašel s teme, samo Matevžku odgovarjam:
Teoretično je omejitev sama pomnilniška kapaciteta vesolja, vendar tako ali tako ne bi mogel dobiti tako velikega problema za LOA program, da bi toliko pomnilnika porabil ...

Ta moj program za pi lahko porabi celo pomnilniško kapaciteto vesolja(če je vesolje končno, če pa je neskončno pa je tudi ne sme, ker sicer bi imel na voljo neskočno pomnilnika in bi bil v bistvu TS). On trdi, da takega programa ni. Pa tu sploh nihče ne dvomi ali se program ustavi ali ne,važno je samo da porabi ves pomnilnik vesolja(v primeru končnosti). Na čase se mi zdi, da sploh točno ne prebereš za kaj se gre(res pa je, da to nima veze z naslovom teme, ampak če je on nekaj napisal s čimer se ne strinjam, bom to komentiral).

Ce ga seveda pozenes na premalo rama bo pa rekel - sorry ne morem ti povedat, ker ne laufam na LOA in imam posledicno premalo rama.


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 :D Psevdokoda za trouble pa ostane čisto ista. Če reče tvoj halt true ali false pride v protislovje, v tem se strinjava? Če pa reče error pa se moj trouble zacikla(ker halt(t,t) != false in se izvede else, kjer pa se zacikla). Zunajni halt reče, da se zaciklam, notranji pa, da je bil error. Vrneš mi dva različna rezultata na istih vhodnih podatkih. Se pravi halt ne deluje pravilno.
Ars longa,vita brevis.

Zgodovina sprememb…

JerKoJ ::

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.


No pogovarjamo se o LOA in moja tocka 1 se vedno drzi (se da napisat program - psevdokodo imas prej) . V vseh primerih ti lahko povem v kolikor moj LOA program (halt(p,i)) pozenes na LOA avtomatu ali se program p na vhodu i ustavi ali ne. Kot sem ti ze povedu ti mal mesas teorijo in prakso. V teoriji velikost vhoda doloca velikost rama pa naj bo ta vhod se tako velik le dokler je koncen je vazno. In teorija LOA doloca tudi, da je tega rama lahko le k*n+m torej linearno odvisno od velikosti vhoda n. V praksi pa imas rama koncno mnogo in torej lahko stvar pozenes le za dovolj majhne vhode - dokler velja k*n+m<#RAM. Se enkrat - racunalnik je ekvivalenten LOA dokler ima rama primerno vhodu. Ne mores neko stvar na LOA izracunat na racunalniku pa ne ce imas za podani vhod dovolj rama (velja tudi obratno - racunalnik ne more izracunati nic vec kot LOA).

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

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.

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

NE se ne strinjava - halt(p,i) rece true ali false za program p, ki se za vhod i izvaja na LOA avtomatu. In ce se program p konca rece true, ce se pa cikla rece false. Ce pa za isti program vcasih rece true vcasih pa false za isti vhod bi pa bil problem, samo do tega ne pride. Se strinjam, da sem se zaplezu prej z vecimi ponovitvami trouble(t), ..., halt(t,t), ... amapak zdej ze neki casa trdim, da se bo ze prvi simulirani halt(t,t) razsu - ker bo imel premalo rama za zagon naslednje simulacije. Ker se tvoj trouble ne error zacikla je output programa halt(t,t) true.

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

Vhodni podatki so ze isti samo prvic stvar zazenes na LOA, drugic na ne, ker ugotovi, da ima premalo pomnilnika glede na zahtevan vhod. Ker se stvar ne pozene vec na LOA pac program ne deluje. Simple a ni? Halt seveda deluje pravilno.

Cas bi ze bil, da nehas tezit s tole funkcijo trouble, ker mislm, da smo fertig. Najdi kaksen drug program, enega izmed treh nastetih vrst. Torej takega ki ima LOA pomnilnika in se po maksimalno moznih korakih nahaja v stanju kjer prej se nikoli ni bil. Takega, ki povzroci cikel v moji prevdokodi. Ali takega ki povzroci, da halt(p,i) porablja vedno vec rama.
Mislim, da drugega in tretjega ne mores napisat glede na podano prevdokodo. Drugega ne zato, ker je edina zanka v programu for in ta je lepo koncna. Tretjega pa zato, ker ves ram, ki ga za simulacijo potrebje zahteva na zacetku. Ostane ti torej edino se prvi tip programa. Pa da vidimo, kako uspes ti pripraviti program do tega, da se pri M=k*n*2^n moznih stanjih v M+1 korakih nikoli ne znajde v istem stanju. Ali se slucajno tudi o stevilu moznih stanj ne strinjava ?

Prosim tudi da nehas o ramu in fizicni omejitvi vesolja, ker se pogovarjamo o teoreticnem LOA in ne prakticni uporabi. Za sledjo se ve, da je skoraj brez pomena, saj se lahko izvaja zelo zelo zelo dolgo (a koncno) in zaradi tega pac takega halt(p,i) programa ni na trziscu.

Matevžk ::

Cofko, nisem trdil, da takega programa ni, ampak da ga boš težko dobil, vsaj praktičnega in koristnega. No, dobil si ga, zdaj mi samo še povej, kako boš celo vesolje ničel nafilal za vhodne podatke :D.
Sicer je pa takole ... program Trouble je bolj program za turingov stroj, saj pademo v neskončno rekurzijo, kar pomeni, da bomo pokurili ves pomnilnik (pri LOA programih pa mora biti količina pomnilnika, ki ga potrebujemo, vnaprej znana). Kot smo že omenili, LOA lahko simulirajo programe, ki so pisani za TS, vendar zaradi omejitve pomnilnika ne vseh programov in ne na vseh vhodih ... Trouble je primer programa, ki ga ne moreš uspešno simulirati, razen če predvidiš še eno dodatno izhodno stanje ("napaka: zmanjkalo je pomnilnika"). To novo stanje je treba definirat (in obnašanje kode, ko na to stanje naletijo) in to je JerKoJ izredno hitro in na prvi pogled tudi zelo kvalitetno (če se tebi ne zdi, pa ovrži) storil.
lp, Matevžk

Cofko Cof ::

Jaz nič ne mešam teorije in prakse, samo pravim, da ti dve stvari nista isto. Mene samo praksa zanima, in v tem smo že prišli do rešitve. Pač ne gre. V teoriji pa kar naj obstaja tak program, meni tak program v praksi nič ne koristi, ker ga ne morem uporabljat.

Kot smo ugotovili: računalnik ni LOA, če nima dovolj rama, in potemtakem trditve(ob predpostavki, da mu zmanjka rama), ki veljajo za LOA zanj ne veljajo.

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.


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š.
Vhodni podatki so ze isti samo prvic stvar zazenes na LOA, drugic na ne, ker ugotovi, da ima premalo pomnilnika glede na zahtevan vhod.


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.

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.
Ars longa,vita brevis.

Zgodovina sprememb…

Cofko Cof ::

No, dobil si ga, zdaj mi samo še povej, kako boš celo vesolje ničel nafilal za vhodne podatke


Kot is napisal:

Teoretično je omejitev sama pomnilniška kapaciteta vesolja,


Najprej ti naredi računalnik, ki ima tako kapapciteto, potem pa ti jaz nafilam vse kot vhodni podatek. Kar direkt v ram ti zapišem same ničle(pa neglede na to kako boš ram sestavil na podlagi vesolja, v vsakem primeru mora nekako sprejeti ničle in enice).

No pa bo spet JerKoJ napisal, da sem šel v off-topic.

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.
Ars longa,vita brevis.

Zgodovina sprememb…

JerKoJ ::

Samo se tole povej ce se strinjas. V kolikor se potem se tema lahko zaklene.

Da se napisati (obstaja) program halt(p,i), ki tece na LOA in zna za vsak program p in njegov vhod ugotoviti ali se ustavi ali zacikla.

Tekom teme smo ugotovili da:
- halt(p,i) ne obstaja za TS
- da poganjanje ne LOA programov na LOA lahko pri dolocenih vhodih (ali pa vedno) vodi v OUT OF MEMORY situacijo (neskoncna rekurzija v trouble, izracun pi-ja v neskoncni zanki, ...)
- so racunalniki enako zmogljivi kot LOA v kolikor jim damo na voljo dovolj rama (glede na zeljeni 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.

Pravim, da ga lahko napisemo tudi v realnosti, lahko ga celo pozenemo na posameznih programnih in vhodih. Sigurno je to ze kdo naredil. To, da je program v praksi neuporaben se pa vsi strinjamo - prevec casa rabis - saj imas casovno zahtevnost O(2^n) glede na zeljeni vhod.

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š.

Parametra k in m doloca program sam in sta torej lastnosti programa, ki ju lahko doloci programer. Kodo lahko seveda ustrezno spremenimo v:
size_ram=p.k*n+p.m; 

V kolikor vrednosti k in m nista neodvisni od velikosti vhoda seveda ne gre LOA program.
Recimo za navadni sort tabele je k=1, ker ne potrebujes nobenega bufferja v velikosti vhoda in pa m=4 (zunanji stevec zanke i, notranji stevec zanke j, index min elementa min_el, in se temp vsebina tabele pri koncnem swapu (temp=a[i], a[i]=a[min_el], a[min_el]=temp)).
Za psevdo halt(p,i) je k=2 in m=const (toliko kolikor rabimo za spremljanje registrov vm in nekaj pomoznih spemenljivk).

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.


Tvoj program doloca parametra k in m in toliko, ti ga simulator dodeli v kolikor je na voljo, ce ga ni niti ne nadaljuje amapak vrne error - ne morem pognati simulacije. Seveda zelis ti poganjati simulacijo znotraj simulacije znotraj .... vse lepo in prav samo ti bo zmajkalo rama (mogoce ze cisto na zacetku).

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.


In imas ga - vrne false (v prejsnjem postu je napaka :D) v tvoji trenutno opisani implementaciji. In ce bi za trouble zgradil LOA in bi na vhod dal t (kodo trouble) bi se stroj zaciklal in se nebi nikoli koncal.

Cofko Cof ::

Smo se tole povej ce se strinjas. V kolikor se potem se tema lahko zaklene.

Da se napisati (obstaja) program halt(p,i), ki tece na LOA in zna za vsak program p in njegov vhod ugotoviti ali se ustavi ali zacikla.

Tu bi dopolnil: za vsak program p, ki je LOA. Ne vem pa zakaj bi šla tema v zaklep, mogoče bo imel še kdo kaj za dodat oz. imel kakšno vprašanje.

Tekom teme smo ugotovili da:
- halt(p,i) ne obstaja za TS
- da poganjanje ne LOA programov na LOA lahko pri dolocenih vhodih (ali pa vedno) vodi v OUT OF MEMORY situacijo (neskoncna rekurzija v trouble, izracun pi-ja v neskoncni zanki, ...)
- so racunalniki enako zmogljivi kot LOA v kolikor jim damo na voljo dovolj rama (glede na zeljeni vhod)


Z zgornjimi tremi trditvami se strinjam.

Pravim, da ga lahko napisemo tudi v realnosti, lahko ga celo pozenemo na posameznih programnih in vhodih. Sigurno je to ze kdo naredil. To, da je program v praksi neuporaben se pa vsi strinjamo - prevec casa rabis - saj imas casovno zahtevnost O(2^n) glede na zeljeni vhod.


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š.

Parametra k in m doloca program sam in sta torej lastnosti programa, ki ju lahko doloci programer.


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.
Ars longa,vita brevis.

Zgodovina sprememb…

Matevžk ::

Cofko, če program vnaprej ne ve, koliko pomnilnika bo porabil, ni LOA!
lp, Matevžk

Cofko Cof ::

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

JerKoJ ::

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

Ni treba, da je LOA program - ker ta program simuliramo na LOA bo simulator ugotovil, da simuliranemu programu zmanjka spomina, ki ga program glede na LOA princip zahteva (k in m). Lahko simuliramo tudi neLOA program, ki se bo uspesno zakljucil za majhne vhode. Npr: Program za izracun vrednosti Hilbertove matrike ( Mathworld) dobi na vhodu le zeljeno velikost matrike N (logN bitov). Output pa zahteva N*N*logN bitov in torej stvar ni LOA, saj tukaj velja k=N*N kar pa ni neodvisno od vhoda, vendar ce recemo k=10^6 potem lahko za vse vhodne N<10^3 izracunamo celotno matriko.

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š.

Pocel bo tocno tisto kar hoces - ugotovil bo ali se podani program p na vhodu i ustavi ali ne, ce tece na LOA. V kolikor se ustavi vrne true, ce se cikla v neskoncnost vrne false. To da imas koncno mnogo pomnilnika je pa lastnost LOA po definiciji in ga nikakor ne mores imeti neskoncno - torej je stanje ko ti zmanjka pomnilnika cisto legalno in samo pomeni, da vhodni program p ni mogoce pognati na LOA (je TS program).

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.


Ni ti treba izvajati programa. Za vsak LOA program se da k in m dolociti iz same kode, v kolikor program ni LOA pa velja, da sta parametra odvisna od vhoda in torej nikakor ne mores dolociti ustreznih k in m . Recimo program iskanje perfektnih lihih števil je neLOA, ker ima vhod 0 porabi pa neskoncno pomnilnika (predvidevamo) in cetudi dolocis m=1 Giga (k nima veze, ker je n=0) bo prislo scasoma do pomankanja pomnilnika. Upam, da se strinjas, da ce so spomninske potrebe linearno odvisne od vhoda, se da parametra k in m dolociti iz kode. V kolikor ni tako napisi prevdokodo LOA programa iz katere ne znam ugotoviti vrednsoti parametra k in m.

Cofko Cof ::

Za LOA programe se že čisto strinjamo.

Spet si nasprotuješ:
Ni treba, da je LOA program - ker ta program simuliramo na LOA bo simulator ugotovil, da simuliranemu programu zmanjka spomina, ki ga program glede na LOA princip zahteva (k in m).

Tu trdiš, da za neLOA program poznaš k in m in se na podlagi njiju lahko odločiš, da mu zmanjka pomnilnika. Malo nižje pa trdiš, da k in m ne moreš določit:
Za vsak LOA program se da k in m dolociti iz same kode, v kolikor program ni LOA pa velja, da sta parametra odvisna od vhoda in torej nikakor ne mores dolociti ustreznih k in m .


To da imas koncno mnogo pomnilnika je pa lastnost LOA po definiciji in ga nikakor ne mores imeti neskoncno - torej je stanje ko ti zmanjka pomnilnika cisto legalno in samo pomeni, da vhodni program p ni mogoce pognati na LOA (je TS program).

Tvoj halt mi vrže error v takem primeru(tisti najbolj notranji). In to ni true ali false.

Upam, da se strinjas, da ce so spomninske potrebe linearno odvisne od vhoda, se da parametra k in m dolociti iz kode. V kolikor ni tako napisi prevdokodo LOA programa iz katere ne znam ugotoviti vrednsoti parametra k in m.


Se strinjam, samo drugi stavek me spet moti iz razlogov, ki sem ti jih že prej napisal: ne smeš ti ugotavljati, temveč moraš imeti program, ki to ugotavlja.
Ars longa,vita brevis.

Matevžk ::

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

TS program ima neskončno število stanj. (Ima neskončen pomnilnik, le vsaka posamezna pomnilniška celica ima končno število stanj.)
Zato tudi TS lahko izračuna vse, kar se izračunati da ...
lp, Matevžk

Cofko Cof ::

TS program ima neskončno število stanj. (Ima neskončen pomnilnik, le vsaka posamezna pomnilniška celica ima končno število stanj.)


Svetujem, da si tole prebereš, A definition of Turing machines. Še posebej tale del:
A Turing machine is a kind of state machine. At any time the machine is in any one of a finite number of states. Instructions for a Turing machine consist in specified conditions under which the machine will transition between one state and another.
Ars longa,vita brevis.

Matevžk ::

Mora iti za napako.
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.

Torej, neskončen papir, le v vsaki celici je končno število možnih stanj.
vir: Wikipedia.
lp, Matevžk

Matevžk ::

Aja, ne, ni napaka, samo ti si narobe razumel. Stroj ima tudi svoje stanje (ki je končno), recimo shranjeno v nekem registru, ampak hkrati moraš za stanje šteti tudi vsebino celotnega (neskončnega!) pomnilniškega traku (saj ta vendar vpliva na delovanje stroja).
lp, Matevžk
1
2
»


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

IBM predstavil prvi čip, zasnovan po zgledu človeških možganov (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
9613221 (9608) Thomas
»

Thomasov problem (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
1318152 (3969) Pixy222
»

Kurzweil in kako narediti možgane (strani: 1 2 3 4 )

Oddelek: Znanost in tehnologija
16818922 (16856) Thomas
»

Turing train terminal

Oddelek: Novice / --Nerazporejeno--
473339 (2538) 64202
»

simulacija procesorja

Oddelek: Programiranje
12924 (723) Zvonko

Več podobnih tem