Cтраница 3
В дальнейшем для вычислимых функций будем использовать исключительно машины, вычисляющие их правильным образом. [31]
Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма. [32]
Работая с композицией частично вычислимых функций, необходимо быть очень внимательным. [33]
Класс & - предсказуемо вычислимых функций определяется в терминах сложности вычислений на машинах Тьюринга. Однако, доказав, что этот класс совпадает с классом о элементарных функций, мы охарактеризовали & - в теоретико-числовых терминах, не ссылаясь на машины Тьюринга. [34]
Докажем, что всякая вычислимая функция / с натуральными аргументами и значениями может быть продолжена до всюду определенной вычислимой функции д: N - N. В самом деле, если / вычисляется алгоритмом А, то следующий алгоритм В вычисляет функцию д, продолжающую /: если А останавливается на п, то В дает тот же результат, что и А; если А не останавливается на тг, то В дает результат ( скажем) О. [35]
По теореме 4.1 существует тотальная вычислимая функция / г, такая, что tk w ( у) жу Следовательно, для каждого фиксированного п величина k ( n) является индексом функции уп. [36]
Доказать, что существует универсальная вычислимая функция, относительно которой нигде не определенная функция имеет единственный номер. [37]
Пусть / - - тотальная инъективная вычислимая функция, такая, что множество Ran ( /) не является рекурсивным. Упражнение 2.18 ( 7) показывает, что таких функций очень много. [38]
Очевидно, композиция двух вычислимых функций вычислима. При этом это утверждение кажется эффективным в том смысле, что по программам двух функций можно алгоритмически получить программу их композиции. [39]
Поэтому задаваемая им нумерация вычислимых функций является главной. [40]
Построение четко выделенного класса вычислимых функций сопряжено с рядом трудностей; для достижения такой цели нужны некоторые упрощающие соглашения. Поэтому вполне естественно ограничиться случаем, в котором и независимые переменные, и функции могут принимать только целые неотрицательные значения. [41]
Напомним, что класс вычислимых функций счетен, тогда как класс всех функций несчетен. [42]
Часто при введении понятия интуитивно вычислимой функции сначала описывают понятие алгоритма ( алгоритм в интуитивном смысле - это точное предписание о выполнении в определенном порядке некоторой системы операций для решения всех задач данного типа), а затем называют интуитивно вычислимой ту функцию, для которой существует алгоритм ( в интуитивном смысле) вычисления ее значений. [43]
Одним из уточнений понятия интуитивно вычислимой функции является понятие частично рекурсивной функции, к введению которого мы приступаем. [44]
Момент t есть по определению вычислимая функция, определенная на каналах и перерабатывающая каждый канал в натуральное число. [45]