Вычислимый набор

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

Невычислимое множество называется невычислимым или неразрешимым.

Более общий класс множеств, чем вычислимые, состоит из вычислимо перечислимых (с.п.) множеств, также называемых полуразрешимыми множествами. Для этих наборов требуется только наличие алгоритма, который правильно определяет, когда число находится в наборе; алгоритм может не дать ответа (но не неправильного ответа) для чисел, не входящих в набор.

• 1 Формальное определение
• 2 Примеры и не примеры
• 3 свойства
• 4 ссылки
• 5 Внешние ссылки

Подмножество из натуральных чисел называется вычислимой, если существует общая вычислимую функцию таким образом, что, если и, если. Другими словами, множество вычислим тогда и только тогда, когда индикаторная функция является вычислимой. ${\ displaystyle S}$ ${\ displaystyle f}$${\ displaystyle f (x) = 1}$${\ displaystyle x \ in S}$${\ displaystyle f (x) = 0}$${\ Displaystyle х \ notin S}$${\ displaystyle S}$ ${\ displaystyle \ mathbb {1} _ {S}}$

Примеры:

• Каждое конечное или кофинитное подмножество натуральных чисел вычислимо. Сюда входят следующие особые случаи:
  • Пустое множество вычислит.
  • Весь набор натуральных чисел вычислим.
  • Каждое натуральное число ( как определено в стандартной теории множеств ) вычислимо; то есть, набор натуральных чисел, меньших заданного натурального числа, вычислим.
• Подмножество простых чисел вычислимо.
• Рекурсивный язык вычислимого подмножество формального языка.
• Множество чисел Гёделя арифметических доказательств, описанных в статье Курта Гёделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем I», вычислимо; см. теоремы Гёделя о неполноте.

Не примеры:

• Набор останавливающихся машин Тьюринга не вычислим.
• Класс изоморфизма двух конечных симплициальных комплексов невычислим.
• Набор занятых бобров-чемпионов не поддается вычислению.
• Десятая проблема Гильберта не вычислима.

Если A - вычислимое множество, то дополнение к A - вычислимое множество. Если A и B вычислимые множества, то A ∩ B, A ∪ B и образ A × B при использовании функции спаривания Кантора являются вычислимыми множествами.

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

А представляет собой множество вычислимы тогда и только тогда, когда он находится на уровне от арифметической иерархии. ${\ displaystyle \ Delta _ {1} ^ {0}}$

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

• Катленд, Н. Вычислимость. Издательство Кембриджского университета, Кембридж-Нью-Йорк, 1980. ISBN   0-521-22384-9 ; ISBN   0-521-29465-7
• Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость, MIT Press. ISBN   0-262-68052-1 ; ISBN   0-07-053522-1
• Соаре Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Берлин, 1987. ISBN   3-540-15299-7

• Сахаров Алексей. «Рекурсивный набор». MathWorld.