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

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

Формалније, Зенонова машина је Тјурингова машина којој је потребно 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]