Насколько я понимаю, поскольку это не вычислимо, оно не может остановиться, когда ответ будет «да» или «нет». Вот почему он не может быть рекурсивно перечислимым, поскольку он не может гарантировать, что он всегда останавливается на «нет».
Что-то невычислимо, может ли оно быть ко-рекурсивно перечислимым?
Ответы (1)
Проблема может быть невычислимой, но при этом быть ко-рекурсивно перечислимой.
У вычислимых, разрешимых или рекурсивных множеств есть ТМ, которые всегда могут остановиться, либо приняв, либо отвергнув любой ввод.
Невычислимые множества все еще могут быть полуразрешимыми, рекурсивно перечислимыми или ко-рекурсивно перечислимыми, если они имеют НП, которые могут останавливаться, принимая все в наборе (при этом, возможно, вообще не останавливаясь, когда входные данные не находятся в наборе) или отбрасывая все, что есть. не в наборе (хотя, возможно, вообще не останавливается, когда вход находится в наборе).
Ясно, что если множество одновременно рекурсивно перечислимо и ко-рекурсивно перечислимо, оно является рекурсивным (вычислимым, разрешимым), поскольку вы можете запускать обе ТМ — одну, которая в конечном итоге останавливается, принимая, другую, которая в конечном итоге останавливается, отклоняя — и вы знайте, что один из двух в конечном итоге даст вам правильный ответ.
person
Patrick87
schedule
30.11.2018
