2011-gre-cs-practice-book.pdf/Q70

Вопрос: Q70-08c765

Если L₁ - разрешимый язык, а L₂ - неразрешимый язык, то язык L₁ ∪ L₂ , который является объединением L₁ и L₂ , будет являться

Ответы

• Правильный ответ: бесконечным, но, возможно, разрешимый и, возможно, неразрешимый
• возможно конечный и, возможно, бесконечный, но определенно разрешимый
• возможно конечный и, возможно, бесконечный, но определенно неразрешимый
• бесконечный и разрешимый
• бесконечный и неразрешимый

Объяснение

Исходники — вопрос 70 на 48 странице книги «2011-gre-cs-practice-book.pdf»

Определения

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

• Неразрешимость языка , означает, что не существует машины Тьюринга, которая могла бы определить принадлежность для каждой строки в языке (в нашем случае L₂).

Что происходит при объединении

• Поскольку L₁ разрешим, оно может содержать конечные или бесконечные элементы и он сам по себе конечен.
• Неразрешимость L₂ означает, что он обладает свойством, заключающимся в том, что невозможно полностью классифицировать принадлежность его элементов. В связи с этим мы также не можем говорить и о его конечности.

Поэтому, если мы включим все элементы из L₂ в L₁ ,способа определить принадлежность для всех элементов из L₂ нет (поскольку L₂ неразрешимо). Таким образом, если L₂ добавляет какие-либо элементы в объединение, объединенное объединение сохраняет неразрешимость. - L₁ ∪ L₂, безусловно, будет неразрешимым , потому что, если бы вы могли разрешить L₁ &cup L₂, вы также могли бы разрешить L₂ , поскольку L₂ является частью L₁ ∪ L₂ , что противоречит тому факту, что L₂ неразрешимо.

Решение

Пусть мы пытаемся определить, находятся ли x в L₁ ∪ L₂. Первой идеей было бы попробовать запустить М₁(машина Тьюринга для языка L₁) на x, и если он не принимает, то запустить М₂(машина Тьюринга для языка L₂) на x. Но М₁ не гарантированно остановится на x, и мы все равно хотели бы принять x, если М₂ примет его. Таким образом, решение состоит в том, чтобы запускать М₁ и М₂ параллельно, переключаясь между выполнением того или другого. Если в какой–то момент вычисления М₁ принимает x, значит x входит в L₁ ∪ L₂; если ни один из них не принимает, то это может продолжаться вечно.

Следовательно язык L₁ ∪ L₂ бесконечный (так как мы не можем ничего сказать о конечности языка L₂ ), но, возможно, разрешимый (если х входит в L₁) и, возможно, неразрешимый (если х не входит в L₁)

Задача зарезервирована: Evvnes 08:39, 19 декабря 2024 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.