Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 6 |
[ Сообщений: 51 ] | На страницу 1, 2, 3, 4, 5, 6 След. |
|
Автор | Сообщение | ||
---|---|---|---|
O Micron |
|
||
Алгоритм называется применимым к данному "входу" если он рано или поздно остановится и выдаст некоторый результат. В противном случае говорят, что алгоритм неприменим к данному "входу". Теорема об "остановке" утверждает, что проблема применимости произвольного алгоритма к произвольному "входу" алгоритмически неразрешима. ▼ (Рассмотрение, как доказывается алгоритмическая неразрешимость "проблемы остановки".)
Я предлагаю зайти с другого конца. Разумеется, я имею ввиду только алгоритмы конечного объема, поскольку в противном случае очевидна невозможность произвести анализ за конечное время. Итак. Введем понятие состояния алгоритма. Под состоянием будем понимать множество величин всех переменных, содержание регистров, указателей, и всего прочего, что способно изменяться в ходе выполнения алгоритма. Начнем выполнение алгоритма, запоминая состояние на каждом его шаге. За конечное время алгоритм либо окажется выполненным до конца и остановится, чем будет доказана его применимость. Если же алгоритм возвратится на предшествующую инструкцию, причем окажется там в том же самом состоянии, как и в один из предыдущих раз, это будет означать обнаружение бесконечного цикла, то есть неприменимость алгоритма. Рассмотрим, будет ли неприменимость обнаружена за конечное время? По определению, объем алгоритма конечен. Следовательно, количество его различных состояний также конечно. Значит и число сочетаний состояний с инструкциями алгоритма должно быть конечным, и за конечное время оно исчерпается и состояния начнут повторяться. Это приведет к тому, что за конечное время на какой-нибудь инструкции окажется опять то же самое состояние, если только конец алгоритма не окажется достигнут еще раньше. Вывод: неприменимость алгоритма будет обнаружена за конечное время, как и применимость. Отсюда простой вопрос: в чем я неправ? Не мог же я оказаться умнее всех профессиональных математиков |
|||
Вернуться к началу | |||
ivashenko |
|
||
Во всем
|
|||
Вернуться к началу | |||
ivashenko |
|
||
Возьмите простейший алгоритм, пусть входом будут натуральные числа, пусть в алгоритме заложено условие, если вход меньше 1917, то вывод halt и остановка иначе - бесконечный цикл. Вам неизвестны условия применимости входа к данному алгоритму. Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. Например дан вход 100 или 1993. Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя, он - черный ящик. Проблема в том, чтоб определить применимость по входу.
|
|||
Вернуться к началу | |||
O Micron |
|
|
ivashenko писал(а): пользоваться алгоритмом нельзя, он - черный ящик. Где это было сказано в условии? Там, наоборот, сказано: "... позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), ..." то есть алгоритм доступен для анализа, какой же тут "черный ящик" может быть.ivashenko писал(а): Но пользоваться алгоритмом нельзя Этого тоже в условии не сказано.ivashenko писал(а): Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. и по функциональной таблице машины Тьюринга, то есть по исходнику, грубо говоря. Вы об этом не забыли?ivashenko писал(а): составьте алгоритм Ну так я ж его описал. Искомым алгоритмом является отладчик ivashenko писал(а): Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя Даже учтя уже выше отвеченное, - я и алгоритмом не пользуюсь я пользуюсь отладчиком, анализирующим применение входа к представленному исходному тексту.Я где-то сказал неправду? |
||
Вернуться к началу | ||
O Micron |
|
||||||||||||||||||||||||||||||
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 |
|
||
Сорь, сейчас мне заявят, что в условиях задачи на входе никакое "состояние" не дается.
Но его можно вычислить, изучая текст алгоритма. Это подразумевалось, но отобразить я забыл. Исправленный алгоритм решения "проблемы остановки" будет таким: 1) Просмотр анализируемого текста построчно от начала до конца для подсчета использованных переменных и/или других объектов, могущих меняться. Таким образом получаем исходное состояние. 2) Выбираем начальную инструкцию текста. 3) очередная инструкция это оператор выхода? Да - алгоритм применим, конец анализа. 4) была ли уже эта инструкция проанализирована? да: сравниваем текущее состояние со всеми запомненными для этого номера инструкции состояниями. Есть совпадающие? Да - алгоритм неприменим, конец анализа. 5) запоминаем номер инструкции, что она была проанализирована. 7) запоминаем текущее состояние при ней. 8) если инструкция требует изменить состояние - изменяем состояние. 9) если оператор перехода - выбираем указанную в нем инструкцию. иначе - 10) проверяем существование следующей инструкции. не существует - достигнут конец текста. Анализ завершен. существует - 11) выбираем следующую инструкцию 12) переход к п.3 |
|||
Вернуться к началу | |||
ivashenko |
|
||
Исследуемый алгоритм- черный ящик, пользуясь отладчиком Вы вскрываете черный ящик и исследуете алгоритм эмпирически, а требуется исследовать его алгоритмически, не касаясь ни кода ни эмпирических данных.
|
|||
Вернуться к началу | |||
O Micron |
|
||
Где Вы увидели такие требования?
|
|||
Вернуться к началу | |||
individ |
|
||
Не обращайте внимание!
Этот сумащедщий сам не понимает, что говорит! |
|||
Вернуться к началу | |||
ivashenko |
|
||
Уважаемый individ, на Вас уже давно никто не обращает внимания, так что расслабтесь.
|
|||
Вернуться к началу | |||
На страницу 1, 2, 3, 4, 5, 6 След. | [ Сообщений: 51 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Дефекты и остановки вентиляторов и насосов
в форуме Теория вероятностей |
3 |
395 |
10 фев 2015, 19:54 |
|
Какое расстояние пройдёт центр шарика до остановки?
в форуме Механика |
2 |
109 |
15 авг 2023, 15:55 |
|
Какой путь пройдёт груз до окончательной остановки?
в форуме Механика |
15 |
341 |
19 авг 2023, 14:07 |
|
Задачи без "точки остановки"
в форуме Комбинаторика и Теория вероятностей |
0 |
333 |
26 июн 2019, 00:08 |
|
Две проблемы
в форуме Геометрия |
18 |
749 |
11 июн 2023, 12:08 |
|
Две проблемы
в форуме Геометрия |
8 |
628 |
09 мар 2023, 23:05 |
|
Проблемы с пределами
в форуме Пределы числовых последовательностей и функций, Исследования функций |
4 |
369 |
19 окт 2015, 12:59 |
|
Проблемы с циклом for
в форуме MathCad |
0 |
501 |
01 июн 2015, 14:28 |
|
Проблемы с геометрией | 6 |
455 |
02 май 2018, 17:41 |
|
Проблемы с геометрией. | 1 |
283 |
09 апр 2018, 16:38 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |