Математическая логика и теория алгоритмов (120

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

искомым решением нашей задачи. Может случиться, однако, что работа длится вечно (ниже будут даны примеры такого рода); тогда задача остается нерешенной. В ближайших разделах мы опишем типичные задачи, а также уточним понятие алгоритма.

Основные задачи теория алгоритмов. Пусть N = {0,1,...},

Nn — множество всех векторов x = (x1,...,xn),xi N. Будем рассматривать функции f: D(f) → N, где D(f) Nn (D(f) —

это область определения функции f). Если D(f) = N, то функцию f называют тотальной. Иногда мы будем вместо множества N использовать множество N+ = {1,2,...}.

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

Будем говорить, что данная программа вычисляет функцию f, если для любого вектора x D(f) она выдает f(x) при x D(f) и выдает сообщение «не определена» при x / D(f). Назовем функцию вычислимой, если существует вычисляющая ее программа.

Будем говорить, что данная программа полувычисляет функцию f, если для любого x D(f) она выдает f(x), а для любого x / D(f) работает бесконечно. Функцию, для которой существует такая программа, называют полувычислимой. Ясно, что вычислимая функция полувычислима; в дальнейшем мы увидим, что обратное неверно.

Обратимся к задаче распознавания множества. Пусть дано множество E Nn. Требуется указать алгоритм, который позволил бы для каждого вектора x Nn выяснить, принадлежит ли он данному множеству. Эта задача сводится к вычислению функции κE, заданной равенствами κE(x) = 1 при x E и κE(x) = 0 при x / E. Она называется характеристической функцией (а также индикатором) множества E.

Множество E Nm называют разрешимым, если его характеристическая функция вычислима; т. е. существует программа, которая, получив на свой вход любой вектор x Nm, работает конечное время и выдает 1 при x E, выдает 0 при x / E. Множество называется перечислимым, если существует программа, которая для каждого вектора x E выдает единицу, а для каждого x / E работает вечно.

31

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Его левую часть обозначим через F(x,y). Пусть E есть множество таких чисел x N+, для которых оно имеет корень y N+. Мы стремимся создать программу, распознающую множество E. Начнем с «наивной» попытки, которая приведет лишь к частичному решению этой задачи. Вот эта программа. «Возьми x N+ и выписывай числа F(x,1),F(x,2),... Если в этой цепочке появится число 0 (т. е. F(x,y) = 0 для некоторого y N+), то остановись и положи κ(x) = 1, т. е. x E». Отметим, что если для данного x уравнение (3.1) не имеет решений в натуральных числах, то работа продолжится вечно.

Прежде чем перейти ко второй программе, исследуем уравнение (3.1). Перепишем уравнение (3.1) в виде

Отсюда xy5 < 2x3y + y2; сокращая на y, получим xy4 < 2x3 + + y. Отметим, что величины 1 и y не превосходят величины y3;

поэтому xy4 < 2x3y3 + y3. Отсюда y < 2x3 +1 x

y 2x2 + 1 x,y N+, удовлетворяющих уравнению (3.1).

Мы приходим к следующей программе. «Возьми x N+ и выписывай числа F(x,1),...,F(x,2x2 + 1). Если в этой цепочке появилось число 0, то остановись и положи κ(x) = 1. В противном случае положи κ(x) = 0». Эта программа «лучше» первой: она работает конечное время для любого x и вычисляет (не только полувычисляет) функцию κ(x).

3.2. Машина с неограниченными регистрами. Тезис Черча¨

Описание машины с неограниченными регистрами. Данное выше расплывчатое описание алгоритма можно формализовать многими способами. Мы сделаем это, используя понятие машины с неограниченными регистрами (МНР).

Машина с неограниченными регистрами — это бесконечная вправо лента, разбитая на квадратики R1,R2,..., называемые регистрами. Впишем в них числа r1,r2,..., такие, что ri = 0

32

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

для достаточно больших i. Последовательность r1,r2,... назовем конфигурацией. Зададим программу P (ее называют МНРпрограммой), т. е. конечную цепочку команд P : I1,...,Is, каждая из которых будет перерабатывать конфигурации. Имеются четыре типа команд (их называют МНР-командами): 1) команда обнуления Z(k),k = 1,2,..., заменяет содержание регистра Rk (т. е. число rk) нулем; 2) команда прибавления единицы S(k) заменяет число rk числом rk + 1; 3) команда переадресации T(m,n) заменяет число rn числом rm; 4) команда условного переход J(m,n;k) работает так. Сравниваем числа rm,rn; если rm = rn, то выполняем команду Ik; если же rm = rn, то выполняем следующую команду программы.

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

Вычисление функций. Возьмем какую-либо программу P,

вектор (x1,...,xn)и рассмотрим конфигурацию (x1,...,xn,0,...). Предположим, что программа P выдала заключительную конфигу-

рацию (y1,...,yn). Нас будет интересовать лишь число y1. В итоге получили функцию y1 = f(x1,...,xn); ее область определения состоит из векторов (x1,...,xn), для которых программа работает конечное время. Функцию, полученную описанным способом, назовем МНР-вычислимой.

Пример 3.2. Возьмем программу

P : I1 = J(1,2,4); I2 = S(1); I3 = J(1,1,1).

Для любого n она вычисляет функцию f(x1,...,xn). Мы опишем

только функцию f(x1,x2).

Начнем применять программу к конфигурции (x1,x2,0,...). Если x1 = x2 = x, то команда I1 отошлет нас к несуществующей команде I4; работа остановится, и мы получим f(x,x) = x.

Пусть теперь x1 < x2. Тогда выполнится команда I2, что приведет к конфигурации (x1 + 1,x2,0,...). Если x1 + 1 = x2, то произойдет остановка, откуда f(x1,x2) = x2. Если x1 +1 < x2, то работа продолжится и на некотором шаге значение x1, постепенно возрастая, сравнится со значением x2. Тогда работа остановится и мы получим f(x1,x2) = x2.

33

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Пусть, наконец, x1 > x2. Тогда значение x1 будет увеличиваться неограниченно, программа работает вечно. Итак, получили следующую функцию: f(x1,x2) = x2 при x1 x2, не определена

при x1 > x2.

Упражнение 3.1. Выясните, какую функцию вычисляет каждая из сдедующих программ:

P1 : I1 = J(1,2,7);I2 = S(2);I3 = J(1,2,7);

I4 = S(2);I5 = S(3);I6 = J(1,1,1);I7 = T(3,1);

P2 : I1 = J(1,2,5);I2 = S(2);I3 = S(2);I4 = J(1,1,1);

I5 = T(1,1).

Упражнение 3.2. Убедитесь, что программа

P : I1 = J(3,2,5); I2 = S(1); I3 = S(3); I4 = J(1,1,1)

вычисляет функцию x1 + x2.

Следующие два упражнения более сложные (и более увлекательные).

Упражнение 3.3. Запишите программу, полувычисляющую следующую функцию: f(x) = x, если x нечетно, и не определена, если x четно.

Упражнение 3.4. Составьте программу, вычисляющую функ-

цию max(x1,x2).

Две полувычислимые (в частности, вычислимые) функции

f1,f2 называются рваными, если D(f1) = D(f2) и f1(x) = f2(x) при x D(f1); в этом случае f1 = f2.

Другие определения вычислимости; тезис Черча¨. Наряду с МНР были придуманы и другие средства задавать алгоритмы для вычисления функций: машина Тьюринга, машина Поста и др. Однако все эти средств оказались равносильными; другими словами, если некоторая функция вычислялась одной из этих машин, то она с успехом вычислялась и любой другой. Было высказано следующее утверждение, называемое тезисом Черча:¨ любая функция, вычислимая каким-либо алгоритмом (не обязательно связанным с какой-либо машиной), может быть вычислена также с помощью каждой из известных машин, например с помощью МНР. Отныне мы принимаем на веру этот тезис. Таким образом, если мы хотим проверить вычислимость некоторой функции, достаточно указать

34

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

какой-либо вычисляющий ее алгоритм, не обязательно связанный с МНР. Если такой алгоритма найден, то найдется и нужный алгоритм на МНР.

3.3. Задачи нумерации и перечисления множеств

Нумерация и перечисление. Далее мы употребляем термин «алгоритм» для любой процедуры (не только для вычисления функции), заданной конечной цепочкой команд. Тезис Черча¨ говорит, что все алгоритмы можно свести к алгоритмам на МНР, хотя такое свед´ение иногда дается непросто. Таким образом, этот тезис дает «свободу действий» при работе с алгоритмами; он позволяет применять любые средства для составления алгоритмов (например, можно использовать сразу несколько экземпляров МНР и т. д.).

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

Возьмем бесконечное множество X. Нумеровать его означает задать (с помощью некоторого алгоритма) такую последовательность x(1),x(2),...,x(i),... X, в которой каждый элемент x X встречается ровно один раз; если это возможно, то множество называется счетным. Нумерация множества X дает биекцию {1,2,...} → X. Иногда удобнее писать нумерацию в виде x(0),x(1),... Если множество X конечно, то нумерация дает его биекцию на множество чисел {1,...,n} для некоторого n N.

Перечислить множество X означает задать алгоритм построения последовательности x(1),x(2),..., такой, что любой элемент x X встречается в ней хотя бы один раз. Эту последовательность назовем перечисляющей.

Приведем примеры нумераций и перечислений множеств. Ограничимся множествами X, состоящими из векторов, координаты которых — целые положительные числа (т. е. принадлежат множеству N+); (число координат произвольно). Предварительно введем понятия «меньше» и «больше» (т. е. способ сравнения)

для любых двух векторов x = (x1,...,xm) и y = (y1,...,yn) из множества X согласно следующим правилам. Если m < n,

то будем считать, что вектор x меньше вектора y (записываем

35

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

это как x < y). Если m = n, то мы считаем, что x < y при выполнении одного из следующих условий: либо x1 < y1, либо

x1 = y1,...,xi = yi,xi+1 < yi+1 для некоторого i.

Пример 3.3. Пусть X — конечное множество векторов x = = (x1,...xn),xi N; здесь число n не фиксировано (допускаются два вектора с одним и тем же числом n).

Используя введенное выше сравнение векторов, расположим векторы их множества X в порядке возрастания: x(1) < x(2) < ...

Тем самим мы перенумеровали множество X.

Пример 3.4. Пусть X — произвольное множество векторов (x1,...,xn),xi N (как и в примере 3.3, n не фиксировано); перенумеруем множество X. Для любого числа r N возьмем

множество Em = {(x1,...,xn): x1 +...+xn = r} и выстроим его элементы в цепочку так, как объяснялось в примере 3.3. Проделав

это последовательно для E1,E2,..., получаем искомую нумерацию x(1),x(2),...,x(k) N∞.

Пример 3.5. Пусть множества X,Y перенумерованы; таким образом, X = {x1,x2,...}, Y = {y(1),y(2),...}. Тогда множество X1 Y можно перенумеровать так: x(1),y(1),x(2),y(2),... Аналогично нумеруется объединение любого конечного набора нумерованных множеств.

Пример 3.6. Перенумеруем множество всех МНР-команд. Команды обнуления и прибавления единицы уже перенумерованы. Далее множества команд переноса T(m,n) и условного перехода J(m,n,k) отождествляются с множествами векторов (m,n) и (m,n,k), поэтому они могут быть перенумерованы (см. пример 3.4). Но тогда можно перенумеровать и множество всех МНРкоманд (см. пример 3.5), т. е. записать его в виде цепочки I1,I2,...

Пример 3.7. Перенумеруем множество всех программ. Программа — это цепочка команд Ii1 ,Ii2 ,...,Iin; она отождествляется с цепочкой чисел i1,...,in. Используя пример 3.4, можно перенумеровать все программы, т. е. выстроить их в цепочку P0,P1,...

Следующий пример — наиболее важный.

Пример 3.8. Обозначим через F1 множество всех вычислимых функций одной переменной. Построим для F1 перечисляющую последовательность. Для каждого числа y = 1,2,... возьмем программу Py; вычисляемую ею функцию обозначим через fy. Получим цепочку функций f1,f2,... Это и есть искомое перечисление

36

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

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

3.4. Некоторые свойства разрешимых и перечислимых множеств

Приведем здесь формулировки некоторых свойств разрешимых и перечислимых множеств (часть из них читатель должен доказать самостоятельно).

1. Докажем, что объединение перечислимых множеств перечислимо.

Пусть множества A,B перечислимы и пусть PA,PB — это программы, полувычисляющие их индикаторы. Составим программу, используя два экземпляр МНР; на первом из них будет работать программа PA, на другом — PB. «Возьми любой x N и применяй команды программы PA и PB поочередно: команды PA — в моменты времени 1,3,..., команды PB — в моменты времени 2,4,... Если хотя бы одна из программ закончит работу, прерви работу обеих МНР и положи κ(x) = 1». Полученная функция и есть искомый индикатор κA B. (Если x / A B, то программа работает вечно.)

2. Пусть G N2 — разрешимое множество, E = Pr(G) (Pr означает проекцию на первую координату); таким образом, E = {x N: y,(x,y) G}. Докажем, что множество E перечислимо.

Для доказательства используем следующую программу: «Возьми любое x N. Рассмотри последовательно точки (x,y),y = = 1,2,... и проверяй, верно ли утверждение (x,y) G. Если для некоторого y это выполнено, остановись и запиши x E». (Отметим, что если x / E, то работа будет длиться вечно.) Это и есть програма перечисления множества E.

3. Покажем, что верно и обратное, т. е. для любого перечислимого множества E N существует такое разрешимое множество G N2, что E = Pr(G). Пусть P есть программа, полувычисляющая функцию κE(x). Зададим множество G следующей программой: «Возьми (x,y) и начни применять программу P к (x,1),(x,2),... Если она остановится не позже чем через y шагов, остановись и положи κG(x,y) = 1. В противном случае также

37

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

остановись и положи κG(x,y) = 0». Проверьте, что G — искомое множество.

4.Пусть E — перечислимое множество. Построим такую тотальную вычислимую функцию h(x), что E = {h(1),h(2),...} (т. е. функция h «перечисляет» множество E — отсюда и название «перечислимое»). Возьмем такое разрешимое множество G N2,

что E = Pr(G) (см. свойство 2). Зафиксируем элемент a E и возьмем биекцию φ : N → N2 (см. пример 3.4). Зададим функ-

цию h(x) следующей программой: «Возьми x и рассмотри точку φ(x) = (u,v). Если (u,v) G, положи h(x) = u; если (u,v) / G, положи h(x) = a». Это и есть искомая функция.

5.Возьмем тотальную вычислимую функцию f : Nm → N.

Тогда множество E = {x : f(x) = 0} разрешимо (составьте программу, вычисляющую κE).

6.Докажите, что пересечение перечислимых множеств перечислимо и что объединение и пересечение разрешимых множеств разрешимы.

7.Докажите, что область определения вычислимой функции разрешима, область определения полувычислимой функции перечислима.

8.Докажите, что если множество и его дополнение перечислимы, то оба они разрешимы. (У к а з а н и е: используйте два экземпляра МНР и запустите на них программы, полувычисляющие индикаторы указанных множеств.)

9.Выпишите первые три вычислимые функции из цепочки, построенной в примере 3.8 (и соответствующие программы).

Вычислимость в других областях. Все понятия, введенные выше для множества N, переносятся на множества Z, Q (целые и рациональные числа). Для этого достаточно перенумеровать (с помощью некоторого алгоритма) множества Z и Q (проделайте это!) и отождествить элементы этих множеств с их номерами. Это позволит отождествить множества Z и Q с множества N, для которого нужная теория уже построена.

Из тезиса Черча¨ следует, что операции сложения, умножения и деления, примененные к классу вычислимых функций, не выводят из этого класса; все рациональные функции вычислимы.

38

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

3.5. Алгоритмическая разрешимость и неразрешимость

Неперечислимость множества тотальных вычислимых функций. В примере 3.8 мы построили (с помощью некоторого алгоритма) цепочку f1,f2,..., содержащую все вычислимые функции (некоторые функции входят в цепочку более одного раза). Рассмотрим все тотальные функции в этой цепочке; обозначим через F множество их номеров. Покажем, что F неперечислимо; таким образом, не существует алгоритма, который мог бы «породить» все тотальные функции.

Допустим, что множество F перечислимо. Тогда согласно доказанному выше свойству существует такая тотальная вычислимая функция h, множество значений которой есть F. Рассмотрим функцию g(x,y) = fh(x)(y). Она вычислима (ибо вычислимы h и fh(x)),

ииз нее получается любая тотальная вычислимая функция переменной y при выборе некоторого значения x. Рассмотрим функцию

g(y,y)+1. Для нее также найдется такое значение x0, что g(y,y)+ +1 = g(x0,y) для всех y N. Взяв y = x0, приходим к нелепости g(x0,x0) + 1 = g(x0,x0). Вывод: множество F неперечислимо.

Проблема остановки; алгоритмическая разрешимость. Мы видели на примерах, что данная программа может работать с некоторыми x N (точнее, с конфигурациями (x,0,...)) вечно. Возникает следующая проблема. Пусть дана программа P. Требуется описать множество E тех x N, для которых она будет работать над переменной x конечное время; описать множество означает указать программу, вычисляющую его индикатор. Это

иесть проблема остановки МНР. Доказывается (рассуждениями, близкими к тем, какие мы использовали в предыдущем абзаце), что для некоторых программ P множество E неразрешимо (мы уже знаем, что оно перечислимо), поэтому такой программы не существует. Это есть пример алгоритмически неразрешимой проблемы.

39

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

4.НЕЧEТКИЕ МНОЖЕСТВА И НЕЧЕТКАЯ ЛОГИКА

4.1.Нечеткие множества

Нечетко заданные элементы; функции достоверности.

Пусть X — непустое множество. Предположим, вы желаете выбрать элемент x X, обладающий некоторым свойством P, однако располагаете лишь неполной информацией относительно того, какой же из элементов обладает этим свойством. Точнее, предположим, что для каждого x X дана величина μ(x) — степень достоверности того, что x обладает свойством P. Множество пар {x, μ(x)} и называется нечетко заданным элементом (НЗЭ) множества; функцию μ называется функцией достоверности.

Иногда целесообразно придать функции μ другой смысл: считать, что μ(x) показывает, в какой мере элемент x обладает свойством P. Если функция μ принимает только значения 1 и 0, то она задает множество A = {x : μ(x) = 1}; оно состоит из элементов со свойством P. Если же μ может принимать значения, отличные от 1 и 0, то множество A не определено. Тем не менее удобно считать, что и в этом случае эта функция задает нечеткое множество A по следующему правилу: элемент x X принадлежит ему с достоверностью (степенью уверенности) μ(x). В силу сказанного естественно назвать НЗЭ (т. е. множество пар {x; μ(x)}) также нечетким множеством (НМ), функцию достоверности назвать функцией принадлежности элементов этому нечеткому множеству

иобозначить через μA(x). Нечеткое множество A записывается

ввиде A = {x, μA(x)}. Таким образом, НЗЭ и НМ — это одно

ито же. Единственный случай, когда НМ можно отождествить с обычным множеством, — это случай функции достоверности (или, что то же самое, принадлежности), принимающей только значения 1 и 0.

Пример 4.1. Рассмотрим нечеткое множество малых чисел множества X = {1,2,...,6}; таким образом, упомянутое выше свойство P есть «малость» числа. Можно, к примеру, задать это нечеткое множество как

A = {1;0,9 , 2;0,9 , 3;0,6 , 4;0,2 , 5;0,1 , 6;0,03}.

Нечеткие переменные; лингвистические переменные. Нечетко заданный элемент называют также нечеткой переменной

40