2011-gre-cs-practice-book.pdf/Q70 — различия между версиями
Материал из DISCOPAL
Evvnes (обсуждение | вклад) |
Evvnes (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Вопрос: Q70-08c765 == | == Вопрос: Q70-08c765 == | ||
| − | < | + | Если L<sub>1</sub> - разрешимый язык, а L<sub>2</sub> - неразрешимый язык, то язык L<sub>1</sub> ∪ L<sub>2</sub> , который является объединением L<sub>1</sub> и L<sub>2</sub> , будет являться |
| − | + | ||
| − | + | ||
| − | + | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
| − | * Правильный ответ: | + | * Правильный ответ: бесконечным, но, возможно, разрешимый и, возможно, неразрешимый |
| − | * | + | * возможно конечный и, возможно, бесконечный, но определенно разрешимый |
| − | * | + | * возможно конечный и, возможно, бесконечный, но определенно неразрешимый |
| − | + | * бесконечный и разрешимый | |
| − | + | * бесконечный и неразрешимый | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | |||
| − | |||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|48|70}} | |
| + | |||
| + | ''Определения'' | ||
| + | * Разрешимость языка , означает, что существует машина Тьюринга, которая может однозначно определить, находится ли любая заданная строка в языке(в нашем случае L<sub>1</sub>) или нет, за конечный промежуток времени. | ||
| + | |||
| + | * Неразрешимость языка , означает, что не существует машины Тьюринга, которая могла бы определить принадлежность для каждой строки в языке (в нашем случае L<sub>2</sub>). | ||
| + | |||
| + | ''Что происходит при объединении'' | ||
| + | |||
| + | * Поскольку L<sub>1</sub> разрешим, оно может содержать конечные или бесконечные элементы и он сам по себе конечен. | ||
| + | * Неразрешимость L<sub>2</sub> означает, что он обладает свойством, заключающимся в том, что невозможно полностью классифицировать принадлежность его элементов. В связи с этим мы также не можем говорить и о его конечности. | ||
| + | |||
| + | Поэтому, если мы включим все элементы из L<sub>2</sub> в L<sub>1</sub> ,способа определить принадлежность для всех элементов из L<sub>2</sub> нет (поскольку L<sub>2</sub> неразрешимо). Таким образом, если L<sub>2</sub> добавляет какие-либо элементы в объединение, объединенное объединение сохраняет неразрешимость. | ||
| + | - L<sub>1</sub> ∪ L<sub>2</sub>, безусловно, будет неразрешимым , потому что, если бы вы могли разрешить L<sub>1</sub> &cup L<sub>2</sub>, вы также могли бы разрешить L<sub>2</sub> , поскольку L<sub>2</sub> является частью L<sub>1</sub> ∪ L<sub>2</sub> , что противоречит тому факту, что L<sub>2</sub> неразрешимо. | ||
| + | |||
| + | ''Решение'' | ||
| + | |||
| + | Пусть мы пытаемся определить, находятся ли x в L<sub>1</sub> ∪ L<sub>2</sub>. Первой идеей было бы попробовать запустить М<sub>1</sub>(машина Тьюринга для языка L<sub>1</sub>) | ||
| + | на x, и если он не принимает, то запустить М<sub>2</sub>(машина Тьюринга для языка L<sub>2</sub>) на x. Но М<sub>1</sub> не гарантированно остановится на x, | ||
| + | и мы все равно хотели бы принять x, если М<sub>2</sub> примет его. Таким образом, решение состоит в том, чтобы запускать М<sub>1</sub> и М<sub>2</sub> | ||
| + | параллельно, переключаясь между выполнением того или другого. Если в какой–то момент вычисления | ||
| + | М<sub>1</sub> принимает x, значит x входит в L<sub>1</sub> ∪ L<sub>2</sub>; если ни один из них не принимает, то это может продолжаться вечно. | ||
| − | + | Следовательно язык L<sub>1</sub> ∪ L<sub>2</sub> бесконечный (так как мы не можем ничего сказать о конечности языка L<sub>2</sub> ), но, возможно, разрешимый (если х входит в L<sub>1</sub>) и, возможно, неразрешимый (если х не входит в L<sub>1</sub>) | |
| − | + | ||
| − | + | ||
| − | |||
{{question-ok|}} | {{question-ok|}} | ||
{{reserve-task|[[Участник:Evvnes|Evvnes]] 08:39, 19 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Evvnes|Evvnes]] 08:39, 19 декабря 2024 (UTC)}} | ||
Версия 11:20, 19 декабря 2024
Вопрос: Q70-08c765
Если L1 - разрешимый язык, а L2 - неразрешимый язык, то язык L1 ∪ L2 , который является объединением L1 и L2 , будет являться
Ответы
- Правильный ответ: бесконечным, но, возможно, разрешимый и, возможно, неразрешимый
- возможно конечный и, возможно, бесконечный, но определенно разрешимый
- возможно конечный и, возможно, бесконечный, но определенно неразрешимый
- бесконечный и разрешимый
- бесконечный и неразрешимый
Объяснение
Исходники — вопрос 70 на 48 странице книги «2011-gre-cs-practice-book.pdf»
Определения
- Разрешимость языка , означает, что существует машина Тьюринга, которая может однозначно определить, находится ли любая заданная строка в языке(в нашем случае L1) или нет, за конечный промежуток времени.
- Неразрешимость языка , означает, что не существует машины Тьюринга, которая могла бы определить принадлежность для каждой строки в языке (в нашем случае L2).
Что происходит при объединении
- Поскольку L1 разрешим, оно может содержать конечные или бесконечные элементы и он сам по себе конечен.
- Неразрешимость L2 означает, что он обладает свойством, заключающимся в том, что невозможно полностью классифицировать принадлежность его элементов. В связи с этим мы также не можем говорить и о его конечности.
Поэтому, если мы включим все элементы из L2 в L1 ,способа определить принадлежность для всех элементов из L2 нет (поскольку L2 неразрешимо). Таким образом, если L2 добавляет какие-либо элементы в объединение, объединенное объединение сохраняет неразрешимость. - L1 ∪ L2, безусловно, будет неразрешимым , потому что, если бы вы могли разрешить L1 &cup L2, вы также могли бы разрешить L2 , поскольку L2 является частью L1 ∪ L2 , что противоречит тому факту, что L2 неразрешимо.
Решение
Пусть мы пытаемся определить, находятся ли x в L1 ∪ L2. Первой идеей было бы попробовать запустить М1(машина Тьюринга для языка L1) на x, и если он не принимает, то запустить М2(машина Тьюринга для языка L2) на x. Но М1 не гарантированно остановится на x, и мы все равно хотели бы принять x, если М2 примет его. Таким образом, решение состоит в том, чтобы запускать М1 и М2 параллельно, переключаясь между выполнением того или другого. Если в какой–то момент вычисления М1 принимает x, значит x входит в L1 ∪ L2; если ни один из них не принимает, то это может продолжаться вечно.
Следовательно язык L1 ∪ L2 бесконечный (так как мы не можем ничего сказать о конечности языка L2 ), но, возможно, разрешимый (если х входит в L1) и, возможно, неразрешимый (если х не входит в L1)
Задача зарезервирована: Evvnes 08:39, 19 декабря 2024 (UTC)