Zenonov stroj

U matematici i računarstvu, Zenonovi strojevi (skraćeno kao ZS, također zvan i ubrzani Turingov stroj) su računski modeli povezani s 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

Ako 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

• Zenonovi paradoksi

Izvori

• Petrus H. Potgieter, Zeno machines and hypercomputation, 2004, http://arxiv.org/abs/cs/0412022