Проблема может быть невычислимой, но все же может быть ко-рекурсивно перечисляемой.
У вычислимых, разрешимых или рекурсивных наборов есть ТМ, которые всегда могут быть остановлены при принятии или отклонении любого ввода.
Не вычислимонаборы все еще могут быть полуразрешимыми, рекурсивно перечислимыми или ко-рекурсивно перечислимыми, если у них есть ТМ, которые могут останавливаться, принимая все в наборе (хотя, возможно, не останавливаясь вообще, когда входные данные не находятся в наборе) или отклоняя все, что не являетсяв наборе (хотя, возможно, вообще не может остановиться, когда вход находится в наборе).
Ясно, что если набор является и рекурсивно перечислимым, и ко-рекурсивно перечислимым, он является рекурсивным (вычислимым, разрешимым) поскольку вы можете запустить обе ТМ - одну, которая в конечном итоге останавливается при принятии, а другую, которая в конечном итоге останавливается при отклонении, - и вы знаете, что одна из двух в конечном итоге даст вам правильный ответ.