2011-gre-cs-practice-book.pdf/Q70 — различия между версиями
Материал из DISCOPAL
Evvnes (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 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|[[Участник:StasFomin|StasFomin]] 14:34, 19 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Теория сложности]] | |
| − | + | ||
Текущая версия на 14:34, 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)