2011-gre-cs-practice-book.pdf/Q70 — различия между версиями
Материал из DISCOPAL
Evvnes (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q70-08c765 == | == Вопрос: Q70-08c765 == | ||
| − | Если L<sub>1</sub> | + | Если L<sub>1</sub> — разрешимый язык, а L<sub>2</sub> — неразрешимый язык, то язык L<sub>1</sub> ∪ L<sub>2</sub> , который является объединением L<sub>1</sub> и L<sub>2</sub> , будет являться |
| − | + | ||
=== Ответы === | === Ответы === | ||
| Строка 17: | Строка 16: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|48|70}} | {{cstest-source|2011-gre-cs-practice-book.pdf|48|70}} | ||
| − | + | ;Определения: | |
| − | * Разрешимость языка , означает, что существует машина Тьюринга, которая может однозначно определить, находится ли любая заданная строка в языке(в нашем случае L<sub>1</sub>) или нет, за конечный промежуток времени. | + | * Разрешимость языка, означает, что существует машина Тьюринга, которая может однозначно определить, находится ли любая заданная строка в языке(в нашем случае L<sub>1</sub>) или нет, за конечный промежуток времени. |
| − | + | * Неразрешимость языка, означает, что не существует машины Тьюринга, которая могла бы определить принадлежность для каждой строки в языке (в нашем случае L<sub>2</sub>). | |
| − | * Неразрешимость языка , означает, что не существует машины Тьюринга, которая могла бы определить принадлежность для каждой строки в языке (в нашем случае L<sub>2</sub>). | + | |
| − | + | ||
| − | + | ||
| + | ;Что происходит при объединении: | ||
* Поскольку L<sub>1</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>2</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 в 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>(машина Тьюринга для языка L<sub>2</sub>) на x. Но М<sub>1</sub> не гарантированно остановится на x, | ||
и мы все равно хотели бы принять x, если М<sub>2</sub> примет его. Таким образом, решение состоит в том, чтобы запускать М<sub>1</sub> и М<sub>2</sub> | и мы все равно хотели бы принять x, если М<sub>2</sub> примет его. Таким образом, решение состоит в том, чтобы запускать М<sub>1</sub> и М<sub>2</sub> | ||
| − | параллельно, переключаясь между выполнением того или другого. Если в | + | параллельно, переключаясь между выполнением того или другого. Если в какой-то момент вычисления |
М<sub>1</sub> принимает x, значит x входит в L<sub>1</sub> ∪ L<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>) | + | Следовательно язык 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)