Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Если ответ «нет», то Qz принимает значение 0. Если ответ «да», то машине Z, команды которой описываются «анализом» ее номера z, предлагается X в качестве входного задания.
Соединяя G2 и Z, мы можем получить машину Тьюринга, вычисляющую Qz(X). Тем самым доказана
Теорема. Функции Qpz (X) частично вычислимы.
Машина Тьюринга, вычисляющая функцию Qz (X), называется универсальной: если поместить на ее ленте подходящее число z, то она сможет вычислять частично вычислимую функцию, соответствующую этому числу.
5.4.2. Замечание, относящееся к терминологии
Ниже, в п. 5.5.3, будут определены рекурсивные функции. Здесь же мы хотим только сделать следующее замечание.
Можно доказать, что класс вычислимых функций совпадает с классом рекурсивных функций; следовательно, прилагательные «вычислимый» и «рекурсивный» являются в принципе синонимами. Существуют, однако, случаи, в которых принято говорить лишь о рекурсивных функциях, избегая термина «вычислимые функции». Мы будем следовать именно этой традиции.
5.4.3. Определения
Далее нам часто придется пользоваться понятием характеристической функции множества. Гл. V. Вычислимость и разрешимость 91
Пусть EczN. Тогда характеристическая функция множества Er обозначаемая через СЕ, определяется следующим образом:
Аналогично определяется характеристическая функция множества E с= Np.
Рекурсивные множества. Мы будем говорить, что некоторое множество рекурсивно, если его характеристическая функция вычислима (ср. замечание в п. 5.4.2). Если множество рекурсивно, то существует машина Тьюринга, которая, получив на вход элемент этого множества, всегда ставит ему в соответствие некоторый ответ: либо 1, либо 0.
Рекурсивно перечислимые множества. Множество называется рекурсивно перечислимым, если оно является областью определения некоторой частично вычислимой функции.
Теоретически мы умеем перечислять частично вычислимые функции от одной целочисленной переменной, от двух целочисленных переменных и т. д.; следовательно, в принципе мы умеем перечислять и рекурсивно перечислимые множества: Sd0, SRi,..., Sflt-.....
5.4.4. Соотношение между понятиями рекурсивного и рекурсивно перечислимого множества
Теорема. Множество является рекурсивным тогда и только тогда, когда оно само и его дополнение рекурсивно перечислимы.
. Предположим, что множество R рекурсивно. Тогда существует машина Тьюринга, вычисляющая его характеристическую функцию (которая вычислима в силу рекурсивности R).
Отправляясь от этой машины, можно построить две другие машины Тьюринга, вычисляющие функции
Отсюда следует, что RaR суть рекурсивно перечислимые множества.
.. Предположим, что множества R и R рекурсивно перечислимы. Тогда они являются областями определения частично вычислимых функций /(X) и /(X) соответственно; этим функциям соответствуют вычисляющие их машины Тьюринга Z и І
Пусть дано X. Если предложить его в качестве исходного задания машинам Z и Z1 то одна из них обязательно выдаст некоторый
СЕ(х) =
1, если х^ Е, 0, если хфЕ.
/(X) =
1, если
не определена, если Ж ^R-, 0, если
не определена, если X ф. R. 92
Часть /. Предварительные сведения из логики и алгебры
результат, а другая нет. Если результат дает машина Z, то Cr(X) = 1, а_если Z, то Cr(X) = 0.
Пара Z, Z эквивалентна некоторой единой машине Тьюринга. Следовательно, функция Cr вычислима и R, равно как и R, является рекурсивным множеством.
5.4.5. Неэквивалентность рекурсивности и рекурсивной перечислимости
Приведенная теорема оставляет открытым вопрос о том, существуют ли рекурсивно перечислимые, но не рекурсивные множества.
Мы докажем существование таких множеств с помощью так называемого «диагонального процесса».
Рассмотрим множество машин Тьюринга, вычисляющих функции от одного аргумента. Каждой из этих машин мы будем предлагать в качестве исходного задания ее собственный гёделевский номер. Возможно одно из двух: либо, начав вычисления с Z = = ng(Z), машина Z когда-нибудь остановится и выдаст некоторый результат (в таком случае машину называют самоприменимой), либо она никогда не остановится.
Таким способом мы получаем некоторую функцию от г, которая, очевидно, есть не что иное, как Qz (г); ясно, что это частично вычислимая функция. Можно построить машину Тьюринга, вычисляющую эту функцию; для этого надо сначала построить универсальную машину, вычисляющую Qz (х).
Таким образом, множество G гёделевских номеров самоприменимых машин оказывается рекурсивно перечислимым.
Теперь предположим, что оно является и рекурсивным. Это равносильно рекурсивной перечислимости его дополнения
В таком случае должна существовать машина Тьюринга с каким-то номером X, перечисляющая G (т\ е. вычисляющая некоторую функцию с областью определения G); в перечислении рекурсивно перечислимых множеств множество G носило бы именно этот номер:
G = JRv
Для любого натурального числа х мы имели бы следующее:
JCS GФФjess SRv Однако в силу самого определения
Следовательно, Гл. V. Вычислимость и разрешимость
