Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Разрешимость и перечислимость множеств

Разрешимость и перечислимость множеств


Теперь, когда мы достаточно подробно изучили три различных формализации понятия алгоритма, установили их эквивалентность и сформулировали тезисы Тьюринга, Чёрча и Маркова, можно сделать некоторые общие выводы. Из наших рассмотрений следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из трех формализации, верны и в Другой. Это означает, что возможно развитие и изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия "алгоритм". Это своего рода общая теория алгоритмов. Основные ее понятия — алгоритм и вычислимая функция.


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


Будем рассматривать функции f от одного или нескольких аргументов, заданные на множестве N=\{0,1,2,3,4,\ldots,n,\ldots\} всех натуральных чисел или на некоторых его подмножествах (частичные функции) и принимающие значения в множестве N. Таким образом, рассматриваются функции f, являющиеся отображениями декартовой n-й степени N^n в множество N. Область определения Df функции f есть подмножество множества N^n=N\times\ldots\times N\colon Df=\{(x_1,\ldots,x_n)\colon\, f(x_1,\ldots,x_n) — определено}. Область изменения (значений) f есть подмножество множества N\colon


If= \bigl\{y\in N\colon\, (\exists x_1,\ldots,x_n)(f(x_1,\ldots,x_n)=y)\bigr\}.

Определение 35.1. Функция f(x_1,\ldots,x_n) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех наборов аргументов, для которых она определена, и работающий вечно, если функция для данного набора значений аргументов не определена.


Пусть M\subseteq N^n=N\times\ldots\times N.


Определение 35.2. Множество M называется разрешимым, если существует алгоритм A_M, который по любому объекту a дает ответ, принадлежит a множеству Мили нет. Алгоритм A_M называется разрешающим алгоритмом для M.


Известно понятие характеристической функции множества M. Ею называется функция \chi_M, заданная на множестве M, принимающая значения в двухэлементном множестве \{0;1\} и определяемая следующим образом:


\chi_M(x_1,\ldots,x_n)= \begin{cases}0,&\text{if}\quad (x_1,\ldots,x_n)\notin M;\\ 1,&\text{if}\quad (x_1,\ldots,x_n)\in M. \end{cases}

Отсюда ясно, что множество M разрешимо тогда и только тогда, когда его характеристическая функция \chi_M вычислима.


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


Пусть теперь M\subseteq N.


Определение 35.3. Множество M\subseteq N называется (рекурсивно, или эффективно, или алгоритмически) перечислимым, если M либо пусто, либо есть область значений некоторой вычислимой функции или, другими словами, если существует алгоритм для последовательного порождения (перечисления) всех его элементов.


Другими словами, M перечислимо, если существует такая вычислимая функция \varphi_M(x), что a\in M \Leftrightarrow (\exists x)(a=\varphi_M(x)). Функция \varphi_M называется перечисляющей множество M (или для множества M); соответственно алгоритм, вычисляющий \varphi_M, называется перечисляющим или порождающим для M.


Пример 35.4. Рассмотрим множество М=\{1,4,9,16,25,36, \ldots\} квадратов натуральных чисел. Оно перечислимо: для получения его элементов нужно последовательно брать числа 1,2,3,4,\ldots и возводить их в квадрат. Другими словами, M есть область значений вычислимой функции f(x)=x^2\colon M=\{1^2,2^2, 3^2, 4^2, \ldots\}. Более того, это множество является также и разрешимым: для проверки того, принадлежит или нет некоторое число данному множеству, нужно разложить число на простые множители, что позволит выяснить, является ли оно точным квадратом.


Далее, в теореме 35.6 будет показано, что любое разрешимое множество перечислимо, а в теореме 35.7 — что обратное утверждение неверно.


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


Теорема 35.5. Если множества M и L перечислимы, то перечислимы множества M\cup L и M\cap L.


Доказательство. Если имеются алгоритмы для порождения элементов множеств M и L, то алгоритм для порождения множества M\cup L получается из исходных путем их одновременного применения. Следовательно, множество M\cup L перечислимо.


Пусть теперь алгоритм \Omega_M последовательно порождает элементы m_1,m_2,m_3,\ldots множества m, а алгоритм \Omega_L последовательно порождает элементы l_1,l_2,l_3,\ldots множества L. Тогда алгоритм для перечисления элементов множества M\cap L заключается в следующем.


Поочередно с помощью алгоритмов \Omega_M и \Omega_L порождаются элементы m_1,l_1,\, m_2,l_2,\, m_3,l_3 и т.д. Каждый вновь порожденный элемент m_i сравнивается со всеми ранее порожденными элементами l_j. Если m_i совпадает с одним из них, то он включается во множество M\cap L. В противном случае надо переходить к порождению элемента l_i и сравнивать его со всеми ранее порожденными элементами m_j, и т.д. Описанная процедура позволяет эффективно перечислить все элементы множества M\cap L, что и требовалось доказать.


Теорема 35.6. Пусть M\subseteq N. Множество M разрешимо тогда и только тогда, когда оно само и его дополнение \overline{M} перечислимы.


Доказательство. Необходимость. Пусть M — разрешимое множество. Можем считать, что M\ne \varnothing, т. е. имеется элемент a\in M. Тогда характеристическая функция \chi_M множества M, как было отмечено выше, вычислима, т.е. имеется алгоритм для ее вычисления.


Строим алгоритм для перечисления множества M. Рассмотрим функцию


f(x)= \begin{cases}x,&\text{if}\quad \chi_M(x)=1,\\ a,&\text{if}\quad \chi_M(x)=0. \end{cases}

Отсюда M=\{f(0), f(1), f(2), f(3),\ldots\}, то есть M есть множество значений функции f, которая, очевидно, вычислима ввиду вычислимости функции \chi_M(x). Следовательно, множество M перечислимо.


Аналогично, выбрав элемент b\notin M, строим функцию:


g(x)= \begin{cases}b,&\text{if}\quad \chi_M(x)=1,\\ x,&\text{if}\quad \chi_M(x)=0, \end{cases}

которая также вычислима ввиду вычислимости функции \chi_M(x). Кроме того, \overline{M}=\{g(0), g(1), g(2), g(3),\ldots\}, т.е. \overline{M} есть множество значений вычислимой функции g. Следовательно, множество \overline{M} также перечислимо.


Достаточность. Пусть множества M и \overline{M} перечислимы, т. е. M=\{f(0), f(1), f(2), f(3),\ldots\} и \overline{M}=\{g(0), g(1), g(2), g(3),\ldots\}, где f и g — некоторые вычислимые функции. Тогда алгоритм, выясняющий, принадлежит или нет произвольное число n множеству M, действует следующим образом. Последовательно порождаем элементы f(0),g(0),\, f(1),g(1),\, f(2),g(2),\ldots и на каждом шаге получаемый элемент сравниваем с n. Поскольку n должно принадлежать либо M, либо \overline{M}, то на конечном шаге получим f(k)=n или g(k)=n. Если f(k)=n, то n\in M, а если g(k)=n, то n\in \overline{M} и, значит, n\notin M. Следовательно, множество M разрешимо.


Прежде чем переходить к следующей теореме, отметим, что существует эффективное перечисление всех упорядоченных пар натуральных чисел, которое называется диагональным методом, или диагональным процессом:


\begin{matrix}\begin{array}{lllllllllll}(0,0)& & (1,0)& & (2,0)& & (3,0)& & (4,0)& & \ldots\\ ~~\downarrow& \nearrow & & \nearrow & & \nearrow & & \nearrow & & \nearrow & \\ (0,1)& & (1,1)& & (2,1)& & (3,1)& & (4,1)& & \ldots\\ & \nearrow & & \nearrow & & \nearrow & & \nearrow & & \nearrow & \\ (0,2)& & (1,2)& & (2,2)& & (3,2)& & (4,2)& & \ldots\\ & \nearrow & & \nearrow & & \nearrow & & \nearrow & & & \\ \end{array}\\[-4pt] \ldots\ldots\ldots \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots.. \end{matrix}

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


(0,0),~ (0,1),~(1,0),~(0,2),~(1,1),~(2,0),~ (0,3),~ \ldots

Можно доказать, что в данной последовательности пара (m,n) стоит на месте с номером


C(m,n)= \frac{m^2+2mn+n^2+3m+n+2}{2}\,.

Теорема 35.7. Существует перечислимое, но неразрешимое множество натуральных чисел.


Доказательство. На основании предыдущей теоремы достаточно привести пример такого множества {U} натуральных_чисел, которое само было бы перечислимо, а его дополнение \overline{U} перечислимым не было.


Ясно, что перечислимых множеств натуральных чисел (как и алгоритмов) имеется лишь счетное количество. Следовательно, все перечислимые множества можно расположить в последовательность (перенумеровать): M_0,M_1,M_2,\ldots. Более того, можно считать, что эта нумерация эффективна, т.е. по номеру множества можно восстановить само это множество.


Рассмотрим теперь алгоритм \Omega, который последовательно порождает все элементы следующего множества {U}. На шаге с номером C(m,n) этот алгоритм вычисляет m-й элемент множества M_n, и если элемент совпадает с n, то он относит его в множестве {U}. Таким образом,


n\in U\quad \Leftrightarrow\quad n\in M_n,

Итак, {U} порождается алгоритмом \Omega, т.е. {U} перечислимо. Поскольку дополнение \overline{U} множества {U} состоит из всех таких n, что n\notin M, то {U} отличается от любого перечислимого множества хотя бы одним элементом. Поэтому \overline{U} не является перечислимым. Следовательно, на основании теоремы 35.6 множество {U} неразрешимо, что и завершает доказательство.


Доказанная теорема фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики, о которой мы подробно будем говорить в заключительном параграфе этой главы.


Подведем некоторые итоги. Итак, эффективно заданное множество — это множество, обладающее разрешающей или перечисляющей функцией (алгоритмом). Объединение и пересечение перечислимых множеств перечислимы. Непустое множество M\subseteq N разрешимо тогда и только тогда, когда оно само и его дополнение перечислимы. В частности, отсюда следует, что всякое непустое разрешимое множество перечислимо. Тем не менее существует перечислимое, но неразрешимое множество натуральных чисел. В теореме 35.7 такое множество описано. Другим примером такого множества является множество M=\{x\colon\, A_x(x) определен}, т.е. множество номеров самоприменимых алгоритмов.


Таким образом, перечислимость — более слабый вид эффективности, нежели разрешимость. Хотя перечисляющая процедура и задает эффективно список элементов множества M, поиск данного элемента а в этом списке может оказаться неэффективным: это неопределенно долгий процесс, который в конечном счете остановится, если a\in M, но не остановится, если a\notin M. В случае же перечислимости и дополнения \overline{M} перечисляющая процедура для M становится эффективной и гарантирует разрешимость множества M.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved