Аннотация:
Построен предикат, распознаваемый некоторым алгорифмом Колмогорова
в реальное время, и не распознаваемый в реальное время
на машинах с полиномиальным доступом к памяти. Библ. 6 назв.
\RBibitem{Gri76}
\by Д.~Ю.~Григорьев
\paper Алгорифмы Колмогорова сильнее машин Тьюринга
\inbook Исследования по конструктивной математике и математической логике.~VII
\serial Зап. научн. сем. ЛОМИ
\yr 1976
\vol 60
\pages 29--37
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl2067}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=536657}
\zmath{https://zbmath.org/?q=an:0449.03030|0345.02023}
\transl
\jour J. Soviet Math.
\yr 1980
\vol 14
\issue 5
\pages 1445--1450
\crossref{https://doi.org/10.1007/BF01693975}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl2067
https://www.mathnet.ru/rus/znsl/v60/p29
Эта публикация цитируется в следующих 8 статьяx:
Andrew Adamatzky, Unconventional Computing, 2018, 431
Andrew Adamatzky, Emergence, Complexity and Computation, 23, Advances in Unconventional Computing, 2017, 709
Andrew Adamatzky, Encyclopedia of Complexity and Systems Science, 2017, 1
Andrew Adamatzky, “From reaction-diffusion to Physarum computing”, Nat Comput, 8:3 (2009), 431
V. Kreinovich, M. Margenstern, “In some curved spaces, one can solve NP-hard problems in polynomial time”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 224–250; J. Math. Sci. (N. Y.), 158:5 (2009), 727–740
Andrew Adamatzky, Lecture Notes in Computer Science, 4664, Machines, Computations, and Universality, 2007, 1
А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103; A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125
Цитирование в формате AMSBIB
Обратная связь: