Об одной характеристике сложности рекурсивных предикатов

В статье рассматривается один из возможных подходов к доказательству ряда теорем, касающихся вычисления рекурсивных предикатов автоматами различных типов в реальное время. Этот подход основан на соображениях информационного характера и сводится, в общих чертах, к следующему: вводится в рассмотрение характеристика сложности рекурсивных предикатов и характеристика “вычислительной силы” автоматов (для лостаточно общего понятия автомата). Вопрос о том, возможно ли вычисление в реальное время данного рекурсивного предиката автоматом из некоторого класса в ряде случаев решается путем сравнения характеристики сложности предиката с характеристикой “вычислительной силы” автоматов рассматриваемого класса. Для указанных характеристик установлены достижимые верхние и нижние оценки. Существенно, что рассматриваемая характеристика сложности рекурсивных предикатов не зависит от выбора стандартизации общего понятия алгорифма. Библ. 22 назв.