Математический форум Math Help Planet
http://mathhelpplanet.com/

Решение "проблемы остановки"
http://mathhelpplanet.com/viewtopic.php?f=51&t=34794
Страница 1 из 6

Автор:  O Micron [ 25 июн 2014, 20:24 ]
Заголовок сообщения:  Решение "проблемы остановки"

"Проблема остановки" - это проблема поиска универсального алгоритма, позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), а также по записи произвольного "входа" - установить, остановится ли вычислительное устройство, действующее в соответствие с данным алгоритмом и обрабатывающее данный "вход", или же оно будет работать бесконечно долго.
Алгоритм называется применимым к данному "входу" если он рано или поздно остановится и выдаст некоторый результат. В противном случае говорят, что алгоритм неприменим к данному "входу". Теорема об "остановке" утверждает, что проблема применимости произвольного алгоритма к произвольному "входу" алгоритмически неразрешима.

▼ (Рассмотрение, как доказывается алгоритмическая неразрешимость "проблемы остановки".)
Эта теорема доказывается весьма просто. Первый шаг заключается в том, что вводится понятие самоприменимости алгоритма. Алгоритм называется самоприменимым, если он эффективно перерабатывает текст, соответствующий его собственной записи, в некоторый результат за конечное число шагов. В противном случае - если алгоритм не останавливается, продолжает работать бесконечно долго - то он называется несамоприменимым.

Вначале доказывается следующее утверждение: не существует алгоритма применимого ко всем несамоприменимым алгоритмам и только к ним. Доказательство заключается в указании на противоречивость понятия о таком алгоритме. Зададимся вопросом: является ли данный алгоритм самоприменимым? Если он самоприменим, то, очевидно, он несамоприменим (поскольку применим лишь к несамоприменимым алгоритмам). Если же он несамоприменим, то он самоприменим (поскольку применим ко всем несамоприменимым алгоритмам).

Исходя из этого результата можно также доказать несуществование алгоритма, способного универсальным образом распознавать несамоприменимость произвольных алгоритмов. Действительно, если такой алгоритм существует, то можно построить и алгоритм, применимый ко всем несамоприменимым алгоритмам и только к ним.

Обозначим буквой В алгоритм способный распознавать несамоприменимость. Тогда следующий алгоритм будет алгоритмом, применимым ко всем несамоприменимым алгоритмам и только к ним:

1. Выполнить В, перейти к п. 2.

2. Если получен ответ "да", то перейти к п. 3, в противном случае перейти к п. 4.

3. Окончить процесс.

4. Перейти к п. 4.

Этот алгоритм останавливается, если рассматриваемый в качестве входа алгоритм несамоприменим, и не останавливается (зацикливает на п. 4) в противном случае.

Используя данный результат можно также показать, что не существует и алгоритм, распознающий универсальным образом самоприменимость (поскольку в противном случае можно построить алгоритм, который распознает несамоприменимость).

И, наконец, можно показать, что алгоритмически неразрешимой является проблема распознавания применимости произвольного алгоритма к произвольному "входу". Допустим обратное. Пусть Е - алгоритм, который по заданному произвольному алгоритму и заданному на входе "слову" распознает применимость данного алгоритма к данному "слову". Нетрудно построить алгоритм, который позволяет установить является ли заданное "слово" кодом данного алгоритма. Обозначим такой алгоритм буквой Р.

Тогда можно построить алгоритм Н:

1. Применить Р. Перейти к п. 2.

2. Если Р дал ответ "да", перейти к п. 3, иначе - к п. 4.

3. Выполнить алгоритм Е. Конец.

4. Перейти к п. 4.

Алгоритм Н является алгоритмом, распознающим самоприменимость произвольных алгоритмов. Следовательно, он не возможен, а значит не возможен и алгоритм Е.

источник: http://www.scorcher.ru/art/theory/algor ... orithm.php


Я предлагаю зайти с другого конца.
Разумеется, я имею ввиду только алгоритмы конечного объема, поскольку в противном случае очевидна невозможность произвести анализ за конечное время.
Итак.

Введем понятие состояния алгоритма. Под состоянием будем понимать множество величин всех переменных, содержание регистров, указателей, и всего прочего, что способно изменяться в ходе выполнения алгоритма.

Начнем выполнение алгоритма, запоминая состояние на каждом его шаге.
За конечное время алгоритм либо окажется выполненным до конца и остановится, чем будет доказана его применимость.
Если же алгоритм возвратится на предшествующую инструкцию, причем окажется там в том же самом состоянии, как и в один из предыдущих раз, это будет означать обнаружение бесконечного цикла, то есть неприменимость алгоритма.

Рассмотрим, будет ли неприменимость обнаружена за конечное время?
По определению, объем алгоритма конечен. Следовательно, количество его различных состояний также конечно.
Значит и число сочетаний состояний с инструкциями алгоритма должно быть конечным, и за конечное время оно исчерпается и состояния начнут повторяться.
Это приведет к тому, что за конечное время на какой-нибудь инструкции окажется опять то же самое состояние, если только конец алгоритма не окажется достигнут еще раньше.

Вывод: неприменимость алгоритма будет обнаружена за конечное время, как и применимость.


Отсюда простой вопрос: в чем я неправ?
Не мог же я оказаться умнее всех профессиональных математиков :P

Автор:  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.
Шаги отладчика инструкция состояние 
новая инструкция: вход a=100
новая инструкция: условный оператор a=100 
оператор выхода обнаружена применимость 



вход 1993:

Шаги отладчика инструкция состояние
1новая инструкция: вход a=1993 
2новая инструкция: условный оператор a=1993 
3новая инструкция: метка a=1993 
4новая инструкция: безусловный переход a=1993 
5прежняя инструкция: метка прежнее состояние: a=1993
новое состояние: a=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: Решение "проблемы остановки"

Не обращайте внимание!
Этот сумащедщий сам не понимает, что говорит! :puzyr:)

Автор:  ivashenko [ 26 июн 2014, 20:32 ]
Заголовок сообщения:  Re: Решение "проблемы остановки"

Уважаемый individ, на Вас уже давно никто не обращает внимания, так что расслабтесь.

Страница 1 из 6 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/