Обсуждение:Проблема остановки
Существует ли Анализатор? Если не создали то не существует :D --Boycraft 10:43, 29 апреля 2009 (UTC)
Название править
Удалил про построчную интерпретацию, см. http://en.wikipedia.org/wiki/Perl#Implementation компилирует в дерево перед выполнением.
"проблема останова" - первый раз слышу подобный термин. Сколько помню, везде, где мне встречалось упоминание о halting problem, оно обозначалось как "проблема остановки". В любом случае, сравните количество и содержание результатов поиска http://www.google.ru/search?complete=1&hl=ru&newwindow=1&client=firefox-a&rls=org.mozilla%3Aru%3Aofficial&hs=kij&as_qdr=all&q=+%22%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0+%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8%22&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=
и
Yrogirg 09:31, 13 марта 2008 (UTC)
Конечно, проблема остановки ;-) только более правильно проблема останова
Ewger 19 марта 2008
Ну ладно. Остановка благозвучнее :) Если измените, я возражать не буду. В принципе, не столь важно -- главное, чтобы перенаправления работали. А лучше подождать. Пусть, кто заинтересуется, выскажется, и пускай решают. Yrogirg 08:56, 19 марта 2008 (UTC)
- Я в учебниках по микропроцессорной технике и алгоритмам всегда видел только понятие «останов», а остановка – это слово бытовое Finarfin 20:24, 31 октября 2010 (UTC)
Доказательство невозможности - Нужен АИ. править
Сейчас описание алгоритма отличается от англ. версии. Насколько я могу судить там анализатор возвращает 1 в случае остановки , и 0 в случае неостановки. Рулин 19:37, 30 июня 2011 (UTC)
Неостановка править
>останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
- Вопрос: а как узнать, что алгоритм не останавливается? Может, если подождать подольше, то он остановится? Это же ведь не эмпирически определяется, правда?Clothclub 17:53, 22 июля 2011 (UTC) 82.142.140.60 12:11, 19 августа 2013 (UTC)
Доказательство править
К чему этот "набросок" на 10 строк? Есть доказательство, которое умещается в 4 строчки. 109.174.114.227 08:23, 6 ноября 2013 (UTC)
- В такой постановке - вообще в одну строчку: анализатор не может проанализировать (не)остановку самого себя, значит его не существует. --Inemiten (обс.) 06:05, 5 мая 2017 (UTC)
Да ведь проще всё править
Если алгоритм N уже остановился, то не проблема послать анализатор в бесконечный цикл. Но если он не останавливается, то он пока не остановился, а анализатор уже должен остановиться на основе некой информации, которую невозможно получить, так как алгоритм, не остановившийся в какой-то момент времени, всё ещё может остановиться в будущем, что должно быть причиной не останова анализатора в прошлом. Но следствие не может предшествовать причине. Таким образом, проблема останова любой машины A нерезарешима на ней самой, а может быть разрешима лишь на машине B, способной за конечное время эмулировать бесконечный цикл на машине A. А такая машина физически реализуема лишь в случае, если машина A с течением времени за конечное количество тактов бесконечно снижает своё быстродействие. Но проблема останова может быть решена в некоторых частных случаях путём анализа текста алгоритма. Например,
while (true)
не останавливается, а
int s=1;
int i;
for (i=20; i>0; --i)
{
s+=s*i;
}
return s;
останавливается. 31.135.46.5 07:16, 10 октября 2019 (UTC)
Стоп править
В реальном мире, диагонализатор будет вызываться до тех пор, пока память не закончится.
Если алгоритм требует бесконечное количество оперативной памяти, он не остановится никогда при наличии бесконечной памяти.
Сейчас попробую решить.
5.44.170.156 21:37, 20 марта 2020 (UTC)bckpkol
- Проблема остановки про машины Тьюринга (или любое другое определение вычислимости), а у них память не ограничена. — Алексей Копылов 22:16, 20 марта 2020 (UTC)
Нет править
Если программа может взять бесконечное количество памяти, может быть, это можно узнать без её выделения. 5.44.170.156 22:23, 20 марта 2020 (UTC) bckpkol