Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
Решение "проблемы остановки" http://mathhelpplanet.com/viewtopic.php?f=51&t=34794 |
Страница 1 из 6 |
Автор: | O Micron [ 25 июн 2014, 20:24 ] |
Заголовок сообщения: | Решение "проблемы остановки" |
"Проблема остановки" - это проблема поиска универсального алгоритма, позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), а также по записи произвольного "входа" - установить, остановится ли вычислительное устройство, действующее в соответствие с данным алгоритмом и обрабатывающее данный "вход", или же оно будет работать бесконечно долго. Алгоритм называется применимым к данному "входу" если он рано или поздно остановится и выдаст некоторый результат. В противном случае говорят, что алгоритм неприменим к данному "входу". Теорема об "остановке" утверждает, что проблема применимости произвольного алгоритма к произвольному "входу" алгоритмически неразрешима. ▼ (Рассмотрение, как доказывается алгоритмическая неразрешимость "проблемы остановки".)
Я предлагаю зайти с другого конца. Разумеется, я имею ввиду только алгоритмы конечного объема, поскольку в противном случае очевидна невозможность произвести анализ за конечное время. Итак. Введем понятие состояния алгоритма. Под состоянием будем понимать множество величин всех переменных, содержание регистров, указателей, и всего прочего, что способно изменяться в ходе выполнения алгоритма. Начнем выполнение алгоритма, запоминая состояние на каждом его шаге. За конечное время алгоритм либо окажется выполненным до конца и остановится, чем будет доказана его применимость. Если же алгоритм возвратится на предшествующую инструкцию, причем окажется там в том же самом состоянии, как и в один из предыдущих раз, это будет означать обнаружение бесконечного цикла, то есть неприменимость алгоритма. Рассмотрим, будет ли неприменимость обнаружена за конечное время? По определению, объем алгоритма конечен. Следовательно, количество его различных состояний также конечно. Значит и число сочетаний состояний с инструкциями алгоритма должно быть конечным, и за конечное время оно исчерпается и состояния начнут повторяться. Это приведет к тому, что за конечное время на какой-нибудь инструкции окажется опять то же самое состояние, если только конец алгоритма не окажется достигнут еще раньше. Вывод: неприменимость алгоритма будет обнаружена за конечное время, как и применимость. Отсюда простой вопрос: в чем я неправ? Не мог же я оказаться умнее всех профессиональных математиков |
Автор: | ivashenko [ 25 июн 2014, 22:44 ] |
Заголовок сообщения: | Re: решение "проблемы остановки" |
Во всем |
Автор: | ivashenko [ 25 июн 2014, 23:15 ] |
Заголовок сообщения: | Re: решение "проблемы остановки" |
Возьмите простейший алгоритм, пусть входом будут натуральные числа, пусть в алгоритме заложено условие, если вход меньше 1917, то вывод halt и остановка иначе - бесконечный цикл. Вам неизвестны условия применимости входа к данному алгоритму. Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. Например дан вход 100 или 1993. Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя, он - черный ящик. Проблема в том, чтоб определить применимость по входу. |
Автор: | O Micron [ 26 июн 2014, 07:12 ] |
Заголовок сообщения: | Re: решение "проблемы остановки" |
ivashenko писал(а): пользоваться алгоритмом нельзя, он - черный ящик. Где это было сказано в условии? Там, наоборот, сказано: "... позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), ..." то есть алгоритм доступен для анализа, какой же тут "черный ящик" может быть.ivashenko писал(а): Но пользоваться алгоритмом нельзя Этого тоже в условии не сказано.ivashenko писал(а): Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. и по функциональной таблице машины Тьюринга, то есть по исходнику, грубо говоря. Вы об этом не забыли?ivashenko писал(а): составьте алгоритм Ну так я ж его описал. Искомым алгоритмом является отладчик ivashenko писал(а): Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя Даже учтя уже выше отвеченное, - я и алгоритмом не пользуюсь я пользуюсь отладчиком, анализирующим применение входа к представленному исходному тексту.Я где-то сказал неправду? |
Автор: | O Micron [ 26 июн 2014, 07:44 ] | ||||||||||||||||||||||||||||||
Заголовок сообщения: | Re: решение "проблемы остановки" | ||||||||||||||||||||||||||||||
ivashenko писал(а): Возьмите простейший алгоритм, пусть входом будут натуральные числа, пусть в алгоритме заложено условие, если вход меньше 1917, то вывод halt и остановка иначе - бесконечный цикл. Вам неизвестны условия применимости входа к данному алгоритму. Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. Например дан вход 100 или 1993. В смысле, Вы хотите, чтобы я описал конкретный случай? - пожалуйста!По Вашему описанию исходник будет такой: Код: a = Input if a<1917 then End label1: goto label1 Алгоритм отладчика будет таков: Вход: текст алгоритма и начальное состояние. 1) очередная инструкция это оператор выхода? Да - алгоритм применим, конец анализа. 2) была ли уже эта инструкция проанализирована? да: сравниваем текущее состояние со всеми запомненными для этого номера состояниями. Есть совпадающие? Да - алгоритм неприменим, конец анализа. 3) запоминаем номер инструкции, что она была проанализирована. 4) запоминаем текущее состояние при ней. 5) если инструкция требует изменить состояние - изменяем состояние. 6) если инструкция перехода - выбираем указанную инструкцию. нет - выбираем следующую инструкцию 7) переход к п.1 Исследуем применимость ко входу 100.
вход 1993:
Задача решена. Чего еще хотим? |
Автор: | O Micron [ 26 июн 2014, 10:49 ] |
Заголовок сообщения: | Re: решение "проблемы остановки" |
Сорь, сейчас мне заявят, что в условиях задачи на входе никакое "состояние" не дается. Но его можно вычислить, изучая текст алгоритма. Это подразумевалось, но отобразить я забыл. Исправленный алгоритм решения "проблемы остановки" будет таким: 1) Просмотр анализируемого текста построчно от начала до конца для подсчета использованных переменных и/или других объектов, могущих меняться. Таким образом получаем исходное состояние. 2) Выбираем начальную инструкцию текста. 3) очередная инструкция это оператор выхода? Да - алгоритм применим, конец анализа. 4) была ли уже эта инструкция проанализирована? да: сравниваем текущее состояние со всеми запомненными для этого номера инструкции состояниями. Есть совпадающие? Да - алгоритм неприменим, конец анализа. 5) запоминаем номер инструкции, что она была проанализирована. 7) запоминаем текущее состояние при ней. 8) если инструкция требует изменить состояние - изменяем состояние. 9) если оператор перехода - выбираем указанную в нем инструкцию. иначе - 10) проверяем существование следующей инструкции. не существует - достигнут конец текста. Анализ завершен. существует - 11) выбираем следующую инструкцию 12) переход к п.3 |
Автор: | ivashenko [ 26 июн 2014, 14:04 ] |
Заголовок сообщения: | Re: решение "проблемы остановки" |
Исследуемый алгоритм- черный ящик, пользуясь отладчиком Вы вскрываете черный ящик и исследуете алгоритм эмпирически, а требуется исследовать его алгоритмически, не касаясь ни кода ни эмпирических данных. |
Автор: | O Micron [ 26 июн 2014, 19:46 ] |
Заголовок сообщения: | Re: Решение "проблемы остановки" |
Где Вы увидели такие требования? |
Автор: | individ [ 26 июн 2014, 20:07 ] |
Заголовок сообщения: | Re: Решение "проблемы остановки" |
Не обращайте внимание! Этот сумащедщий сам не понимает, что говорит! |
Автор: | ivashenko [ 26 июн 2014, 20:32 ] |
Заголовок сообщения: | Re: Решение "проблемы остановки" |
Уважаемый individ, на Вас уже давно никто не обращает внимания, так что расслабтесь. |
Страница 1 из 6 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |