Существуют ли счетные множества, которые не являются вычислимо перечислимыми?

Множество является счетным, если оно имеет биекцию с натуральными числами, и вычислимо перечислимо (ce), если существует алгоритм, который перечисляет его членов.

Любое не конечное вычислимо перечислимое множество должно быть счетным, поскольку мы можем построить биекцию из перечисления.

Есть ли примеры счетных множеств, которые не являются вычислимо перечислимыми? Таким образом, существует биекция между этим множеством и натуральными числами, но нет алгоритма, который мог бы вычислить эту биекцию.

Есть ли примеры счетных множеств, которые не перечислимы?

Да. Все подмножества натуральных чисел являются счетными, но не все из них перечислимы. (Доказательство: существует бесчисленное множество различных подмножеств  но только счетное количество машин Тьюринга, которые могут выступать в качестве перечислителей.) Таким образом, любое подмножество  N, которое вы уже знаете, не является рекурсивно перечислимым, является примером - например, набор всех чисел, кодирующих Тьюринг. машины, которые останавливаются для каждого входа.$\mathbb{N}$$\mathbb{N}$

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

Например, рассмотрим, что множество .$L = \{(x,M) \mid M \text{ does not halt on input } x \}$

Предположим, у нас есть алгоритм, который может перечислять членов этого набора. Если бы такой алгоритм существовал, мы могли бы использовать его для решения проблемы остановки со входами , используя следующий алгоритм:$x,M$

• Переключение между работает машина для п шагов по х и перечисления п - й член L .$M$$n$$x$$n$$L$

либо останавливается, либо не останавливается на x . Если оностановится, в конце концов мы найдем n, где мы достигнем состояния остановки. Если он не остановится, то в конечном итоге мы достигнем ( M , x ) в нашем перечислении.$M$$x$$n$$(M,x)$

Таким образом, у нас есть сокращение, и мы можем сделать вывод, что такого перечисления не существует.

Обратите внимание, что такие перечисления могут существовать для полуразрешимых задач. Например, вы можете перечислить набор всех пар ввода остановки машины, перечислив все возможные трассировки всех выполнений машины Тьюринга после шагов, и отфильтровать те, которые не заканчиваются в состоянии остановки. $n$

$\Sigma^*$$\Sigma = \{0,1\}$$L \subseteq \Sigma^*$$\Sigma^*$