|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
To the definition of algorithmsстатья
- Авторы: Uspensky V.A., Kolmogorov A.N.
- Сборник: Selected Works of A. N. Kolmogorov. Vol. III. Information Theory and the Theory of Algorithms
- Редактор: Ширяев Альберт Николаевич
- Серия: Math. Appl. (Soviet Ser.)
- Том: 27
- Глава в коллективной монографии
- Год издания: 1993
- Издательство: Kluwer Academic Pubishers
- Местоположение издательства: Dordrecht, Netherlands
- Первая страница: 62
- Последняя страница: 85
- DOI: 10.1007/978-94-017-2973-4_6
- Аннотация: This article, except for unimportant style editing, was written when the authors, trying to understand the meaning of the notion of “computable function” and “algorithms”, tried to find a new approach to various versions of definitions found in the literature and finally to convince themselves that there is no possibility to widen the content of the notion of “computable function” itself. Thus the result turned out to be negative. It is not without hesitation that the authors publish this description of their search, since from the point of view of the subject matter it gives nothing new as compared to simpler definitions. However, it appears that the approach to the subject that we developed here corresponds to the line of thought of many mathematicians whom the publication of our article will possibly save from going through the same steps of hesitation and thought. Let us also note that we also discussed a version of the definitions in which, instead of a passive unbounded volume of memory in the computer, it is possible to work with an unbounded amount of “active regions” working in parallel, each of which has a bounded complexity of structure. Naturally nothing new appeared in this direction, except partially recursive functions.
- Добавил в систему: Успенский Владимир Андреевич