Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Разрешимое множество

Из Википедии — свободной энциклопедии

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

Более общее определение таково: множество разрешимо, если существует алгоритм, который по любому объекту даёт ответ на вопрос, принадлежит он данному множеству или нет. Таким образом, разрешимое множество — это множество с алгоритмически разрешимой проблемой вхождения.

Множество, не являющееся разрешимым, называется неразреши́мым.

Множество является разрешимым, если и только если его характеристическая функция вычислима. Согласно тезису Чёрча, вычислимость характеристической функции означает её частичную рекурсивность. А значит, и её вычислимость по Тьюрингу. Поэтому разрешимое множество называют также частично рекурсивным (или рекурсивным) множеством.

Также можно говорить о разрешимом множестве, состоящем из любых конструктивных объектов, кодируемых натуральными числами. Любое разрешимое множество является перечислимым и арифметическим. Разрешимые множества соответствуют уровню арифметической иерархии[англ.].

В общем случае, подмножество множества конструктивных элементов называется разрешимым относительно , если существует алгоритм, применимый к объектам из и в случае применения к некоторому объекту дающий ответ на вопрос, принадлежит ли этот объект [1].

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

Совокупность всех разрешимых подмножеств является счётным множеством, а совокупность всех неразрешимых подмножеств  — несчётным, так как множество всех подмножеств положительных целых чисел несчётно.[2]

Существует взаимно однозначное соответствие между вычислимыми подмножествами и вычислимыми вещественными числами [2].

Энциклопедичный YouTube

  • 1/3
    Просмотров:
    1 619
    809
    1 403
  • Основы вычислимости и теории сложности, лекция 1
  • Дипломный фильм Натальи Дерюгиной «От мостов Кёнигсберга до сборки генома»
  • 2015_12_24 - 23, 24 лек. А.В.Савватеева - Перестановки: циклы, чётность, порядок ч. 1/3

Субтитры

Примеры

  • Пустое множество является разрешимым.
  • Любое конечное множество и его дополнение являются разрешимыми множествами.
  • Существуют бесконечные разрешимые множества с бесконечным дополнением. Например, множество всех чётных чисел и множество всех простых чисел являются разрешимыми.
  • Дополнение разрешимого множества является разрешимым.
  • Объединение и пересечение конечного числа разрешимых множеств также являются разрешимыми.
  • Любое перечислимое множество, дополнение которого также перечислимо, является разрешимым (теорема Поста).
  • Множество рациональных чисел, меньших числа , является разрешимым.
  • Множество, единственный элемент которого равен единице, если гипотеза Римана верна, и нулю в противном случае, является разрешимым (так как оно конечно).
  • Множество номеров нетривиальных нулей ζ-функции, для которых нарушается гипотеза Римана, является разрешимым (хотя неизвестно, является ли оно пустым, конечным или бесконечным).
  • Множество строк, являющихся правильными доказательствами в ZFC, разрешимо. Его проекция — множество утверждений, доказуемых в ZFC — перечислимо, но, при условии непротиворечивости ZFC — неразрешимо.

Примечания

  1. Эббинхауз, 1972, с. 19.
  2. 1 2 Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375—376

Литература

  • Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М.: Мир, 1972. — 262 с.
Эта страница в последний раз была отредактирована 4 сентября 2023 в 09:17.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).