| Abstrakt: | V posledných rokoch sa na scéne teoretickej informatiky objavili viaceré výpočtové modely, ktorých výpočtová sila prekonáva silu Turingových strojov. Tieto modely nesú spoločný anglický názov Hypermachines alebo Super Turing machines. V úvode práce stručne predstavíme niektoré takéto modely, pokúsime sa ich voľne porovnať a poukázať na rozdiely ako aj spoločné črty. V ďaľšej časti sa zameriame na nekonečne dlhé výpočty. Predstavíme vlastný model, ktorý nám umožní ich podrobné skúmanie. Náš model sa skladá z časti realizujúcej nekonečný výpočet a z časti spracuvajúcej výsledok tohto výpočtu. V práci skúmame vplyv veľkosti informácie získanej nekonečným výpočtom na silu nášho modelu. Tiež sa zapodievame otázkou vplyvu zložitosti výstupov nekonečného výpočtu na výpočtovú silu modelu. Ukážeme, že nami zadefinované stroje (resp. jazyky nimi určené) s vyššie spomenutými obmedzeniami (obmedzenia veľkosti, alebo zložitosti informácie získanej nekonečným výpočtom) tvoria hierarchiu, ktorá je vnorená do stupňa Sigma_3 aritmetickej hierarchie. Ukážeme, že najspodnejšie poschodie tejto novovzniknutej hierarchie je totožné s triedou Sigma_2 a že štruktúra horných piatich poschodí pripomína Chomského hierarchiu.
|
|---|