Сообщения со словом
«алгоритмически»

1. 13.01.2013, 02:12. siryoga в теме
   «Основы конструктивной теории множеств»
   ... функции вида f n- 0 1 к-рые в принципе можно вычислить алгоритмически и к-рые определены u на каждом натуральном...
2. 12.01.2013, 20:01. siryoga в теме
   «Основы конструктивной теории множеств»
   ... операция построения мн-ва д ч выше я доказал что мн-во алгоритмически вычислимых бесконечных двоичних последовательностей...
3. 22.12.2012, 18:10. Shmakov в теме
   «Зарплата выпускника МИФИ 2011 года: где? какая?»
   ... потоков данных и прочее и прочее решите эту задачу алгоритмически или численно за вами начнется охота...
4. 29.05.2012, 14:31. Besta в теме
   «КиБ: специалитет»
   ... программирования вообще на к в первые два года что-то алгоритмически сложное есть вроде бы только на 17-ой...
5. 13.10.2011, 14:53. jiffy в теме
   «Что делать с гастарбайтерами ?»
   это задача алгоритмически эквивалентная уничтожению коррупции...
6. 24.10.2010, 18:06. min в теме
   «Ответ на обращения группы студентов МИФИ о демонтаже креста.»
   ... стремление придумать себе бога может быть заложено алгоритмически тогда весь этот мир является только...
7. 28.04.2010, 01:54. ildar в теме
   «Есть только ВМиК...»
   ... своему усмотрению модифицировать язык должен быть алгоритмически полным разумеется ну то есть поддерживать...
8. 22.05.2009, 18:56. ramzai в теме
   «Школа анализа данных Яндекса, летние сборы Саратовского ГУ»
   ... и computer science второе несколько ближе к нашей алгоритмически-олимпиадной тематике первое больше в...
9. 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 задача об остановке конкретной машины на конкретной ленте продолжая уменьшать неопределенность при решении проблемы останова сформулируем проблему еще более конкретно является ли задача останова конкретной машины т0 при конкретном входном слове t0 алгоритмически разрешимой если дана пара т0 t0 то может...
10. 21.01.2009, 22:03. Nemo в теме
    «Теорема Кантора: конец векового спора»
    ... останове на чистой произвольной ленте для м тьюринга алгоритмически неразрешима это я так на всякий случай...