Введение
В теории вычислимости и теории вычислительной сложности, RE (рекурсивно перечислимый) – это класс задач, для которых ответ "да" может быть проверен машиной Тьюринга за конечное время. Неформально это означает, что если ответ на экземпляр задачи – "да", то существует процедура, которая за конечное время определяет это, и эта процедура никогда не выдает ложноположительный результат ("да"), когда истинный ответ – "нет". Однако, если истинный ответ – "нет", процедура не обязана завершаться; она может уйти в "бесконечный цикл" для некоторых случаев, когда ответ "нет". Такая процедура иногда называется полуалгоритмом, чтобы отличать её от алгоритма, который определяется как полное решение задачи принятия решения. Аналогично, co-RE – это множество всех языков, являющихся дополнениями к языкам из RE. В некотором смысле, co-RE содержит языки, для которых можно конечно доказать отсутствие членства, но доказательство членства может занять неограниченное время.
Эквивалентное определение
Аналогичным образом, RE – это класс задач принятия решений, для которых машина Тьюринга может перечислить все экземпляры, отвечающие "да", один за другим (именно это и означает термин "перечислимый"). Каждый элемент RE является рекурсивно перечисляемым множеством и, следовательно, диофантовым множеством. Чтобы показать эквивалентность, заметим, что если существует машина, перечисляющая все принимаемые входные данные, то другая машина, принимающая строку на вход, может запускаться и принимать, если эта строка была перечислена. И наоборот, если машина принимает входные данные, принадлежащие языку, то другая машина может перечислить все строки этого языка, чередуя симуляции работы первой машины на всех возможных входных данных и выводя те строки, которые были приняты (существует порядок выполнения, который в конечном итоге достигнет каждого шага вычисления, поскольку существует счетное количество упорядоченных пар "вход-шаг").
Отношения с другими классами
Набор рекурсивных языков (R) является подмножеством как RE, так и co RE. Фактически, это пересечение этих двух классов, поскольку любую задачу, для которой существует распознаватель и со-распознаватель, можно решить, просто попеременно запуская их, пока один из них не выдаст результат. Следовательно:
Напротив, множество языков, которые не являются ни RE, ни co RE, известно как NRNC. Это множество языков, для которых невозможно доказать ни принадлежность, ни непринадлежность за конечное время, и оно включает в себя все остальные языки, не входящие ни в RE, ни в co RE. То есть:
Не только эти задачи неразрешимы, но ни они, ни их дополнение не являются рекурсивно перечислимыми. В январе 2020 года в препринте было объявлено о доказательстве эквивалентности RE классу MIP* (классу, в котором классический верификатор взаимодействует с несколькими всемогущими квантовыми доказателями, разделяющими запутанность); пересмотренное, но еще не прошедшее полную проверку доказательство было опубликовано в Communications of the ACM в ноябре 2021 года. Это доказательство подразумевает, что проблема вложения Коннеса и проблема Цирельсона неверны.
Conversely, the set of languages that are neither RE nor co RE is known as NRNC. These are the set of languages for which neither membership nor non membership can be proven in a finite amount of time, and contain all other languages that are not in either RE or co RE. That is:
Not only are these problems undecidable, but neither they nor their complement are recursively enumerable. In January of 2020, a preprint announced a proof that RE was equivalent to the class MIP* (the class where a classical verifier interacts with multiple all powerful quantum provers who share entanglement); a revised, but not yet fully reviewed, proof was published in Communications of the ACM in November 2021. The proof implies that the Connes embedding problem and Tsirelson's problem are false.