3.2. Вычислимые последовательности вычислимых функций

Пусть дана некоторая последовательность /о, /ц,... вычислимых функций одного аргумента. Мы хотим при­дать смысл выражению «последовательность г н->- вы­числима». Это можно сделать двумя способами:

• можно называть эту последовательность вычисли­мой, если функция Р двух аргументов, заданная формулой Р(г,п) = /г(я), является вычислимой.

• можно называть эту последовательность вычисли­мой, если существует вычислимая последователь­ность чисел со, с\,..., для которой с,- является од­ним из номеров функции

Второе определение (в отличие от первого) зависит от выбора нумерации.

Теорема 17. Если нумерация является вычислимой (то есть соответствующая универсальная функция вычисли­ма), то из второго определения следует первое. Если ну­мерация является к тому же главной, то из первого опре­деления следует второе.

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

<] Если II — вычислимая универсальная функция, а последовательность г н->- с,- вычислима, то функция Р: (г, ж) и-)- /,-(ж) = и(с-1,х) вычислима как результат подстановки одной вычислимой функции в другую.

Напротив, если функция Р вычислима, а универсаль­ная функция 1} является главной, то функция-трансля­тор, существующая по определению главной универсаль­ной функции, как раз и даёт по г один из номеров функ­ции >

31. Пусть фиксирована главная универсальная функция для класса вычислимых функций одного аргумента. Тогда возникает нумерация вычислимых действительных чисел в соответствии с определением на с. 16: номером числа а явля­ется любой номер любой функции, которая но рациональному е > 0 даёт £-нриближение к а.

(а) Покажите, что существует алгоритм, который но лю­бым двум номерам двух вычислимых действительных чисел даёт (некоторый) номер их суммы.

(б) Покажите, что не существует алгоритма, который но любому номеру любого вычислимого действительного числа отвечает на вопрос, равно ли это число нулю.

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