WikiSysop: Bot: Automatski unos stranica

2021-08-20T04:32:49Z

Bot: Automatski unos stranica

Nova stranica

U [[matematika|matematici]] i [[računarstvo|računarstvu]], '''Zenonovi strojevi''' (skraćeno kao '''ZS''', također zvan i '''ubrzani Turingov stroj''') su računski modeli povezani sa [[Turingov stroj|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 [[Zenonov stroj#Nemogućnost ostvarenja Zenonovih strojeva|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 [[aktorski model|aktorskom modelu]] računanja.

== Porijeklo Zenonovih strojeva ==
O ideji Zenonovih strojeva je prvi raspravljao [[Hermann Weyl]] [[1927.]] Imenovani su po starogrčkom filozofu [[Zenon iz Eleje|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 [[pseudokod]]om:

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 [[konjektura o prostim brojevima blizancima|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 [[proročki stroj|proroka]] za problem koji želimo riješiti.

== Vidjeti također ==
* [[Zenon iz Eleje#Zenonovi paradoksi|Zenonovi paradoksi]]

== Izvori ==

* Petrus H. Potgieter, ''Zeno machines and hypercomputation'', 2004, http://arxiv.org/abs/cs/0412022
[[Kategorija:Računski modeli]]

Zenonov stroj - Povijest promjena

WikiSysop: Bot: Automatski unos stranica