|
Труды ордена Ленина Математического института имени В. А. Стеклова, 1970, том 113, страницы 79–101
(Mi tm3056)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Об одной характеристике сложности рекурсивных предикатов
Р. И. Фрейдзон
Аннотация:
В статье рассматривается один из возможных подходов к доказательству ряда теорем,
касающихся вычисления рекурсивных предикатов автоматами различных типов
в реальное время. Этот подход основан на соображениях информационного характера и сводится, в общих чертах, к следующему: вводится в рассмотрение характеристика сложности
рекурсивных предикатов и характеристика “вычислительной силы” автоматов (для
лостаточно общего понятия автомата). Вопрос о том, возможно ли вычисление в реальное
время данного рекурсивного предиката автоматом из некоторого класса в ряде случаев
решается путем сравнения характеристики сложности предиката с характеристикой “вычислительной
силы” автоматов рассматриваемого класса. Для указанных характеристик
установлены достижимые верхние и нижние оценки. Существенно, что рассматриваемая
характеристика сложности рекурсивных предикатов не зависит от выбора стандартизации
общего понятия алгорифма. Библ. 22 назв.
Образец цитирования:
Р. И. Фрейдзон, “Об одной характеристике сложности рекурсивных предикатов”, Проблемы конструктивного направления в математике. 5, Тр. МИАН СССР, 113, 1970, 79–101; Proc. Steklov Inst. Math., 113 (1970), 91–117
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tm3056 https://www.mathnet.ru/rus/tm/v113/p79
|
Статистика просмотров: |
Страница аннотации: | 128 | PDF полного текста: | 71 |
|