Naslov
Some Things Algortihms Cannot Do

Autori
Rosenzweig, Dean ; Runje, Davor

Vrsta, podvrsta
Ostale vrste radova, rukopis

Godina
2005

Ključne riječi
behavioral theory of algorithms ; indistinguishability

Sažetak
A new, `behavioral' theory of algorithms, intending to capture algorithms at their intended abstraction level, has been developed in this century in a series of papers by Y. Gurevich, A. Blass and others, motivated initially by the goal of establishing the ASM thesis. A viable theory of algorithms must have its limitative results, algorithms, however abstract, cannot do just anything. We establish some nonclassical limitative results for the behavioral theory: \begin{; ; ; ; itemize}; ; ; ; \item algorithms cannot distinguish some distinct states ; \item algorithms cannot reach some existing states ; \item algorithms cannot access some existing objects. \end{; ; ; ; itemize}; ; ; ; The algorithms studied are interactive, querying an environment, small--step, operating over different background classes. Since our primary motivation is abstract analysis of cryptographic algorithms, our examples come from this field -- we believe however that the potential application field is much broader.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

Napomena
Rad je preliminarno objavljen kao Microsoft Research
Technical Report 2005-52

POVEZANOST RADA