Вычислимое множество

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

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

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

Формальное определение

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

Примеры и не примеры

Примеры:

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

Непримеры:

Основная статья: Список неразрешимых проблем

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

Свойства

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

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

A является вычислимым множеством тогда и только тогда, когда оно находится на уровне $\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
• Соаре, Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Шпрингер-Верлаг, Берлин, 1987 г. ISBN   3-540-15299-7

Внешние ссылки

• Сахаров, Алексей . «Рекурсивный набор» . Математический мир .