U matematici i računarstvu, Zenonovi strojevi (skraćeno kao ZS, također zvan i ubrzani Turingov stroj) su računski modeli povezani sa Turingovim strojevima koji dozvoljavaju obavljanje prebrojivo beskonačno mnogo algoritamskih koraka u konačnom vremenu. Ovi strojevi su također isključeni u istom računskom modelu. (pogledati Nemogućnost ostvarenja Zenonovih strojeva dolje.)
Formalnije, Zenonov stroj je Turingov stroj koji zahtijeva 2-n vremenskih jedinica za obavljanje n-tog koraka. Stoga prvi korak zahtijeva 0.5 jedinica vremena, drugi korak 0.25 jedinica, treći korak 0.125 i tako dalje, iz čega slijedi da će nakon jedne vremenske jedinice trebati biti obavljeno beskonačno mnogo koraka.
Nemogućnost ostvarenja Zenonovih strojeva
Zenonove strojeve isključuje zakon diskretnosti u aktorskom modelu računanja.
Porijeklo Zenonovih strojeva
O ideji Zenonovih strojeva je prvi raspravljao Hermann Weyl 1927. Imenovani su po starogrčkom filozofu Zenonu.
Zenonovi strojevi i izračunljivost
Zenonovi strojevi dozvoljavaju izračun nekih funkcija koje nisu Turing-izračunljive. Na primjer, problem zaustavljanja za Turingove strojeve Zenonov stroj može lako riješiti, što je prikazano sljedećim pseudokodom:
započni program
zapiši 0 na prvu poziciju izlazne trake;
postavi i = 1;
započni petlju
simuliraj prvih i koraka danog Turingovog stroja za dani ulaz;
ako se Turingov stroj zaustavio, tada zapiši 1 na prvu poziciju izlazne trake;
i = i + 1;
završi petlju
završi program
(Međutim, problem zaustavljanja za Zenonove strojeve se ne može riješiti Zenonovim strojem).
Nažalost, naivan pristup Zenonovim strojevima u beskonačnim izračunavanjima vodi ka problemima. Na primjer, za razliku od Turingovog stroja, izlaz Zenonovog stroja nakon njegova završavanja računanja (tj. nakon jedne vremenske jedinice) ne mora biti u drugačijem stanju. Ovo se na primjer može dogoditi ako stroj nastavi alternirajuće zapisivati različite izlaze. Neke od ostalih komplikacija uključuju nedefinirana unutarnja stanja stroja, glave za pisanje koje "otpišu u beskonačnost" i sl.
Sljedeći algoritam predstavljen u pseudokodu, koji pokušava algoritamski odlučiti istinitost konjekture o prostim brojevima blizancima, zorno to predočava:
započni program
postavi i = 3;
započni petlju
zapiši 0 na prvu poziciju izlazne trake;
ako su i i i + 2 prosti brojevi, tada zapiši 1 na prvu poziciju izlazne trake;
i = i + 2
završi petlju
završi program
Ukoliko konjektura o prostim brojevima blizancima nije istinita, izlaz će ovog Zenonovog stroja biti 0. Inače, stroj će nastaviti alternirajuće zapisivati jedinice i nule, ad infinitum, uzrokujući nedefinirano završno stanje po isteku jedne jedinice vremena izvršavanja.
Možda se na prvi pogled čini primamljiva ideja o uvođenju mehanizma koji otklanja ove abnormalnosti (smrzavanjem izlaza stroja, pomicanjem glave za pisanje do konačne pozicije i postavljanjem unutarnje zastavice) - međutim, to će u biti samo uvesti proroka za problem koji želimo riješiti.
Vidjeti također
Izvori
- Petrus H. Potgieter, Zeno machines and hypercomputation, 2004, http://arxiv.org/abs/cs/0412022