Zenonova mašina

U matematici i računarstvu, Zenonova mašina (skraćeno ZM, ili ubrzana Tjuringova mšaina) je hipotetički računski model u vezi sa Tjuringovom mašinom, koji omogućava izvršavanje prebrojivo beskonačno algoritamskih koraka u konačnom vremenu. Ovakve mašine se isključuju iz razmatranja u većini računskih modela.

Formalnije, Zenonova mašina je Tjuringova mašina kojoj je potrebno 2^-n jedinica vremena za izvršavanje njenog n-tog koraka; tako se prvi korak izvršava za 0,5 jedinica vremena, drugi za 0,25, treći za 0,125 i tako dalje, pa je nakon jedne jedinice vremena izvršen beskonačan broj koraka.

Koncept Zenonove mašine je prvi razmatrao Herman Vajl 1927; ime je dobila po grčkom filozofu Zenonu iz Eleje^[1]. Zenonova mašina igra ključnu ulogu u nekim teorijama. Teorija omega tačke koju je razvio Frenk Dž. Tipler, na primer, može da bude ispravna samo ako su Zenonove mašine moguće.

Zenonova mašina i izračunljivost[uredi | uredi izvor]

Zenonova mašina omogućava izračunavanje nekih funkcija koje nisu Tjuring izračunljive. Na primer, halting problem za Tjuringove mašine lako može da se reši na Zenonovoj mašini (korišćenjem algoritma prikazanog sledećim pseudokodom):

почетак програма
  испиши 0 на првој позицији излазне траке;
  почетак петље
    симулирај 1 наредни корак за дату Тјурингову машину и дати улаз;
    ако се Тјурингова машина зауставила, испиши 1 на првој позицији излазне траке и изађи из петље;
  крај петље
крај програма

Ovakvo računanje je izvan granica Tjuringovog ograničenja i naziva se hiperizračunavanjem. Ovo je primer superzadatka.

Treba imati u vidu da halting problem za Zenonovu mašinu nije rešiv na Zenonovoj mašini (Potgieter, 2006).

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ Zenon iz Eleje je bio Parmenidov učenik, koji je smišljao logičke paradokse, aporije, kojima je pokušavao da dokaže ideju svog učitelja o tome kako ne postoji kretanje (kao ni mnoštvo, već postoji samo jedno neprolazno i jedinstveno biće). Poznati primer Zenonovog dokaza protiv kretanja (po kome je Zenonova mašina i dobila ime) je da ako neko pokušava da pređe iz jedne u drugu tačku, on mora prvo da pređe polovinu puta, pa zatim polovinu polovine, pa polovinu polovine i tako redom, i nikada neće stići u ciljnu tačku.

Literatura[uredi | uredi izvor]

Potgieter, Petrus H. (2006). „Zeno machines and hypercomputation”. Theoretical Computer Science. 358: 23—33. S2CID 6749770. arXiv:cs/0412022 . doi:10.1016/j.tcs.2005.11.040.

[1] Zenon iz Eleje je bio Parmenidov učenik, koji je smišljao logičke paradokse, aporije, kojima je pokušavao da dokaže ideju svog učitelja o tome kako ne postoji kretanje (kao ni mnoštvo, već postoji samo jedno neprolazno i jedinstveno biće). Poznati primer Zenonovog dokaza protiv kretanja (po kome je Zenonova mašina i dobila ime) je da ako neko pokušava da pređe iz jedne u drugu tačku, on mora prvo da pređe polovinu puta, pa zatim polovinu polovine, pa polovinu polovine i tako redom, i nikada neće stići u ciljnu tačku.

[1]