Cтраница 4
В рассмотренных выше примерах каждая вычислимая функция оказывалась нормально вычислимой и наоборот. [46]
Из сказанного следует, что вычислимые функции образуют счетное подмножество множества всех функций натуральных чисел. А так как мы только что показали, что последнее не является счетным, существуют функции ( на самом деле их большинство), которые не вычислимы никакой процедурой. [47]
При этом произвольная отдельно взятая регулярно вычислимая функция характеризуется цифрой (, а сама функция I) ( /, п, а) определяется независимо от функций, которые ей надлежит изображать. [48]
Покажите, что существует такая тотальная вычислимая функция k, что для каждого п множество Wk w равно множеству точных n - х степеней натуральных чисел. [49]
Во-первых, существуют сколь угодно сложно вычислимые функции. [50]