Cтраница 1
Вычислимые функции называют также рекурсивными Подмножество в N рекурсивно тогда и только тогда, когда его характеристическая функция рекурсивна. Заметим, что характеристическая функция обязательно является тотальной. [1]
Вычислимая функция / с бесконечной областью определения - предел последовательности функций / на конечных множествах, графики которых расширяют друг друга. [2]
Существует вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента. [3]
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. [4]
Существует вычислимая функция, принимающая только значения 0 и 1 и не имеющая всюду определенного вычислимого продолжения. [5]
Существует вычислимая функция / из N в N не имеющая всюду определенного вычислимого продолжения. [6]
Если вычислимая функция д принадлежит классу Q, то существует функция h с конечной областью определения ( образец), принадлежащая классу Q, продолжением которой д является. [7]
Все конкретные вычислимые функции, рассмотренные в § 1, 3, 4 гл. Мы уже отмечали, что функции с и /, использованные в доказательстве теоремы 2.2, примитивно рекурсивны. Таким образом, класс примитивно рекурсивных функций является достаточно обширным. [8]
Существует тотальная вычислимая функция, не, являющаяся примитивно рекурсивной. [9]
Существует тотальная вычислимая функция g, яу что для любого п утверждение Qg ( Л) есть п ( К. [10]
Существует всюду определенная вычислимая функция двух аргументов, универсальная для класса всех примитивно рекурсивных функций одного аргумента. [11]
Класс вычислимых функций совпадает с классом нормально вычислимых функций. [12]
Для вычислимой функции Т ( п) ( R ( n)) назовем класс Т ( п) - распознаваемых ( R ( n) - распознаваемых) множеств последовательностей классом сложности и обозначим его через CT ( CR) - Следующий результат показывает, что существует бесконечно много классов сложности. [13]
Из вычислимой функции при добавлении и изъятии несущественных переменных I получается вычислимая функция. [14]
Понятие вычислимой функции является весьма важным во всей математике и центральным - в прикладной математике. [15]