Введение
Математическая логическая концепция
В теории вычислимости множество S натуральных чисел называется вычислимо перечислимым (c. e.), рекурсивно перечислимым (r. e.), полуразрешимым, частично разрешимым, перечисляемым, доказуемым или Тьюринг-распознаваемым, если:
Существует алгоритм, такой что множество входных чисел, для которых алгоритм завершается, является точно S.
Или, эквивалентно,
Существует алгоритм, который перечисляет элементы S. Это означает, что его выход представляет собой просто список всех элементов S: s1, s2, s3, … Если S бесконечно, этот алгоритм будет выполняться бесконечно. Первое условие объясняет, почему иногда используется термин "полуразрешимый". Более точно, если число принадлежит множеству, это можно определить, запустив алгоритм, но если число не принадлежит множеству, алгоритм будет выполняться бесконечно, и никакой информации не будет возвращено. Множество, которое "полностью разрешимо", является вычислимым множеством. Второе условие объясняет, почему используется термин "вычислимо перечислимый". Сокращения c. e. и r. e. часто используются, даже в печати, вместо полной фразы. В теории вычислительной сложности класс сложности, содержащий все вычислимо перечислимые множества, обозначается RE. В теории рекурсии решетка вычислимо перечислимых множеств относительно включения обозначается .
Формальное определение
Множество S натуральных чисел называется вычислимо перечислимым, если существует частично вычислимая функция, область определения которой совпадает точно с S, то есть функция определена тогда и только тогда, когда ее аргумент принадлежит S.
Примеры
Каждое вычислимое множество вычислимо перечислимо, но неверно, что каждое вычислимо перечислимое множество вычислимо. Для вычислимых множеств алгоритм должен также указывать, не принадлежит ли вход множеству – это не требуется для вычислимо перечислимых множеств. Рекурсивно перечислимый язык – это вычислимо перечислимое подмножество формального языка. Множество всех доказуемых утверждений в эффективно представленной аксиоматической системе является вычислимо перечислимым множеством. Теорема Матиясевича утверждает, что каждое вычислимо перечислимое множество является диофантовым множеством (обратное утверждение тривиально верно). Простые множества вычислимо перечислимы, но не вычислимы. Творческие множества вычислимо перечислимы, но не вычислимы. Любое продуктивное множество не является вычислимо перечислимым. При заданной нумерации Гёделя вычислимых функций, множество (где – функция Кантора, а указывает, что функция определена) является вычислимо перечислимым (см. рисунок для фиксированного x). Это множество кодирует проблему останова, поскольку оно описывает входные параметры, для которых каждая машина Тьюринга останавливается. При заданной нумерации Гёделя вычислимых функций, множество является вычислимо перечислимым. Это множество кодирует проблему определения значения функции. Для заданной частичной функции f из натуральных чисел в натуральные числа, f является частично вычислимой функцией тогда и только тогда, когда её график, то есть множество всех пар , таких что f(x) определено, является вычислимо перечислимым.
Свойства
Если A и B являются вычислимо перечислимыми множествами, то A ∩ B, A ∪ B и A × B (с упорядоченной парой натуральных чисел, отображаемой на одно натуральное число функцией Кэнтора) являются вычислимо перечислимыми множествами. Прообраз вычислимо перечислимого множества под частичной вычислимой функцией является вычислимо перечислимым множеством. Множество называется ко-вычислимо перечислимым или ко-в.п., если его дополнение является вычислимо перечислимым. Эквивалентно, множество является ко-в.п. тогда и только тогда, когда оно находится на определенном уровне арифметической иерархии. Класс сложности ко-вычислимо перечислимых множеств обозначается co RE. Множество A вычислимо, если и только если и A, и дополнение к A вычислимо перечислимы. Некоторые пары вычислимо перечислимых множеств эффективно разделимы, а некоторые – нет.
Замечания
Согласно тезису Черча-Тьюринга, любая эффективно вычислимая функция вычислима машиной Тьюринга, и, следовательно, множество S является вычислимо перечислимым тогда и только тогда, когда существует алгоритм, выдающий перечисление S. Однако это нельзя рассматривать как формальное определение, поскольку тезис Черча-Тьюринга — это неформальное предположение, а не формальная аксиома. В современных текстах распространено определение вычислимо перечислимого множества как области частной функции, а не области значений тотальной вычислимой функции. Этот выбор обусловлен тем, что в обобщенных теориях рекурсии, таких как α-рекурсия, определение, соответствующее областям определения, оказалось более естественным. В других текстах используется определение через перечисления, которое эквивалентно для вычислимо перечислимых множеств.