Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

КЛАССЫ ПРЕДСКАЗУЕМО ВЫЧИСЛИМЫХ ФУНКЦИЙ
Р. В. Ричи
ВВЕДЕНИЕ
В этой работе мы изучаем последовательность классов вычислимых функций, сложность вычисления которых можно сравнительно просто предсказать. Класс рекурсивных функций состоит из таких функций, для которых существуют механические процедуры для получения значений из аргументов. Однако этот класс, так как он включает все вычислимые функции, должен содержать функции со сколь угодно сложными вычислениями. Существуют различные более ограниченные классы функций, которые легко вычисляются каким-либо способом, однако это в большой степени происходит за счет интуиции. Приятное исключение составляет класс F — функций, вычислимых2) конечными автоматами. Но этот класс слишком ограничен: он не содержит даже умножения. Мы строим иерархию более содержательных классов функций; каждый из них определяется как класс таких функций, сложность вычисления которых «предсказывается» функцией из предыдущего класса.
Известно, что класс F числовых функций, вычислимых конечными автоматами, содержит сложение и замкнут относительно явных преобразований3) и композиции. В частности, он содержит линейные функции4). Этот класс F берется в качестве исходного класса, так как эти функции вычисляются наиболее просто: по входу сразу печатается выход. Для получения большего класса рассматриваем класс функций, вычислимых (в двоичной системе счисления) на машинах Тьюринга, использующих ленту, длина которой ограничена более простой функ-
') Ritchie R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc., 106 (1963), 139—173.
2) Эти функции закодированы в общепринятой двоичной системе счисления, но ясно, что в равной степени приемлемо кодирование в /г-ичной системе счисления для любого п. Определение F смотри в приложении 2.
3) В смысле Смульяна. Определение смотри ниже в сноске 1 на стр. 53.
4) Включение линейных функций подразумевается в смысле [2, стр. 31 и 41], и этого достаточно для дальнейшего. (Фактически, если читатель хочет, он может без ограничения общности считать F на протяжении всей статьи классом линейных функций.) Свойства F, которые мы будем использовать, исследуются в приложении 2.

 

1 10 20 30 40 50 51 52 53 54 55 56 57 58 59 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика