Ответы на экзаменационные вопросы № 1-31 по курсу "Дискретная математика" (Определение взаимно однозначного соответствия между двумя множествами. Определение транспортной сети, разреза в ней и его пропускной способности. Теорема Форда-Фолкерсона), страница 6

Пусть АÌN. Множество А называют разрешимым (рекурсивным), если его характеристическая функция c_А(n), определяемая так: c_А(n)={1 при nÎА, 0 в противном случае}, вычислима. Иными словами А разрешимо, если существует алгоритм, определяющий по произвольному натуральному числу, входит оно в А, или нет.

Множество АÌN называется перечислимым (рекурсивно перечислимым), если оно есть множество значений некоторой вычислимой функции. Иными словами, множество перечислимо, если все его элементы и только они порождаются некоторым алгоритмическим процессом.

Теорема

Всякое разрешимое множество является перечислимым.

Доказательство: Пусть А – разрешимо, т.е. функция c_А(n)={1 при nÎА, 0 в противном случае}, вычислима. Построим вычислимую функцию f_А, перечисляющую множество А.

f_А(n+1)=min k {c_A(k)=1, k>f(n)}.

f_A(0)=min k {c_A(k)=1}.

Функция f_А вычислима благодаря вычислимости функции c_А.

Теорема

Множество А разрешимо тогда и только тогда, когда перечислимы А и`А.

Доказательство:

1.  А разрешимо => А перечислимо (доказано выше)

А разрешимо =>`А разрешимо (теорема 1) =>`А перечислимо

2.  Пусть А,`А перечислимы. Разрешающий алгоритм легко строится с помощью машин, перечисляющих эти множества. Решая эту задачу надо запустить обе машины, перечисляющие А и`А соответственно, и дожидаться, пока n будет сгенерировано одной из них. Так как А +`А = N, это число непременно появится. Поскольку А и`А не пересекаются, оно будет сгенерировано только одной машиной. Если оно сгенерировано машиной А, то nÎА, если`А – то nÏА.

Вопрос20.

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

Док-во:

Организуем процесс параллельного вычисления значений функции f для всех натуральных чисел x. Смотри чертеж. Если вычисление значения f(x₀) заканчивается на каком-то такте t₀ работы соответствующей машины, то мы сразу и только в этом случае объявляем, что x₀ – входит в перечисляемое нами множество. Понятно, что: 1) мы построили процесс эффективного порождения некоторого множества, и значит оно перечислимо; 2) это множество – область определения данной вычислимой функции f. Итак, область определения всякой вычислимой функции – перечислима.

Следствие: Существуют перечислимые множества, не являющиеся разрешимыми.

Док-во:

Ф(n,x) – универсальная вычислимая функция (для класса всех выч. ф-ий одного переменного). В силу следствия и из теоремы об универсальной ф-ии область определения D_ф – неразрешима, но согласно предыдущей теореме множество D_ф перечислимо.

Вопрос 21.

Доказать теорему Райса.

Не существует нетривиальных разрешимых классов вычислимых функций.

Док-во:

Лемма: Для всякой вычислимой функции f(n, x) двух переменных существует алгоритм, по произвольному числу n₀, выдающей один из номеров a(n₀) функции f(n₀, x) переменного x.

Док-во леммы:

Укажем программу вычисления ф-ии f(n₀,x). По условию, т.к. ф-ия f(n,x) двух переменных вычислима, существует машина T_f, вычисляющая значение этой ф-ии 2-х переменных. Требуемая программа работает так: вначале имея на ленте запись числа x, делаем слева от него пропуск в одну клетку и записываем левее число n₀. После этого остается запустить программу f(n,x). Описанная процедура и служит изложением алгоритма a(n₀).

Замечание: В обозначениях леммы, очевидно имеем: f(n₀, x)=Ф(a(n₀), x).

Док-во теоремы:

Пусть w - некоторое перечислимое неразрешимое множество и пусть K – некоторый нетривиальный класс вычислимых ф-ий. Как известно нигде неопределенная ф-ия z(x) явл. вычислимой. Имеем одно из двух: либо zÎK либо zÏK. Док-во теоремы проходит аналогично в обоих случаях. Рассмотрим, например, когда zÎK. Поскольку К¹В, $xÎВ-К. Область определения ф-ии x очевидно не пуста. Построим ф-ию 2-х переменных: f(n,x)={ z(x) если nÏw; x(x) если nÎw. Покажем, что ф-ия f(n,x) вычислима. Алгоритм вычислений ее значений таков:

Запускаем алгоритм перечисления мн-ва w. До тех пор, пока он не выдаст число n – значение 1-го аргумента не делаем более ничего. Когда (и если) обнаружется, что nÎw запускаем программу вычисления ф-ии x(x) для значения аргумента х. Изложенное и есть требуемый алгоритм.