Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Рекурсивные и рекурсивно перечислимые множества и предикаты



 

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

Утверждения о неразрешимости проблем распознавания свойств имеют следующий вид: “Не существует алгоритма, позволяющего по любому конструктивному объекту из заданного класса А узнать, обладает ли этот объект данным свойством”. Тезис Черча позволяет уточнить эту формулировку так: “Не существует машины Тьюринга, распознающей данное свойство объектов класса А”. При этом предполагается, что класс А состоит из слов в некотором конечном алфавите; но в действительности очень часто речь идет о классах иной природы, элементы которых кодируются словами. Что касается выражения “машина Тьюринга распознает свойство”, то оно понимается так: машина перерабатывает каждый элемент класса А в “и”, если он обладает данным свойством, и в “л” – если не обладает (вместо “и” и “л” можно использовать любые другие символы.). Аналогичным образом уточняются утверждения о нераспознаваемости отношений.

Проще всего доказывается неразрешимость некоторых алгоритмических проблем, относящихся к самой теории алгоритмов, а именно, проблем распознавания определенных свойств машин Тьюринга. Из них самая простая – проблема распознавания самоприменимости. Машина Тьюринга называется самоприменимой, если она применима к своему собственному коду. В противном случае машина называется несамоприменимой.

Теорема 4.1. Не существует алгоритма, позволяющего для любой машины Тьюринга узнать, является ли она самоприменимой.

В соответствии со сказанным выше точный смысл этого утверждения таков: не существует машины Тьюринга, перерабатывающей код любой самоприменимой машины Тьюринга в “и” и код любой несамоприменимой – в “л”.

Доказательство. Допустим, что такая машина существует; обозначим ее . По этой машине легко построить другую машину , работающую на кодах несамоприменимых машин так же, как , а на кодах самоприменимых машин работающую вечно.

Какова бы ни была машина Тьюринга М, машина применима к ее коду тогда и только тогда, когда М несамоприменима. Но отсюда следует, что, во-первых, не может быть самоприменимой, так как тогда она была бы неприменима к своему коду, т.е. была бы несамо-применима; во-вторых, не может быть несамоприменимой, так как в этом случае она была бы применима к своему коду, т.е. была бы самоприменима. Противоречие доказывает теорему.



Точное понятие алгоритма позволяет выделить среди всевозможных функций вычислимые, т.е. такие, значения которых можно “в самом деле находить”. Под таким же углом зрения можно рассмотреть и понятие множества: весьма естественно попытаться среди всевозможных способов задания множеств выделить “эффективные”, т.е. такие, которые позволяли бы “в самом деле работать” с множествами – указывать их конкретные элементы и производить над ними вычислительные операции, отвечать для конкретных объектов на вопрос, входят ли эти объекты в данное множество, и т.п. При этом, разумеется, придется ограничиться множествами, состоящими из конструктивных объектов; как и прежде, моделью конструктивного объекта будет служить слово в конечном алфавите. Однако во многих случаях удобно вместо слов рассматривать натуральные числа, пользуясь тем, что между словами в заданном конечном алфавите и натуральными числами можно установить очень простое взаимно однозначное соответствие. Именно, если фиксировать произвольное целое , то любое целое положительное n может быть единственным образом представлено в виде

,

где принимают значения (доказательство по индукции). Поэтому, если выбрать конечный алфавит мощности Р и сопоставить числу n, представленному в виде (4.1), слово , то каждому целому положительному n будет отвечать единственное слово; обратно, для каждого непустого слова в алфавите V по формуле (4.1) вычисляется единственное целое положительное число, которому отвечает это слово. Если, кроме того, числу 0 сопоставить пустое слово, мы получим взаимно однозначное соответствие между натуральным рядом и множеством всех слов в алфавите V. Число, соответствующее слову x, мы будем обозначать vx и называть стандартным номером этого слова, а само отображение v – стандартной нумерацией слов в алфавите V.



От обычной записи натуральных чисел в системе счисления с основанием Р представление с помощью отображения v отличается тем, что “цифры” a1a2…ap имеют значения 1,…,P, а не 0,…,P–1. Для наших целей обычная запись непригодна из-за того, что при ней используются не все слова, составленные из цифр, а только те, которые не начинаются с нуля.

Здесь мы будем все время, говоря о множествах, подразумевать множества натуральных чисел (и говоря о дополнении множества – дополнение до натурального ряда). Кроме того, будем считать, что фиксирован некоторый конечный алфавит V={a1,…,ap}, , и во всех вычислениях на машинах Тьюринга числа представляются словами в этом алфавите описанным только что способом.

Существуют, как известно, два основных способа задания множества – путем указания характеристического свойства его элементов и путем их перечисления. Владея точным понятием алгоритма, мы можем указать для каждого из этих двух способов “алгоритмический вариант”. Для первого способа такой вариант получается наложением условия, чтобы характеристическое свойство было распознаваемым (или, как часто говорят, разрешимым), т.е. чтобы существовал алгоритм, позволяющий по любому слову узнать, обладает ли оно этим свойством. В алгоритмическом варианте второго способа перечисление должно быть “в самом деле перечислением”, т.е. происходить с помощью некоторого перечисляющего алгоритма.

Эти соображения нетрудно уточнить следующим образом. В первом варианте не вполне четкое понятие “характеристическое свойство” можно заменить понятием “характеристический предикат”. Во втором варианте перечисляющий алгоритм можно понимать как машину Тьюринга, которая “выдает” в заключительных ситуациях все возможные элементы множества, если “подавать” на ее ленту в начальных ситуациях все возможные натуральные числа. Иначе говоря, перечисляемое множество должно быть множеством значений (одноместной) функции, которую вычисляет некоторая машина Тьюринга с входным и выходным алфавитами, совпадающими с нашим алфавитом V. Это приводит к следующим двум определениям.

Словарный предикат – выражение , где xi – слова в некотором алфавите. Например, x1пробегает слова в алфавите D1, x2 – слова в алфавите D2 и т.д. Про такой предикат говорят, что он относится к типу , указывая область пробегания каждого аргументного места.

Характеристическая функция предиката Р – функция вида такая, что для всех наборов , где : истинно ( – тогда и только тогда, когда...).

Рекурсивный предикат – предикат типа , для которого вычислима по Тьюрингу соответствующая характеристическая функция .

Предикат принадлежности множества Х– предикат, для которого выполняется следующее: P(x) истинно , при этом задано множество слов и всякое слово .

Рекурсивное множество – это множество XÍå*, для которого рекурсивен соответствующий предикат принадлежности и где x пробегает множество å*.

Рекурсивными множествами являются многие обычные множества натуральных чисел: множество четных чисел, множество простых чисел и т.д.

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

Рекурсивно перечислимый предикат – предикат P рекурсивно перечислим, если существует процедура, позволяющая устанавливать истинность P(x1,…xk); если же P(x1,…xk) ложно, то эта процедура иногда будет это устанавливать, а иногда будет продолжаться неограниченно долго.

Теорема 4.2. Применение логических связок Ù, Ú, к рекурсивным предикатам дает рекурсивные же предикаты.

Теорема 4.2¢. Применение квантора к рекурсивному предикату приводит к рекурсивному же предикату.

Интуитивно предикат Р рекурсивен, если существует алгоритм, позволяющий выяснить для каждого набора {x1,…xk} слов истинно P(x1,…xk) или нет.

Обычно арифметические предикаты x £ y, x + y = z, “x – простое число”, “х делит у” являются рекурсивными.

Здесь и далее под вычислимыми функциями будут подразумеваться одноместные вычислимые функции.

Рассмотрим свойства рекурсивных и перечислимых множеств.

Теорема 4.3. Объединение и пересечение рекурсивных множеств рекурсивны; дополнение к рекурсивному множеству рекурсивно.

Ввиду известного соответствия между теоретико-множественными операциями и пропозициональными связками эта теорема немедленно вытекает из следующей теоремы.

Теорема 4.3¢. Дизъюнкция и конъюнкция вычислимых предикатов вычислимы; отрицание вычислимого предиката вычислимо.

Теорема 4.3¢. справедлива для предикатов любой вместимости; мы, однако, докажем ее только для одноместных предикатов – этого достаточно, чтобы получить теорему 4.3. Для общего случая теорема доказывается аналогично.

Доказательство теоремы 4.3¢

1. Пусть машины Тьюринга M1 и M2 вычисляют предикаты F1(x) и F2(x), соответственно. Тогда машина, вычисляющая предикат F1(x) È F2(x) (с входным алфавитом, равным объединению входных алфавитов M1 и M2), будет работать следующим образом. Если на ее ленте в начальной ситуации записано слово (число) x, она это слово удваивает, вставляя между двумя его экземплярами разделительный знак (не принадлежащий объединению внешних алфавитов M1 и M2). Затем она работает со вторым экземпляром x как M1 (обращаясь при этом с разделительным знаком как с граничным маркером); если в результате получится И (ИСТИНА), то все содержимое ленты стирается и вслед за (настоящим) граничным маркером записывается и; если же в результате работы со вторым экземпляром x получилось Л (ЛОЖЬ), то машина стирает это л и разделительный знак, а затем работает с первым экземпляром х как M2.

2. Если машина М вычисляет предикат F(x), то машина, вычисляющая ØF(x), (с тем же входным алфавитом), должна работать так же, как М, до самого конца, а затем, если получилось И, переработать его в Л, а если Л – то переработать его в И.

3. Утверждение для конъюнкции следует из утверждений для дизъюнкции и отрицания ввиду соотношения F1(x)Ç F2(x) ºØ(Ø F1(x)ÈØ F2(x).

Теорема 4.4. Объединение и перечисление перечислимых множеств перечислимы.

Доказательство. Пусть машины M1 и M2 вычисляют функции f1(x) и f2(x) с множествами значений E1 и E2, соответственно. Тогда:

1) по машинам M1 и M2 легко построить машину, которая будет вычислять функцию f, определенную следующим образом:

 

, .

Значениями f будут те и только те числа, которые служат значениями хотя бы одной из функций f1, f2, так что множество ее значений есть E1 È E2;

2) нетрудно построить по M1 и M2 также машину, вычисляющую функцию g, такую, что: а) для чисел вида определена тогда и только тогда, когда f1(x) и f2(x) определены и совпадают, и в этом случае значение g(x) равно общему значению f1(x1) и f2(x2); б) для остальных х значение g(x) не определено. Значениями g будут те и только те числа, которые служат значениями как f1, так и f2, так что множество ее значений есть E1 Ç E2.

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

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

1. Пусть машина М вычисляет функцию f(x) с множеством значений Е. Рассмотрим машину, входной и выходной алфавиты которой совпадают с выходным алфавитом машины М, работающую следующим образом. Если в начальной ситуации на ее ленте записано число х, машина ставит справа от него разделительный знак (“квадратик”) и справа от этого знака проделывает два первых шага того вычисления машины М, которое начинается с числа 0. Затем головка идет вправо; в первой встретившейся ей при этом пустой ячейке ставится другой разделительный знак (“звездочка”), справа от этого знака записывается число 1 и производится первый шаг вычисления машины М, начинающегося с этого числа. Затем головка идет влево до квадратика, и на том участке ленты, где были проделаны два первых шага вычисления М, начинающегося с нуля, производится третий шаг этого вычисления. (Для этого нужно, чтобы после первых двух шагов была помечена ячейка, в которой остановилась головка, и метка указывала, на каком этапе вычисление было прервано.) Если на этом шаге головка машины М сдвигалась вправо, то производится сдвиг вправо той части записи, которая расположена правее преобразуемого сейчас участка. Далее головка идет вправо, и на том участке ленты, где был выполнен первый шаг вычисления М, начинающегося с единицы, производится второй шаг. После этого головка идет дальше вправо; в первой встретившейся ей пустой ячейке ставится еще одна звездочка, за ней записывается число 2 и производится первый шаг начинающегося с него вычисления М.

Потом головка снова идет влево до квадратика, после чего производится четвертый шаг вычисления с нулем, третий с единицей, второй с двойкой, затем через звездочку записывается число 3 и над ним производится первый шаг вычисления и т.д.

Таким образом, наша машина параллельно вычисляет (вернее, пытается вычислять) значения функции f для всевозможных значений аргумента n. Этот процесс продолжается до тех пор, пока на каком-то “n-участке” вычисление не остановится. Если эта остановка безрезультатная, так что f(n) не определена, машина продолжает работу с той только разницей, что далее головка проходит этот “n-участок”, не изменяя его. Если же вычислено значение f(n), оно сравнивается с х. При f(n)¹x работа продолжается так же, как в случае безрезультатной остановки; при f(n)=x все содержимое ленты стирается и машина переходит в заключительное состояние.

Ясно, что функция, вычисляемая описанной машиной, определена для тех и только тех x, которые служат значениями функции f, т.е. принадлежат Е.

2. Пусть машина М вычисляет функцию f с областью определения Е. Рассмотрим машину, входной и выходной алфавиты которой совпадают с входным алфавитом М, работающую так: если в начальной ситуации на ее ленте записано слово х, оно удваивается с поставкой разделительного знака между двумя экземплярами, затем со вторым экземпляром машина работает как М, и если при этом будет получено какое-то значение f(x), то справа от разделительного знака все стирается и он сам тоже, головка становится на граничный маркер и машина переходит в заключительное состояние; если же f(x), не определено, то машина “ломается” или работает вечно. Вычисляемая этой машиной функция определена в точности для тех же х, что и f, и в случае, когда ее значение определено, оно совпадает со значением аргумента; таким образом, множество значений этой функции есть Е.

Теорема 4.6. Множество A является рекурсивно перечислимым тогда и только тогда, когда существует разрешимый предикат , такой, что тогда и только тогда, когда .

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

Доказательство. По машине М, вычисляющей характеристический предикат множества Е, легко построить другую машину, которая выдает И, если М выдаст и, и работает вечно, если М выдает Л. Область определения вычисляемой этой машиной функции есть Е. Остается воспользоваться теоремой 4.4.

Теорема 4.8 (теорема Поста). Множество тогда и только тогда разрешимо, когда оно само и его дополнение рекурсивно перечислимы.

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

1. Пусть множества Е и СЕ (дополнение Е) рекурсивно перечислимы. По теореме 4.4 существуют машины Тьюринга M1 и M2, вычисляющие функции f1 и f2, с областями определения Е и СЕ, соответственно. Построим по ним машину (входной алфавит которой будет совпадать с входным алфавитом машины M1), работающую следующим образом. Если на ее ленте в начальной ситуации записано слово х в алфавите , оно удваивается (с постановкой разделительного знака между экземплярами), а затем оба экземпляра обрабатываются параллельно – первый по программе машины M1, второй по программе машины M2 (шаги вычислений с первым и вторым экземплярами производятся поочередно – ср. доказательство теоремы 4.4). Поскольку х принадлежит одному и только одному из множеств Е и СЕ, один и только один из этих двух параллельных процессов закончится вычислением значения соответствующей функции. После этого все стирается и записывается и, если вычислено значение f1, и л, если вычислено значение f2. Таким образом, наша машина вычисляет характеристический предикат множества Е.

2. Обратное утверждение непосредственно вытекает из теорем 4.3 и 4.7.

Обратимся теперь к вопросу о существовании неразрешимых и неперечислимых множеств, а также невычислимых функций. (Разумеется, речь идет о множествах натуральных чисел (или слов в конечных алфавитах) и о функциях, отображающих такие множества в такие же.) Ответить на этот вопрос очень просто исходя из мощностных соображений. Действительно, мощность множества функций, вычисляемых всевозможными машинами Тьюринга, во всяком случае не превосходит мощности множества кодов всевозможных машин Тьюринга, т.е. слов специального вида в алфавите {a1,…,a8}; но даже множество всех слов в конечном алфавите счетно, в то время как множество всех функций, отображающих подмножества натурального ряда на подмножества натурального ряда, имеет мощность континуума. Далее, мощность множества всех перечислимых множеств натуральных чисел не превосходит мощности множества вычислимых функций, значения которых пробегают эти множества; таким образом, множество перечислимых множеств натуральных чисел счетно, в то время как множество всех подмножеств натурального ряда имеет мощность континуума. Итак, невычислимые функции и неперечислимые (а значит, и неразрешимые) множества не только существуют, но их “больше”, чем вычислимых функций соответственно перечислимых множеств.

Это простое решение страдает, однако, существенным недостатком: оно не дает никакого конкретного примера неперечислимого множества или невычислимой функции. Кроме того, мощностные соображения не позволяют решить столь же естественный вопрос о существовании неразрешимых перечислимых множеств, поскольку множество разрешимых множеств тоже счетно. Если удастся указать пример неразрешимого перечислимого множества, то его дополнение, в силу теоремы 4.7, дало бы пример неперечислимого множества, а его характеристический предикат (точнее – функция, сопоставляющая значениям аргумента истинностные значения значений предиката) – пример невычислимой функции. Прежде чем привести такой пример, введем следующее определение.

Стандартный номер кода машины Тьюринга называется геделевским номером, или просто номером, этой машины.

Это определение нуждается, однако, в уточнении: ведь стандартная нумерация слов зависит от выбора алфавита (а также от выбора его пересчета). Коды машин Тьюринга – это цепочки в алфавите A¢ = {a1,…,a8}, и мы можем выбрать любой алфавит, содержащий А¢. Мы остановимся на алфавите {a1,…,a9}.

Теорема 4.9. Множество номеров самоприменимых машин Тьюринга рекурсивно перечислимо, но не разрешимо.

Поскольку мы обычно отождествляем слово с его номером, вместо множества номеров мы можем говорить здесь о множестве кодов.

Доказательство. Утверждение о неразрешимости этого множества есть просто другая формулировка теоремы 4.1. Чтобы доказать его перечислимость, рассмотрим машину Тьюринга с входным алфавитом {a1,…,a8}, работающую следующим образом: если на ее ленте в начальной ситуации записано слово x, она прежде всего, не изменяя этого слова, распознает, является ли оно кодом какой-либо машины Тьюринга; если нет – машина “ломается”, если да – удваивает слово x, вставляя между двумя его экземплярами a9, и далее работает как универсальная машина, т.е. преобразовывает слово х в соответствии с программой той машины, для которой это же слово служит кодом. Если при этом будет получен результат, т.е. если машина с кодом х самоприменима, то все содержимое ленты стирается, и машина переходит в заключительное состояние. (В противном случае она “ломается” или работает вечно.) Ясно, что вычисляемая этой машиной функция определена для тех и только для тех слов, которые являются кодами самоприменимых машин Тьюринга. Остается применить теорему 4.5.

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

Следствие. Множество номеров несамоприменимых машин Тьюринга неперечислимо.

Доказательство. Пусть А, В и С – соответственно, множество номеров несамоприменимых машин, дополнение к множеству номеров самоприменимых машин и множество чисел, не являющихся номерами никаких машин. Множество С разрешимо и тем более перечислимо, и если бы А также было перечислимо, то ввиду очевидного равенства B = A È C по теореме 4.4 оказалось бы перечислимым и В, что невозможно в силу теорем 4.8 и 4.9.

С помощью конструкции, использованной в доказательстве теоремы 4.9, мы докажем сейчас еще одну важную теорему. Ее доказательство предоставит нам еще два примера неразрешимых перечислимых множеств (а также способ получать такие примеры в любом числе).

Теорема 4.10.Существуют непересекающиеся рекурсивно перечислимые множества E1 и E2 такие, что никакое разрешимое множество не может содержать E1, не имея при этом общих точек с E2. (Как иногда говорят, E1 и E2 не отделимы разрешимыми множествами.)

Доказательство. Обозначим через E1 и соответственно через E2 множество кодов тех машин Тьюринга, которые перерабатывают свой собственный код в пустое и соответственно в непустое слово.

Для доказательства перечислимости этих множеств достаточно рассмотреть машину, использовавшуюся в доказательстве теоремы 4.8.

Пусть в случае E1, машина переходит в заключительное состояние лишь при условии, что результат, получаемый на этапе, когда машина работает как универсальная, есть пустое слово (пустое слово служит своим собственным кодом), а в случае E2 – при условии, что этот результат есть непустое слово. Допустим теперь, что существует разрешимое множество Е, содержащее E1 и не пересекающееся с E2. По машине, вычисляющей характеристический предикат множества Е, легко построить другую машину (обозначим ее М), которая каждое число, т.е. каждое слово x в алфавите {a1,…,a9} перерабатывает в непустое слово, если x Î E, и в пустое, если x Ï E. Но во что переработает машина М свой собственный код k(M)? Если в пустое слово, то тем самым k(M) Î E1, откуда k(M) Î E – а тогда по построению машины она должна перерабатывать k(M) в непустое слово. Если же М перерабатывает k(M) в непустое слово, то k(M) Î E2, откуда k(M) Ï E и, следовательно, М должна перерабатывать k(M) в пустое слово. Полученное противоречие доказывает теорему.

Замечания

1. Любая неразрешимая алгоритмическая проблема дает пример неразрешимого множества.

2. Существуют и такие множества натуральных чисел, которые неперечислимы вместе со своими дополнениями.

Нельзя ли использовать для перечисления множеств только всюду определенные вычислимые функции? Это лучше отвечало бы интуитивному представлению о перечислении: “запуская” машину последовательно для чисел 0, 1, 2,..., мы получили бы один за другим все элементы множества, никогда не рискуя, что вычисление окажется бесконечным или оборвется безрезультатно. Ответ на этот вопрос, за очевидным исключением пустого множества, оказывается положительным, что вытекает из следующей теоремы.

Теорема 4.11. Всякое непустое рекурсивно перечислимое множество является множеством значений некоторой всюду определенной вычислимой функции.

Доказательство. Пусть машина М вычисляет функцию f с непустым множеством значений Е и пусть x0 – некоторый элемент Е. Построим по машине М новую машину M1, которая будет работать так же, как машина, построенная в п. 1 доказательства теоремы 4.5, с той только разницей, что зона ленты, где записано данное число х, используется теперь как “счетчик шагов”: после имитации каждого шага какого-либо вычисления машины М головка машины М идет в зону счетчика, и содержащееся в этой зоне число уменьшается на единицу. Когда содержимое зоны счетчика оказывается нулем (пустым словом), имитация вычислений машины М прекращается и, если на имитировавшемся перед этим шаге работы машины М как раз было вычислено какое-то значение f(z) функции f, машина записывает это f(z) на ленте (стирая все остальное) и переходит в заключительное состояние; в противном случае она все стирает, записывает на ленте слово x0 и также переходит в заключительное состояние. Вычисляемая машиной M1 функция f1 всюду определена, и легко видеть, что множество ее значений совпадает с Е.

Рассмотрим теперь важный подкласс рекурсивно перечислимых множеств, а именно, так называемые креативные множества. Это те рекурсивно перечислимые множества, дополнение которых в некотором довольно сильном смысле не является рекурсивно перечислимым. Поэтому мы начнем с рассмотрения класса нерекурсивно перечислимых множеств, которому будут принадлежать эти дополнения.

Пусть А – любое множество, которое не является рекурсивно перечислимым. Тогда если Wx есть какое-нибудь рекурсивно перечислимое множество, содержащееся в А, то должно существовать число y Î A\Wx. Существование такого числа говорит о том, что A ¹Wx. Оказывается,что для некоторых нерекурсивно перечислимых множеств такое число может быть найдено эффективным образом. Рассмотрим, например, нерекурсивно перечислимое множество ={xçxÏWx}. Если , то не может быть, чтобы xÎ Wx (в противном случае xÎ K и Wx ). Отсюда x Î \ Wx, и нашим числом, показывающим, что Wx ¹ , является само числоx.

Нерекурсивно перечислимые множества, длякоторых такое число может быть всегда вычислено таким путем, носят название продуктивных.

Множество A называется продуктивным тогда и только тогда, когда существует всюду определенная вычислимая функция g такая, что из Wx Í A следует,что g(x) Î A\Wx. Функция g называется продуктивной функцией для множества A (рис. 4.1).

 

 

Рис. 4.1. Продуктивное множество

Пример 4.3. Множество продуктивно,причем продуктивная функция есть .

Пример 4.4. Следующие множества продуктивны:

,

(с – фиксированное число, – область определения ),

(с – фиксированное число, – множество значений ).

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

Самый простой пример креативного множества дает, конечно, множество К. Креативным множеством является рекурсивно перечислимое множество, которое нерекурсивно в очень сильной степени.

Пример 4.5. Следующие множества являются креативными:

,

,

.

Эти множества являются креативными, поскольку их дополнения – продуктивны (см. пример 4.4).

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!