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

From Wikipedia, the free encyclopedia

Remove ads

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

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

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

Remove ads

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

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

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

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

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

Remove ads

Види још

Референце

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads