7.2. Относительная вычислимость: эквивалентное описание

Сейчас мы дадим эквивалентное определение вычи­слимости функции относительно а, не апеллирующее к программам с вызовом оракула.

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

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

Пусть имеется множество М троек вида (х,у,£), где х ж у — натуральные числа, а, t — образец. Будем гово­рить, что две тройки (х\,у\^\) ж {х2,У2^2) противоре­чат друг другу, если х\ = Х2, уг ф У2, з, образцы 1\ ж 12 совместны. Множество М будем называть корректным, если в нём нет противоречащих друг другу троек.

Пусть М — корректное множество, а а — некоторая функция. Отберём в М все тройки вида (х,у,£), для ко­торых ^ является частью а (график ^ является подмноже­ством графика а). Входящие в них образцы совместны, поэтому (в силу корректности) среди отобранных троек нет двух, у которых первые члены равны, а вторые — нет. Значит, отбросив третьи компоненты в отобранных тройках, мы получим график некоторой функции (во­обще говоря, частичной). Будем обозначать эту функ­цию М[а].

Теорема 45. Частичная функция /: N —У N вычислима относительно всюду определённой функции а : N —У N то­гда и только тогда, когда существует перечислимое кор­ректное множество троек М, для которого f = М[а].

<] Пусть имеется программа р, вычисляющая / и включающая в себя обращения к внешней процедуре а. Будем для всех натуральных п моделировать работу этой программы на входе п по всем путям, то есть пре­дусматривая все возможные значения а(п) для каждого обращения к внешней процедуре. Для каждого п по­лучается дерево вариантов — каждому обращению к внешней процедуре соответствует развилка со счётным ветвлением. На некоторых ветвях этого дерева вычисле­ния завершаются и программа выдаёт ответ. Как только мы обнаруживаем, что на входе х возможен ответ у (на некоторой ветви), мы образуем тройку (x,y,t), где t — образец, содержащий все аргументы и значения функ­ции а, использованные на этой ветви.

Полученное множество троек, которое мы обозна­чим М, будет перечислимым (описанная процедура по­зволяет выписывать все его элементы). В этом множе­стве нет противоречащих друг другу троек. В самом деле, если для одного и того же х в него вошли трой­ки (x,y\,t\) и {x,y2,i2) с у\ ф г/2! то они соответствуют разным путям в дереве вычислений на одном и том же входе х. Эти пути в каком-то месте разошлись, то есть на один и тот же вопрос в них были получены разные от­веты. Эти ответы вошли в образцы i\ и i2, и потому эти образцы несовместны. Итак, множество М корректно.

Пусть а — всюду определённая функция. Присоеди­ним её к программе р. После этого программа р вычи­сляет функцию /. Покажем, что / = М[а]. В самом де­ле, пусть f(x) = у, то есть работа программы р на вхо­де х дала ответ у. Эта работа включала в себя несколь­ко вызовов функции а и соответствовала некоторой ве­тви рассмотренного выше дерева. Пусть i — образец, со­держащий все заданные при этом вопросы и полученные на них ответы. Тогда i является частью а. Кроме того, тройка (x,y,t) входит в множество М. Следовательно, М[а](ж) определено и равно у.

Напротив, если М[а](ж) = у, то существует трой-ка (х,у,£) £ М, для которой I является частью а. Эта тройка соответствует некоторой ветви дерева вычисле­ний. Поскольку I является частью а, присоединение к программе р внешней процедуры а приведёт к тому, что вычисления пойдут именно по этому пути, и программа даст ответ у.

Итак, для любой программы р мы построили коррект­ное множество М, которое задаёт ту же функцию, что и программа р, и первая половина утверждения теоремы доказана.

Чтобы доказать вторую половину, предположим, что имеется корректное множество М, и построим эквива­лентную ему программу р. Эта программа будет (после присоединения к ней оракула, вычисляющего а) вычи­слять функцию М[а]. Программа р действует так: полу­чив вход х, она перечисляет множество М и отбирает в нём тройки, первым членом которых является х. Для каждой такой тройки (ш,г/Д), вызывая внешнюю проце­дуру (задавая вопросы оракулу) мы выясняем, является ли I частью функции а. Если является, то вычисление за­канчивается и выдаётся ответ у, если нет, перечисление множества М продолжается.

Очевидно, что построенная программа р вычисляет функцию М[а]. >

59. Предположим, что мы провели это построение в обе стороны: сначала но корректному множеству М построили некоторую программу, как это описано во второй половине доказательства, а затем но программе построили некоторое корректное множество Л/'. Может ли М' отличаться от V/.'