Операции, при которых класс неразрешимых языков не закрыт

12

Существуют ли неразрешимые языки, так что их язык объединения / пересечения / сцепления является разрешимым? Какова физическая интерпретация такого примера, потому что в целом неразрешимые языки не закрыты под этими операциями?

Что мы можем сказать о закрытии клини? У нас тоже есть примеры для этого? Т.е. может ли быть решено закрытие неразрешимого языка?

Кроме того, можем ли мы обобщить такие неразрешимые классы?

Дэвид Ричерби
источник

Ответы:

21

Да, пусть будет двоичным кодированием задачи остановки и , , затем (почему?)HA=0H1{0,1}{ϵ}B=1H0{0,1}{ϵ}AB={0,1}

sdcvvc
источник
9

Мы знаем, что язык остановки неразрешим. Пусть H будет его двоичной кодировкой. Мы также можем утверждать, что дополнение к H неразрешимо. Следовательно, объединение / пересечение H и HComp - это и , которые разрешимы.Σϕ


источник
9

То же самое касается звезды Клини (замыкание Клини):

установить где - проблема остановки. явно неразрешима и , что является правильным (то есть разрешимым).HP=HP{0,1}HPHP(HP)=Σ

Ран Г.
источник
1

Ран показал, что неразрешимые языки не закрываются при операции звезды Клина; но они также не закрыты при простой «собственной» конкатенации ( ); например:LL=L2={xyx,yL}

L={1}{2n}{2n+1nHalt}

L неразрешима, но разрешима.L2

Вор
источник