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

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

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

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

Формальное определение [ править ]

Подмножество из натуральных чисел называется вычислимой , если существует общая вычислимую функцию таким образом, что , если и , если . Другими словами, множество вычислим тогда и только тогда , когда индикаторная функция является вычислимой .${\ 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 .