engleski

Some Things Algortihms Cannot Do

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.

behavioral theory of algorithms ; indistinguishability

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