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

Концепция в теории вычислимости

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

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

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

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

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

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

Примеры:

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

Не примеры:

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

Характеристики

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

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

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

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

Смотрите также

• Рекурсивно перечислимый язык
• Рекурсивный язык
• Рекурсия

Ссылки

• Катланд, Н. Вычислимость. Cambridge University Press, Кембридж-Нью-Йорк, 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 .