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

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

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

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

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

Подмножество натуральных чисел называется вычислимым, если существует полная вычислимая функция такая, что if и if . Другими словами, множество вычислимо тогда и только тогда, когда вычислима индикаторная функция . $S$ $е$ $f(x)=1$ $x\in S$ ${\ displaystyle 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 является вычислимым множеством тогда и только тогда, когда оно является либо диапазоном неубывающей полной вычислимой функции, либо пустым множеством. Образ вычислимого множества при неубывающей тотальной вычислимой функции вычислим.

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

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