КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Перечислимые и разрешимые множества
При использовании далее терминов «алгоритм», «вычислимая функция» имеется в виду любая возможная их формализация в терминах машин Тьюринга, нормальных алгорифмов или рекурсивных функций. Все рассматриваемые множества – суть подмножества натурального ряда. Дополнением множества MÌ N является множество N\ M. Определение 5.1.1. Множество MÌ N называется разрешимым, если существует алгоритм, позволяющий для каждого nÎ N определить, принадлежит ли это число множеству M или нет. Такой алгоритм называется разрешающим для множества M. В иной терминологии это определение формулируется так. Определение 5.1.1*. Множество MÌ N называется разрешимым, если его характеристическая функция: является общерекурсивной. Теорема 5.1.1. Если множества А и В разрешимы, то разрешимы множества N\ А, АÈВ, АÇВ. Доказательство. Если характеристические функции и – общерекурсивны, то и характеристические функции множеств N\ А, АÈВ, АÇВ: , . также являются общерекурсивными функциями. Теорема 5.1.2. Любое конечное множество MÌ N – разрешимо. Определение 5.1.2. Непустое множество MÌ N перечислимо, если существует алгоритм, перечисляющий (порождающий) его элементы. Этот алгоритм называют порождающим алгоритмом для множества M. Пустое множество считается перечислимым по определению. В терминологии рекурсивных функций приведенное определение формулируется так. Определение 5.1.2*. Непустое множество MÌ N перечислимо, если существует общерекурсивная функция j M (x) такая, что: M={ y: y=j M (x), xÎ N }. Теорема 5.1.3. Если множества А и В перечислимы, то перечислимо множество АÈВ. Доказательство. Положим Так как функция rest (x, 2) нахождения остатка от деления x на 2 является общерекурсивной (доказательство этого факта остается за читателем), то общерекурсивной будет и функция:
, где – целая часть числа . В этом случае множество АÈВ={ y: , xÎ N } по определению будет перечислимым. ¨Теорема доказана. Теорема 5.1.4. Если множества А и В перечислимы, то перечислимо множество АÇВ. Доказательство. Введем в рассмотрение следующие функции: 1) функцию ограниченного вычитания: 2) функции большого размаха:
где . 3) где: j A (x) – общерекурсивная функция, порождающая множество A; j B (x) – общерекурсивная функция, порождающая множество B; Все перечисленные функции являются общерекурсивными, и потому общерекурсивной функцией будет функция j AÇB (x)=j A (n(s(x))), порождающая множество AÇB. ¨Теорема доказана. Теорема 5.1.5. Непустое разрешимое множество MÌ N перечислимо. Доказательство. Пусть – характеристическая функция множества MÌ N, . Тогда функция является общерекурсивной и порождающей множество М. Если М={ m0, m1, m2, …, mn,.. } и m0,<m1<m2 <…<mn, то график функции имеет вид: Теорема 5.1.6. Множество MÌ N разрешимо тогда и только тогда, когда Mи N\ М перечислимы. Доказательство. Если множество M разрешимо, то по теореме 5.1 разрешимо его дополнение N\ М. По теореме 5.4 перечислимы оба множества. В одну сторону теорема доказана. Пусть далее Mи N\ М перечислимы, что означает существование общерекурсивных функций j М, j N\ М. Определим общерекурсивную функцию s(x), значением которой является наименьшее число z, при котором либо j М (z)= x, либо j N\ М (z)= x, следующим образом: . Тогда характеристическая функция множества М может быть записана так:. Так как:общерекурсивная функция, то теорема доказана. Следствие. Если множество M перечислимо, но неразрешимо, то множество N\ М не перечислимо. Теорема 5.1.7. Множество записей машин Тьюринга является перечислимым множеством.
Теорема 5.1.8. Множество записей самоприменимых машин Тьюринга перечислимо, но не разрешимо. Следствие. Дополнение множества записей самоприменимых машин Тьюринга неперечислимо.
Дата добавления: 2014-01-06; Просмотров: 699; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |