Зенонова машина

У математици и рачунарству, Зенонова машина (скраћено ЗМ, или убрзана Тјурингова мшаина) је хипотетички рачунски модел у вези са Тјуринговом машином, који омогућава извршавање пребројиво бесконачно алгоритамских корака у коначном времену. Овакве машине се искључују из разматрања у већини рачунских модела.

Формалније, Зенонова машина је Тјурингова машина којој је потребно 2^-n јединица времена за извршавање њеног n-тог корака; тако се први корак извршава за 0,5 јединица времена, други за 0,25, трећи за 0,125 и тако даље, па је након једне јединице времена извршен бесконачан број корака.

Концепт Зенонове машине је први разматрао Херман Вајл 1927; име је добила по грчком филозофу Зенону из Елеје^[1]. Зенонова машина игра кључну улогу у неким теоријама. Теорија омега тачке коју је развио Френк Џ. Типлер, на пример, може да буде исправна само ако су Зенонове машине могуће.

Зенонова машина и израчунљивост[уреди | уреди извор]

Зенонова машина омогућава израчунавање неких функција које нису Тјуринг израчунљиве. На пример, халтинг проблем за Тјурингове машине лако може да се реши на Зеноновој машини (коришћењем алгоритма приказаног следећим псеудокодом):

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

Овакво рачунање је изван граница Тјуринговог ограничења и назива се хиперизрачунавањем. Ово је пример суперзадатка.

Треба имати у виду да халтинг проблем за Зенонову машину није решив на Зеноновој машини (Potgieter, 2006).

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

^ Зенон из Елеје је био Парменидов ученик, који је смишљао логичке парадоксе, апорије, којима је покушавао да докаже идеју свог учитеља о томе како не постоји кретање (као ни мноштво, већ постоји само једно непролазно и јединствено биће). Познати пример Зеноновог доказа против кретања (по коме је Зенонова машина и добила име) је да ако неко покушава да пређе из једне у другу тачку, он мора прво да пређе половину пута, па затим половину половине, па половину половине и тако редом, и никада неће стићи у циљну тачку.

Литература[уреди | уреди извор]

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] Зенон из Елеје је био Парменидов ученик, који је смишљао логичке парадоксе, апорије, којима је покушавао да докаже идеју свог учитеља о томе како не постоји кретање (као ни мноштво, већ постоји само једно непролазно и јединствено биће). Познати пример Зеноновог доказа против кретања (по коме је Зенонова машина и добила име) је да ако неко покушава да пређе из једне у другу тачку, он мора прво да пређе половину пута, па затим половину половине, па половину половине и тако редом, и никада неће стићи у циљну тачку.

[1]