Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу 1, 2, 3, 4, 5, 6  След.
Автор Сообщение
 Заголовок сообщения: Решение "проблемы остановки"
СообщениеДобавлено: 25 июн 2014, 21:24 
Не в сети
Одарённый
Зарегистрирован:
09 мар 2014, 09:58
Сообщений: 165
Откуда: РФ
Cпасибо сказано: 6
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 2

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

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

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

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 25 июн 2014, 23:44 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Во всем :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 00:15 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Возьмите простейший алгоритм, пусть входом будут натуральные числа, пусть в алгоритме заложено условие, если вход меньше 1917, то вывод halt и остановка иначе - бесконечный цикл. Вам неизвестны условия применимости входа к данному алгоритму. Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа. Например дан вход 100 или 1993. Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя, он - черный ящик. Проблема в том, чтоб определить применимость по входу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 08:12 
Не в сети
Одарённый
Зарегистрирован:
09 мар 2014, 09:58
Сообщений: 165
Откуда: РФ
Cпасибо сказано: 6
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
ivashenko писал(а):
пользоваться алгоритмом нельзя, он - черный ящик.
Где это было сказано в условии? Там, наоборот, сказано: "... позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), ..." то есть алгоритм доступен для анализа, какой же тут "черный ящик" может быть.

ivashenko писал(а):
Но пользоваться алгоритмом нельзя
Этого тоже в условии не сказано.

ivashenko писал(а):
Вам дан вход, составьте алгоритм определения применимости исследуемого алгоритма к данному входу по виду этого входа.
и по функциональной таблице машины Тьюринга, то есть по исходнику, грубо говоря. Вы об этом не забыли?

ivashenko писал(а):
составьте алгоритм
Ну так я ж его описал. Искомым алгоритмом является отладчик :)

ivashenko писал(а):
Вы предлагаете определять результат по выходу, т.е. проверить это эмпирически. Но пользоваться алгоритмом нельзя
Даже учтя уже выше отвеченное, - я и алгоритмом не пользуюсь :) я пользуюсь отладчиком, анализирующим применение входа к представленному исходному тексту.

Я где-то сказал неправду?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 08:44 
Не в сети
Одарённый
Зарегистрирован:
09 мар 2014, 09:58
Сообщений: 165
Откуда: РФ
Cпасибо сказано: 6
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
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

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

Задача решена. Чего еще хотим? :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 11:49 
Не в сети
Одарённый
Зарегистрирован:
09 мар 2014, 09:58
Сообщений: 165
Откуда: РФ
Cпасибо сказано: 6
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Сорь, сейчас мне заявят, что в условиях задачи на входе никакое "состояние" не дается.
Но его можно вычислить, изучая текст алгоритма. Это подразумевалось, но отобразить я забыл.
Исправленный алгоритм решения "проблемы остановки" будет таким:

1) Просмотр анализируемого текста построчно от начала до конца для подсчета использованных переменных и/или других объектов, могущих меняться.
Таким образом получаем исходное состояние.

2) Выбираем начальную инструкцию текста.

3) очередная инструкция это оператор выхода?
Да - алгоритм применим, конец анализа.

4) была ли уже эта инструкция проанализирована?
да:
сравниваем текущее состояние со всеми запомненными для этого номера инструкции состояниями.
Есть совпадающие?
Да - алгоритм неприменим, конец анализа.

5) запоминаем номер инструкции, что она была проанализирована.
7) запоминаем текущее состояние при ней.

8) если инструкция требует изменить состояние - изменяем состояние.
9) если оператор перехода - выбираем указанную в нем инструкцию.
иначе -
10) проверяем существование следующей инструкции.
не существует - достигнут конец текста. Анализ завершен.
существует -
11) выбираем следующую инструкцию
12) переход к п.3

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 15:04 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 20:46 
Не в сети
Одарённый
Зарегистрирован:
09 мар 2014, 09:58
Сообщений: 165
Откуда: РФ
Cпасибо сказано: 6
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Где Вы увидели такие требования?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 21:07 
Не в сети
Оракул
Зарегистрирован:
03 июл 2013, 13:54
Сообщений: 895
Cпасибо сказано: 6
Спасибо получено:
39 раз в 34 сообщениях
Очков репутации: 4

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение "проблемы остановки"
СообщениеДобавлено: 26 июн 2014, 21:32 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3272
Cпасибо сказано: 229
Спасибо получено:
207 раз в 196 сообщениях
Очков репутации: 21

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу 1, 2, 3, 4, 5, 6  След.

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Дефекты и остановки вентиляторов и насосов

в форуме Теория вероятностей

Valeria_2015

3

199

10 фев 2015, 20:54

Какой путь прошло тело от начала движения до остановки

в форуме Интегральное исчисление

Bermen

0

194

14 ноя 2012, 10:46

Проблемы с циклом for

в форуме MathCad

zagorka

0

217

01 июн 2015, 15:28

Проблемы с тегами

в форуме Предложения, Замечания, Обратная связь

Shaman

11

618

11 янв 2012, 16:52

Проблемы с пределами

в форуме Пределы числовых последовательностей и функций, Исследования функций

lordvan

4

164

19 окт 2015, 13:59

Очередные проблемы с урнами

в форуме Теория вероятностей

polaris

2

135

14 дек 2015, 02:26

Упрощение выражения и мои проблемы с ним

в форуме Алгебра

PaHda

4

230

20 ноя 2014, 12:06

Проблемы с сетевой моделью

в форуме Исследование операций и Задачи оптимизации

wilder

1

183

13 янв 2015, 16:15

Проблемы с решением простых задач

в форуме Теория вероятностей

ImDredd

4

744

15 дек 2012, 18:06

С чего начать изучение проблемы?

в форуме Математическая статистика и Эконометрика

energetic

7

157

22 сен 2016, 22:20


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved