Является ли дополнение к не регулярному языку всегда рекурсивным языком?

Question

Является ли дополнение к не регулярному языку всегда рекурсивным языком?

Я понимаю, что 1. Языки безконтекста не закрываются под дополнением. 2.перечисленные перечислимые языки не закрываются под дополнением. 3. Рекурсивные языки действительно закрыты под дополнением.

Но как я могу ответить на первоначальный вопрос, используя эти факты? Как я могу определить, является ли нерегулярный язык рекурсивным или нет?

Answer 1

Нет, дополнение к нерегулярному языку не всегда рекурсивно. Контрпример - проблема остановки, дополнение которой (все программы, которые не останавливаются) является нерегулярным. Таким образом, сама проблема остановки, которая не является рекурсивной (но рекурсивно перечислимой), является дополнением к нерегулярному языку. (Я думаю, что упомянутые факты не помогут вам с этой проблемой.)

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