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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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


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


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

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


Пусть [math]M\subseteq N^n=N\times\ldots\times N[/math].


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


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


[math]\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}[/math]

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


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


Пусть теперь [math]M\subseteq N[/math].


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


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


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


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


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


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


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


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


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


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


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


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


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

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


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


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

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


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


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


[math]\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 & & \nearrow & \\ \multicolumn{11}{l}{\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots} \end{array}[/math]

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


[math](0,0),~ (0,1),~(1,0),~(0,2),~(1,1),~(2,0),~ (0,3),~ \ldots[/math]

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


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

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


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


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


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


[math]n\in U\quad \Leftrightarrow\quad n\in M_n,[/math]

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


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


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


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


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


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

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