1.1. Вычислимые функции

Функция / с натуральными аргументами и значени­ями называется вычислимой, если существует алгоритм, её вычисляющий, то есть такой алгоритм А, что

• если Дп) определено для некоторого натурально­го п, то алгоритм А останавливается на входе п и печатает Дп);

• если Дп) не определено, то алгоритм А не остана­вливается на входе п.

Несколько замечаний по поводу этого определения:

1. Понятие вычислимости определяется здесь для ча­стичных функций (областью определения которых явля­ется некоторое подмножество натурального ряда). На­пример, нигде не определённая функция вычислима (в качестве А надо взять программу, которая всегда заци­кливается) .

2. Можно было бы изменить определение, сказав так: «если Дп) не определено, то либо алгоритм А не остана­вливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, ал­горитм может зацикливаться).

3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (сло­ва в алфавите {0,1}), пары натуральных чисел, конеч­ные последовательности слов и вообще любые, как гово­рят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значения­ми которой являются рациональные числа.

Для функций, скажем, с действительными аргумен­тами и значениями понятие вычислимости требует сне­

Разрешимые множества

циального определения. Здесь ситуация сложнее, опреде­ления могут быть разными, и мы о вычислимости та­ких функций говорить не будем. Отметим только, что, например, синус (при разумном определении вычислимо­сти) вычислим, а функция sign(ai), равная —1, 0 и 1 при ш<0, ш = 0иі>0 соответственно — нет. Точно так же требует специального определения вычислимость функ­ций, аргументами которых являются бесконечные после­довательности нулей и единиц и т. п.

4. Несколько десятилетий назад понятие алгоритма требовало специального разъяснения. Сейчас («компью­терная грамотность»?) такие объяснения всё равно никто читать не будет, поскольку и так ясно, что такое алго­ритм. Но всё же надо соблюдать осторожность, чтобы не принять за алгоритм то, что им не является. Вот пример неверного рассуждения:

«Докажем», что всякая вычислимая функция / с нату­ральными аргументами и значениями может быть про­должена до всюду определённой вычислимой функции д: N —У N. В самом деле, если / вычисляется алгорит­мом А, то следующий алгоритм В вычисляет функцию д, продолжающую /: «если А останавливается на п, то В да­ёт тот же результат, что и А; если А не останавливается на п, то В даёт результат (скажем) О». (В чём ошибка в этом рассуждении?)