Сообщения со словом
«неразрешима»

1. 13.09.2013, 08:21. Алексей Лотов в теме
   «Новая парадигма мировоззрения (А.Лотов)»
   ... биороботов откуда следует что смена версии прораммы почти неразрешима потому что в прежней программе зашит приказ...
2. 15.05.2013, 19:27. A_Ponta??? в теме
   «В Иране собираются построить новый реактор»
   ... находит решение задачи то есть по вашему эта задача неразрешима в условиях классической физики точнее ее...
3. 22.01.2009, 19:02. Nemo в теме
   «Теорема Кантора: конец векового спора»
   ... тьюринга на произвольном входном слове алгоритмически неразрешима иными словами нельзя придумать универсальный алгоритм в результате выполнения которого будет получен однозначный ответ да если произвольная машина т остановится на ленте с произвольным входным словом t и нет если т не остановится на ленте t доказательство докажем теорему от противного предположим что задача об остановке произвольной машины т при обработке произвольного слова t алгоритмически разрешима это означает что существует алгоритм решения а значит и существует реализующая его машина тьюринга д построим машину д на ленте которой записано кодовое описание машины т и кодовое описание входного слова t д обрабатывает эти два слова и пишет да если т останавливается при обработке t и нет если этого не происходит если этот алгоритм работает для любого случая любого входного слова t то должен работать и для частного случая в качестве начального слова в том числе можно выбрать описание машины т е возьмем dt dt построим машину е которая будет на своей ленте иметь описание произвольной машины т работа машины е состоит в том что она копирует описание dt а затем работает как д если существует д то существует е построим машину f f работает как e но отличие состоит в том что если после работы на входном слове dt машина е останавливается с ответом да что означает что машина т останавливается то машина f не останавливается а продолжает бесконечное движение вправо без изменения знаков на ленте если же вдруг машина е останавливается с ответом нет это означает что машина т не останавливается то f просто останавливается если данный алгоритм работает для произвольной машины т то и для конкретной тоже будет работать положим т f таким образом на ленте машины f оказывается описание самой машины f в результате получим что машина f анализирует саму себя f самоанализирующая машина получаем что f не останавливается в том случае если е остановится с ответом да а это означает что машина т остановится поскольку т f имеем ситуацию f остановится если f не остановится и f не остановится если f остановится что явно противоречит здравому смыслу такой машины существовать не может поскольку все рассуждения были логически обоснованы полученное противоречие означает что ошибка в изначальном предположении о существовании машины д в данном доказательстве используется прямой метод отсюда напрямую следует что задача об остановке произвольной машины т на произвольном слове t алгоритмически неразрешима q e d 1 5 2 задача об остановке произвольной машины тьюринга на пустой ленте если бы имелся алгоритм а значит и соответствующая машина тьюринга для решения проблемы остановки произвольной машины при обработке произвольного слова то эта машина могла бы решить и проблему остановки на пустой ленте как частный случай но неразрешимость проблемы остановки при анализе произвольного слова непосредственно не означает неразрешимости проблемы остановки на пустой ленте потому как последняя задача может оказаться более простой так как ее сфера применения явно уже однако мы можем показать что эти задачи эквиваленты в том случае если для каждой пары машина-лента t-t докажем наличие соответствующей машины mtt работающей на чистой ленте т 1 5 2 теорема задача об остановке произвольной машины тьюринга на пустой ленте алгоритмически неразрешима доказательство для каждой пары машина-лента t-t докажем наличие соответствующей задачи остановки на пустой ленте для некоторой другой машины предположим mtt машина mtt строится непосредственно по описанию t и t если диаграмму состояний т дополнить последовательностью новых состояний предположим что для пары t t в некоторый момент времени лента выглядит таким образом рис 1 8 r1 r2 rm rm 1 курсор здесь rm 2 rn рис 1 8 лента машины т в выбранной момент времени новая машина mtt начинает работу на пустой ленте и работает по следующей программе s1 r1 r s2 s2 r2 r s3 sm rm r sm 1 sm 1 x r sm 2 sm 2 rm 2 r sm 3 sn rn l sх sх rn-1 rn-1 l sх sх rn-2 rn-2 l sх sх rm 2 rm 2 l sх sх х rm 1 l s0 s0 rm далее работа аналогично машине т на ленте t где x некоторая буква в других случаях не встречающаяся на входной ленте t s1 sn sх новые состояния машины mtt которых не было в машине т т о машина mtt при запуске на пустой ленте эквивалента машине т работающей на ленте t так как по сути машина mtt просто печатает копию ленты t на своей ленте затем выбирает нужную позицию и после этого становится полностью идентичной машине т значит mtt и т эквивалентные машины предположим что задача об остановке машины на чистой ленте алгоритмически разрешима значит ее можно решить и применительно к машине mtt начинающей работу на чистой ленте соответственно такая задача решается и для машины т на ленте t что есть противоречие с доказанным в теореме 1 5 1 утверждением о том что для произвольной машины т задача остановки при обработке произвольного слова t алгоритмически неразрешима отсюда следует что задача об остановке машины на чистой ленте алгоритмически неразрешима q e d в данном доказательстве используется косвенный метод называемый методом сведения в п 1 5 1 была доказана неразрешимость проблемы останова для произвольных пар т t только что показано что каждой паре т t соответствует легко конструируемая машина mtt которая останавливается на пустой ленте тогда и только тогда когда имеет место останов пары т t способность решать частные проблемы останова т пустая лента которая включает все ситуации mtt пустая лента предоставила бы возможность решить все проблемы останова для произвольных пар т t можно сказать что значительно более трудная проблема для пар т t свелась к значительно более простой проблеме для пар т пустая лента сводимость достаточно тонкое и важное понятие в теории вычислимости оказывается можно определить бесконечную иерархию проблем неразрешимости возрастающей сложности ни одна из которых не сводится к предшествующей было даже показано что существуют пары неразрешимых проблем ни одна из которых не сводится к другой 1 5 4 задачи о печатании символов т 1 5 4 теорема задача о печатании данного символа на чистой ленте точно один раз алгоритмически неразрешима доказательство без ограничения общности возьмем знак 0 итак машина тьюринга т работает на чистой ленте преобразуем ее в новую машину тьюринга d если т не содержит в своем алфавите знака 0 то d просто совпадает с t если t имеет этот знак в своем алфавите то в алфавите машины d знак 0 будет заменен любым знаком ранее не входящим в алфавит машины очевидно что d остановится тогда когда остановится т построим машину е которая работает как d вплоть до ее остановки после этого машина е печатает 0 и тоже останавливается т о получим что символ 0 печатается точно один раз в том случае если произвольная машина т останавливается на чистой ленте значит задача о печатании ровно одного нуля равносильна задаче об остановке машины на чистой ленте поскольку задача останова алгоритмически неразрешима то и задача о печатании символа точно один раз тоже неразрешима q e d т 1 5 5 теорема задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима доказательство без ограничения общности возьмем знак 0 итак машина тьюринга т работает на чистой ленте преобразуем ее в новую машину тьюринга d если т не содержит в своем алфавите знака 0 то d просто совпадает с t если t имеет этот знак в своем алфавите то в алфавите машины d знак 0 будет заменен любым знаком ранее не входящим в алфавит машины очевидно что d остановится тогда когда остановится т построим машину е которая работает как d вплоть до ее остановки после этого машина е переходит в состояние а и печатает 0 бесконечно много раз a 0ra т о получим что символ 0 печатается бесконечно много раз в том случае если произвольная машина т останавливается на чистой ленте значит задача о печатании бесконечно большого числа нулей равносильна задаче об остановке машины на чистой ленте поскольку задача останова алгоритмически неразрешима то и задача о печатании символа бесконечно много раз тоже не разрешима q e d т 1 5 6 теорема задача о печатании данного символа на чистой ленте хотя бы один раз алгоритмически неразрешима доказательство без ограничения общности возьмем знак 0 итак машина тьюринга т работает на чистой ленте построим машину е которая работает как т вплоть до ее остановки после чего машина е печатает 0 и останавливается в итоге будет напечатан хотя бы один символ 0 возможно и больше если ранее машиной т такой символ уже печатался т о получим что символ 0 печатается хотя бы один раз в том случае если произвольная машина т останавливается на чистой ленте значит эта задача равносильна задаче об остановке машины на чистой ленте поскольку эта задача согласно теореме 1 5 2 алгоритмически неразрешима то и задача о печатании символа хотя бы один раз тоже неразрешима q e d 1 5 6 задача об остановке конкретной...
4. 21.01.2009, 22:03. Nemo в теме
   «Теорема Кантора: конец векового спора»
   ... чистой произвольной ленте для м тьюринга алгоритмически неразрешима это я так на всякий случай
5. 17.05.2006, 07:43. подколодный' в теме
   «To be or not to be»
   задача однозначно неразрешима полюбому требуются какие-то алгоритмы определения...
6. 05.11.2005, 14:56. подколодный в теме
   «Идея "рыночной общины"»
   ... еще одно если вы считаете что поставленная задача неразрешима то прямо так и пишите
7. 09.10.2005, 15:28. maxru в теме
   «нам тут кое-что задали»
   ... содержимому следовательно на вопрос нет ответа задача неразрешима
8. 18.05.2005, 14:49. Yolkeen в теме
   «Логические парадоксы 7»
   ... собственных условиях было бесполезно она попросту неразрешима оставалось отбросить эти условия и ввести свое и еще один момент сервантес этим эпизодом явно осуждает непомерно формальный пронизанный духом схоластической логики масштаб средневековой справедливости но какими распространенными в его время а это было около четырехсот лет назад были сведения из области логики не только самому сервантесу известен данный парадокс писатель находит возможным приписать своему герою безграмотному крестьянину способность понять что перед ним неразрешимая задача 5 другие парадоксы приведенные...