Taran_T_A_quot_Osnovy_Diskretnoy_Matematiki_qu

Рекурсивные множества называют также разрешимыми множествами.

Можно доказать следующие теоремы о рекурсивных и рекурсивно перечислимых множествах.

Теорема 15.8. Если множества R и S рекурсивно перечислимы, то их объединение R S и пересечение R ∩ S также рекурсивно перечислимы.

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

Из условия теоремы следует, что существуют две машины МR è ÌS, которые порождают элементы множеств R и S соответственно. Тогда можно построить машину Тьюринга МR ÌS, выписывающую на ленту последовательно элементы r1, s1, r2, s2,… , удаляя повторяющиеся элементы. Можно построить также машину МR ∩ ÌS, которая в этой последовательности будет оставлять только те элементы, которые входят одновременно и в R, и в S.

Теорема 15.9. Множество S рекурсивно тогда и только тогда, когда S и его дополнение S′ рекурсивно перечислимы.

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

1. Предположим, что S N и S рекурсивно. Тогда существует машина Тьюринга МS, которая для каждого натурального числа n N распознает, принадлежит ли оно множеству S, или нет. Тогда можно построить такую композицию, что если МS(n) останавливается в состоянии «да!», т.е. n S, то начинает работу машина М1, которая выписывает на свою ленту все элементы S, а если МS(n) останавливается в состоянии «нет!», т.е. n S, то начинает работать машина М2, которые выписывает все элементы, не принадлежащие S, на свою ленту. Тогда машина М1 порождает все элементы S, а М2 — его дополнения S′. Согласно определению, это означает, что S и его дополнение S′ рекурсивно перечислимы.

2. Предположим, что S и S′ рекурсивно перечислимы. Следовательно, существуют порождающие их машины МS è ÌS′. Тогда можно построить машину М(x), которая для каждого x будет запускать попеременно МS è ÌS′ и сравнивать x с очередным элементом si. Åñëè x = si, порожденному машиной МS, то машина М(x) останавливается в «да!» состоянии, а если машиной МS′ — то в «нет!» состоянии. Тогда машина М(x) работает как распознающая машина Тьюринга для вычисления предиката x S. Существование такой машины означает, что множество S рекурсивно.

Теорема 15.10. Существуют рекурсивно перечислимые, но нерекурсивные множества.

В силу теоремы 15.9 это означает, что существует такое множество S, которое рекурсивно перечислимо, но его дополнение S′ не является рекурсивно перечислимым.

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

Предположим, что все рекурсивно перечислимые множества мы можем переписать в виде списка (занумеровать): S1, S2,…, Si,…. Тогда существует машина Тьюринга М(n), такая, что для каждого натурального числа n = 1, 2, 3,… она проверяет, принадлежит ли число n, соответствующее индексу множества Sn, самому этому множеству, (т.е. n Sn), или нет. Тогда, если n Sn, она выдает сообщение «да» и записывает это число в множество U, а если n Sn, то она выдает «нет», и записывает число n в множество U′. Таким образом, U будет содержать некоторое подмножество натуральных чисел и будет рекурсивно перечислимо. Очевидно, что U′ будет дополнением множества U до множества всех натуральных чисел. Докажем теперь, что множество U′ не рекурсивно перечислимо.

Действительно, если U′ рекурсивно перечислимо, то U′ входит в наш пересчет с некоторым номером k, т.е. U′ = Sk. Тогда, если

k Sk , то k U, т.е. k U′, но тогда k Sk; à åñëè k Sk , òî k U′, ò.å. k Sk.

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

Из доказательства этой теоремы становится понятным, что алгоритмическая неразрешимость и нерекурсивность — это взаимосвязанные свойства. Способ кодирования программ машин Тьюринга, описанный выше, задает эффективную процедуру, порождающую множество индексов машин Тьюринга. Отсюда следует, что множество всех машин Тьюринга рекурсивно перечислимо. Рекурсивно перечислимым является также множество всех машин, которые заканчивают свою работу за конечное число шагов. При доказательстве алгоритмической неразрешимости проблемы останова для машины Тьюринга было показано, что можно построить такую машину Тьюринга, для которой невозможно распознать останов. Это построение доказывает, что множество всех машин Тьюринга, которые не останавливаются на некотором слове, не является рекурсивно перечислимым. Следовательно, множество всех машин, которые останавливаются, нерекурсивно (неразрешимо). Нерекурсивность множества означает, что его характеристическая функция, распознающая принадлежность элемента этому множеству, является невычислимой. Построим такую функцию.

15.6. Невычислимые функции

Определим предикат T(i, a, x), где i — индекс машины Тьюринга, которая, будучи применима к слову a, заканчивает работу в момент времени x, вычисляя при этом функцию ϕ i(a). Существование момента времени x — гарантия останова машины. Этот предикат будет разрешимым (т.е. истинным при некоторых значениях i, a, x). Действительно, можно построить такую универсальную машину Тьюринга М′, которая для любой машины будет определять, является ли i правильным кодом машины Тьюринга. Если i не является кодом, то М′ остановится в состоянии «нет!»; тогда |T(i, a, x)| = F. Если i является правильным кодом машины Тьюринга, то М′ будет работать над словом a и остановится в состоянии «да!», если в момент x машина вычислит значение функции ϕ i(a). Тогда |T(i, a, x)| = T.

Эти рассуждения показывают, что предикат T(i, a, x) разрешим в интуитивном смысле. Если принимать тезис Ч¸рча, то этот предикат разрешим и в строгом смысле, т.е. можно построить такую машину Тьюринга, которая вычисляет характеристическую функцию предиката:

0, åñëè T(i,a, x) = F, τ(i,a, x) =

1, åñëè T(i,a, x) =T.

Таким образом, во-первых, предикат T(i, a, x) разрешим, а вовторых, ϕ i(a) вычислима как частичная функция от x. Действительно, она определена не для всех i и a, а только для тех, для которых существует момент времени x, когда машина Тьюринга остановится. Поэтому ϕ i(a) является частично определенной функцией и вычислима как частичная функция от i и x, т.е. тогда, когда | a xT(i, a, x)| = T.

Определим теперь следующую функцию:

Теорема 15.11. (Черча). Функция ψ (a) невычислима.

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

Предположим, что ψ (a) вычислима. Тогда существует машина Тьюринга МP, вычисляющая ψ (a), и p — индекс этой машины, т.е. ψ (a) = ϕ ð(a) для всех a. Подставляя p вместо a, получим: ψ (p) = ϕ ð(p). Тогда предикат | xТ(р, а, x)| = Т для данного p и для любого a, в том числе и для а = р, т.е. | xТ(р, р, x)| = Т. Но тогда, по определению функции ψ (a), ψ (р)= ϕ ð(р) + 1, что противоречит полученному ранее равенству. Полученное противоречие доказывает утверждение теоремы.

Теорема Ч¸рча дает конструктивный способ построения невычислимой функции.

Пример. В качестве примера определения невычислимой функции рассмотрим следующую задачу. Представим себе большую библиотеку, в которой книги расставлены по разделам. Для каждого раздела составлен каталог. Каждая книга имеет назначенную ей цену, а поскольку каталог раздела содержит сведения обо всех книгах, он должен быть самой ценной книгой. Поэтому его стоимость определена как функция от стоимости самой дорогой книги в разделе: Сê = Ñmax + 1. Книг в библиотеке оказалось настолько много, что все каталоги были составлены в отдельный раздел — раздел каталогов, для которого также был составлен каталог — каталог каталогов. Ему также должна быть назначена цена по определенному выше правилу: стоимость его Сêê должна быть самой высокой

в этом разделе, т.е. Сêê = Ñêmax, и должна быть на единицу больше цены самой дорогой книги в разделе: Сêê = Ñêmax + 1. Но поскольку

каталог каталогов сам является каталогом, то его цена должна быть на единицу больше его собственной стоимости: Сêê = Ñêê + 1. Таким образом, оказалось, что стоимость его невозможно вычислить по заданному правилу.

Невычислимая функция Ч¸рча уже встречалась нам и ранее: при доказательстве несчетности множества всех арифметических функций, при доказательстве нерекурсивности множества, имеющего не перечислимое рекурсивно дополнение. Но в теореме Ч¸рча эта функция определена через предикат Т(р, а, x), существенно использующий условие останова для машины Тьюринга — переменную x. Предикат xТ(р, р, x) формулирует условие останова машины Тьюринга на своем собственном коде, т.е. условие самоприменимости. Полученное в теореме противоречие доказывает, что этот предикат неразрешим (т.е. предположение о его разрешимости было ложным). Тем самым теорема Ч¸рча еще раз доказывает неразрешимость проблемы самоприменимости, а в терминах теории предикатов — существование неразрешимого предложения: предложения о распознавании останова для машины Тьюринга на своем собственном коде. Существование неразрешимого предиката доказывает неразрешимость исчисления предикатов, содержащего арифметику, — вспомним, что формула G, построенная Г¸делем, также утверждает свою собственную невыводимость, а поскольку ее действительно нельзя ни доказать, ни опровергнуть, то это равнозначно неразрешимости проблемы самоприменимости.

Интуитивно нам уже понятно, что неразрешимость теории предикатов связана с нерекурсивностью множества всех теорем формальной теории. Арифметизация формальной теории S (и

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

Формально это доказывается следующей теоремой, доказательство которой известно как доказательство Россера теоремы Геделя.

Теорема 15.12. Пусть существуют два рекурсивно перечислимых непустых множества C0 è C1, такие, что C0 ∩ C1 = , и существуют два рекурсивно перечислимых множества D0 è D1,

такие, что C0 D0, C1 D1 è D0 ∩ D1 = . Тогда можно найти такое число f, что f D0 è f D1.

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

Определим множества C0 è C1 следующим образом:

C0 = {a | ϕ a(a) определена и ϕ a(a) = 0}, C1 = {a | ϕ a(a) определена и ϕ a(a) ≠ 0}.

Понятно, что множества C0 è C1 непусты и не пересекаются.

Пусть существуют множества D0 è D1, удовлетворяющие условиям теоремы.

Тогда из того, что D0 рекурсивно перечислимо, следует существование машины Тьюринга, перечисляющей элементы D0, т.е. вычисляющей функцию ϕ 0(D0), è èç òîãî, ÷òî D1 рекурсивно перечислимо, следует существование машины Тьюринга, перечисляющей элементы D1, т.е. вычисляющей функцию ϕ 1(D1). Тогда можно построить машину Тьюринга М, которая для любого числа a определяет, принадлежит это число нумерации ϕ 0 или нумерации ϕ 1. При этом, если машина Тьюринга М находит число a в нумерации

то машина напечатает «1», т. е. ϕ f(f) = 1. Тогда, по определению

следовательно, f C0, а значит и f D0, следовательно, f D1. Таким образом, f не попадает ни в одно, ни в другое множество. Это противоречие доказывает теорему.

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

Теорема 15.13. (Теорема Г¸деля в форме Россера). Пусть K — теория первого порядка с теми же символами, что и теория S, и пусть, кроме того, K удовлетворяет следующим условиям:

(1)всякое рекурсивное выражение выразимо в K;

(2)множество г¸делевых номеров собственных аксиом теории K рекурсивно;

(3)выполнены условия: имеется формула u ≤ v такая, что

(i) для всякой формулы A(x) и для всякого натурального k

|—K A(0) & A(1) & ... & A(k) → x(x ≤ k → A(x)); (ii) для всякого натурального числа

|—K x ≤ k k ≤ x.

Тогда для теории K справедлива теорема Г¸деля в форме Россера: если теория K непротиворечива, то существует неразрешимое в этой теории предложение. (Заметим, что условие (1) выполняется, если в K представима каждая рекурсивная функция).

Определение 15.15. Назовем теорию K рекурсивно аксиоматизируемой, если существует такая теория K′ с тем же, что и у K, множеством теорем, что множество г¸делевых номеров собственных аксиом K′ рекурсивно.

Определение 15.16. Теория называется эффективно аксиоматизированной, если существует эффективная процедура, позволяющая для каждой формулы этой теории узнавать, является ли она ее аксиомой.

Следствие. Теорема Г¸деля в форме Россера справедлива для каждого непротиворечивого рекурсивно аксиоматизируемого расширения теории S, т.е. для каждого такого расширения существует предложение, неразрешимое в нем.

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

Так как все рекурсивные отношения выразимы в S, то они выразимы и во всяком расширении S. Точно так же, если условия (i) — (ii) выполнены в S, то они выполнены и во всяком расширении S. Поэтому, на основании теоремы 14.9, теорема Г¸деля в форме Россера применима к любому непротиворечивому рекурсивно аксиоматизируемому расширению теории S.

Если принимать тезис Ч¸рча, то последнее следствие утверждает, что теория S существенно неполна, т.е., что любое непротиворечивое эффективно аксиоматизированное расширение теории S имеет неразрешимые предложения.

Список литературы

1.Арбиб М. Мозг, машина и математика. — М.: Наука, 1968.

2.Берж К. Теория графов и ее приложения. — М.: Изд-во иностр. лит., 1962.

3.Биркгоф Г. Теория решеток. — М.: Наука, 1984.

4.Булос Дж., Джеффри Р. Вычислимость и логика. — М.: Мир, 1994.

5.Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. — М.: Наука, 1979.

6.Гиндикин С. Г. Алгебра логики в задачах. — М.: Наука, 1972.

7.Глушков В. М. Введение в кибернетику. — К.: Èçä-âî ÀÍ ÓÑÑÐ, 1964.

8.Горбатов В. А. Основы дискретной математики. — М.: Высш. шк., 1986.

9.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

10.Донской В. И. Дискретная математика. — Симферополь: СОНАТ, 2000.

11.Ершов Ю. А., Палютин Е. А. Математическая логика. — М.: Наука, 1979.

12.Заде Л. Понятие лингвистической переменной и его применение к принятию проблемных решений. — М.: Мир, 1976.

13.Карри Х. Б. Основания математической логики. — М.: Мир, 1969.

14.Клини С. К. Введение в метаматематику. — М.: Мир, 1957.

15.Клини С. К. Математическая логика. — М.: Мир, 1973.

16.Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. — М.: Èçä-âî Ìîñê. óí-òà, 1982.

17.Кофман А. Введение в теорию нечетких множеств. — М.: Радио и связь, 1982.

18.Коэн П. Дж. Теория множеств и континуум-гипотеза. — М.: Мир, 1973.

19.Кузин Л. Т. Основы кибернетики: В 2 т. — Т. 2. — М.: Энергия, 1979.

20.Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергия, 1980.

21.Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.

22.Кэррол Л. История с узелками. — М.: Мир, 1973.

23.Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975.

24.Линдон Р. Заметки по логике. — М.: Мир, 1968.

25.Логический подход к искусственному интеллекту / Тейз Ф., Грибомон П., Луи Ж. и др. — М.: Мир, 1990.

26.Мальцев А. И. Алгебраические системы. — М.: Наука, 1975.

27.Манин. Ю. И. Вычислимое и невычислимое. — М.: Сов. Радио, 1980.

28.Мендельсон Э. Введение в математическую логику. — М.: Наука, 1976.

29.Нагель Э., Ньюмен Д. Теорема Геделя. — М.: Знание, 1970.

30.Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992.

31.Новиков П. С. Элементы математической логики. — М.: Физматгиз, 1959.

32.Ньюсом К. В., Ивс Г. О математической логике и философии математики. — М.: Знание. 1968.

33.Оре О. Теория графов. — М.: Наука. 1968.

34.Робертс Ф. С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. — М.: Наука, 1986.

35.Столл Р. Множество, логика, аксиоматические теории. — М.: Просвещение, 1968.