Вычислимый набор - Computable set
В теории вычислимости , А набор из натуральных чисел называются вычислимым , рекурсивным или разрешимым , если существует алгоритм , который принимает число в качестве входных данных, завершается после конечного количества времени (возможно , в зависимости от заданного числа) и правильно решает , является ли число принадлежит набору или нет.
Невычислимое множество называется невычислимым или неразрешимым .
Более общий класс множеств, чем вычислимые, состоит из вычислимо перечислимых (с.п.) множеств , также называемых полуразрешимыми множествами. Для этих наборов требуется только наличие алгоритма, который правильно определяет, когда число находится в наборе; алгоритм может не дать ответа (но не неправильного ответа) для чисел, не входящих в набор.
Формальное определение
Подмножество из натуральных чисел называется вычислимой , если существует общая вычислимую функцию таким образом, что , если и , если . Другими словами, множество вычислим тогда и только тогда , когда индикаторная функция является вычислимой .
Примеры и не примеры
Примеры:
- Каждое конечное или кофинитное подмножество натуральных чисел вычислимо. Сюда входят следующие особые случаи:
- Пустое множество вычислит.
- Весь набор натуральных чисел вычислим.
- Каждое натуральное число ( как определено в стандартной теории множеств ) вычислимо; то есть, набор натуральных чисел, меньших заданного натурального числа, вычислим.
- Подмножество простых чисел вычислимо.
- Рекурсивный язык вычислимого подмножество формального языка .
- Множество чисел Гёделя арифметических доказательств, описанных в статье Курта Гёделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем I», вычислимо; см. теоремы Гёделя о неполноте .
Не примеры:
- Набор останавливающихся машин Тьюринга не вычислим.
- Класс изоморфизма двух конечных симплициальных комплексов невычислим.
- Набор занятых бобров-чемпионов не поддается вычислению.
- Десятая проблема Гильберта не вычислима.
Характеристики
Если A - вычислимое множество, то дополнение к A - вычислимое множество. Если A и B вычислимые множества, то A ∩ B , A ∪ B и образ A × B при использовании функции спаривания Кантора являются вычислимыми множествами.
Вычислимое множество тогда и только тогда , когда А и дополнение в А оба с . Прообраз вычислимого множества при полной вычислимой функции является вычисляемым множеством. Образ вычислимого множества при полной вычислимой биекции вычислим. (В общем, образ вычислимого множества при вычислимой функции - это ce, но, возможно, не вычислимый).
А представляет собой множество вычислимы тогда и только тогда , когда он находится на уровне от арифметической иерархии .
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