Перечислимые множества их свойства
Оценка 5

Перечислимые множества их свойства

Оценка 5
Научно-исследовательская работа +4
docx
информатика
Взрослым
17.02.2017
Перечислимые множества их свойства
Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество[1]) — множество конструктивных объектов(например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называетсякорекурсивно перечислимым[2]. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню арифметической иерархии (англ.), а корекурсивно перечислимые — уровню Всякое разрешимое множество является перечислимым. Перечислимое множество является разрешимым, тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножествоперечислимого множества может не быть перечислимым (и даже может не быть арифметическим).
перечислимые множества их свойства.docx
перечислимые множества их свойства ии ои ии  рекурс вно  ии [1]) — множество конструктивных   (эффект вно перечислимое, ии Перечисл мое мн жество перечислимое, полуразреш мое множество объектов(например, натуральных чисел), все элементы которого могут быть получены с  помощью некоторого алгоритма. Дополнение перечислимого множества  называетсякорекурсивно перечислимым[2]. Всякое перечислимое множество  является арифметическим. Корекурсивно перечислимое множество может не быть  перечислимым, но всегда является арифметическим. Перечислимые множества  соответствуют уровню  перечислимые — уровню   арифметической иерархии (англ.), а корекурсивно  Всякое разрешимое множество является перечислимым. Перечислимое множество  является разрешимым, тогда и только тогда, когда его дополнение также перечислимо.  Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножествоперечислимого множества  может не быть перечислимым (и даже может не быть арифметическим). Совокупность всех перечислимых подмножеств  совокупность всех неперечислимых подмножеств   является счётным множеством, а   — несчётным. Варианты определения. Различным формализациям представления об алгоритме отвечают  различные формальные определения понятия перечислимого множества, оказывающиеся  эквивалентными. Так, на основе понятия рекурсивной функции перечислимые  множества натуральных чисел могут быть определены как образы частично рекурсивных  функций одной переменной (поэтому перечислимые множества натуральных чисел иногда  называют «рекурсивно перечислимыми множествами»). Аналогично, перечислимые  множества слов в некотором алфавите A могут быть введены как множества результатов  работы машин Тьюринга с внешним алфавитом A, или как множества являющихся словами  в алфавите A результатов работы нормальных алгоритмов над алфавитом A. В теории алгоритмов доказывается утверждение о том, что областями значений алгоритмов могут служить перечислимые множества, и только они. Это позволяет ввести ещё один  эквивалентный способ определения понятия перечислимого множества. Так,  перечислимыми множествами натуральных чисел могут считаться области значений  рекурсивных функций, множествами слов — области применимости машин  Тьюринга или нормальных алгоритмов с соответствующими алфавитами. Рекурсивно­перечислимые и рекурсивные множества Имеется несколько эквивалентных формулировок, определяющих понятие рекурсивного и  рекурсивно­перечислимого множества целых     чисел. Для удобства мы соберем их в таблицу так, что в левой половине этой таблицы будут находиться определения рекурсивно­ перечислимого множества, а в правой — определения рекурсивного множества. Сделаем теперь относительно этих определений несколько замечаний: Замечание относительно  общерекурсивной функцией с повторениями, то оно может быть пересчитано и без  повторений (некоторой другой общерекурсивной функцией). . Доказано, что если некоторое множество можно пересчитать  Замечание относительно  . Покажем, как определение   вытекает из  . Пусть С —  множество значений некоторой общерекурсивной функции  . Тогда тот факт, что  некоторое число у принадлежит множеству С, означает, что существует такое  , что иначе Равенство  общерекурсивных функций:  может рассматриваться как общерекурсивное отношение равенства двух где Замечание относительно  . Определение   является лишь уточнением определения  Замечание относительно ЗБ. Из выполнения условия ЗБ следует выполнение условия  . .  Действительно, пусть множество С перечисляется общерекурсивной функцией  , а С —  функцией  . Для того чтобы узнать, принадлежит ли данное число множеству С, будем параллельно  вычислять последовательности Так как число у принадлежит либо С, либо С, то оно рано или поздно должно встретиться  или в ряду I, или в ряду II. Если оно встретилось в ряду I,  , если в II —  имеется алгоритм распознавания принадлежности любого у множеству С. . Поэтому  Замечание относительно  принадлежности любого у множеству С. Действительно, будем вычислять  . При условии   также имеется алгоритм распознавания  последовательность  . Если при некотором  , то процессу вычисления можно  остановить и сделать вывод, что  ; если же встретится   такое, что  , то  . Приведем примеры рекурсивных множеств: 1) Двухэлементное множество   рекурсивно в силу условий   или  . 2) Любое конечное множество рекурсивно в силу условий   или  . 3) Множество четных       чисел   рекурсивно. Здесь  , и множество рекурсивно в силу  условия   или  , и множество рекурсивно в силу условия  . Приведем теперь примеры рекурсивно­перечислимых и не рекурсивно­перечислимых  множеств. Согласно определению   рекурсивно­перечислимым множеством будет множество тех у, для которых  при некотором общерекурсивном  . Можно так подобрать  , что  множество  будет множеством тех у, для которых  будет рекурсивно­перечислимым, но не рекурсивным; его дополнение    (где Q — общерекурсивный предикат); это множество  будет не рекурсивно и не рекурсивно­перечислимо. Множество гёделевских номеров z тех систем Е, которые определяют общерекурсивную  функцию, не рекурсивно и не рекурсивно­перечислимо. В заключение заметим, что из сравнения  множество как рекурсивно, так и рекурсивно­перечислимо, следует, что любое  рекурсивное множество есть рекурсивно­перечислимое множество. Обратное утверждение  неверно.  и из того факта, что любое конечное    Понятие о рекурсивных действительных важно при выяснении того, может ли машина «делать» что­либо большее, чем  реализовывать заданный алгоритм. Выше было показано, что любой алгоритм сводится к  подсчету значений вычислимой целочисленной функции.     числах и о рекурсивно­перечислимых множествах  Если какое­либо устройство «выдает» на выходе множество чисел, и если это множество  не является рекурсивно­перечислимым, то это свидетельствует о том, что процесс работы  этого устройства не может быть алгоритмизирован, т. е. что устройство «делает больше,  чем реализует алгоритм».

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства

Перечислимые множества их свойства
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
17.02.2017