Пример языка, который не является рекурсивно перечислимым, и его дополнительный язык также не является RE

Question

Пример языка, который не является рекурсивно перечислимым, и его дополнительный язык также не является RE

Только язык, о котором я не могу думать, который не принадлежит классу RE, является диагональным языком, но, к сожалению, его дополнительный язык рекурсивно перечислим. У кого-нибудь есть какие-либо идеи?

1

formal-languages chomsky-hierarchy

Источник

user1987852 23 ноя '13 в 14:43

1 ответ

Решение

Другие вопросы по тегам formal-languages chomsky-hierarchy

user847269 16 дек '13 в 16:21 2013-12-16 16:21 · Accepted Answer · 2013-12-16 16:21

Рассмотрим следующий набор: все машины, которые не могут остановиться на некотором входе. Другими словами, все машины M, для которых существует вход X, такой, что M не останавливается на входе X. Это не является рекурсивно перечисляемым, так как нет алгоритмического способа определить, что данная машина не может остановиться на данном входе. Я имею в виду, как бы вы это сделали? Имитировать работу машины на входе? На сколько долго?

Дополнение этого набора следующее: все машины, которые останавливаются на всех входах. Другими словами, все машины M, которые всегда останавливаются на любом входе X. Это также не является рекурсивно перечисляемым, поскольку нет алгоритмического способа определить, что данная машина останавливается на всех возможных входах. Как бы вы это сделали? Проверь их всех?