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

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

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

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

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

Подмножество $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

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

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