Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.
Типа доказано, что нет.

Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".

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

Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и анализируемую машину.

Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))

Имхо получается просто бессмысленная синтаксическая конструкция, как с Теоремой Гёделя о неполноте.

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

Здравствуйте, graniar, Вы писали:

G>Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.

Только нагрузочное тестирование, только хардкор. И вотчдог к нему в нагрузку.

Здравствуйте, graniar, Вы писали:

G>Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))

Не пойму, о чём ты. sha256sum /usr/bin/sha256sum прекрасно работает, без всяких рекурсий. Точно так же ты можешь запустить halt-analyzer /usr/bin/halt-analyzer.

Здравствуйте, graniar, Вы писали:

G>Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.
G>Типа доказано, что нет.
G>Только это доказательство какое-то совсем неубедительное.

А ты в курсе, почему алгоритм называется "Диагонализатор"? Он диаги анализирует?

Здравствуйте, vsb, Вы писали:

vsb>Точно так же ты можешь запустить halt-analyzer /usr/bin/halt-analyzer.

Скорее $0 "$0 $1"

Здравствуйте, Alekzander, Вы писали:

A>А ты в курсе, почему алгоритм называется "Диагонализатор"? Он диаги анализирует?

Наверное от слова диагональ, типа тестит диагональные элементы матрицы.

Здравствуйте, vsb, Вы писали:

vsb>Не пойму, о чём ты. sha256sum /usr/bin/sha256sum прекрасно работает, без всяких рекурсий.

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

Ведь анализатор анализирует не просто код, а конкретное состояние машины.
А там предлагается анализатору скормить просто код анализатора без его входящих данных.

Здравствуйте, graniar, Вы писали:

G>А там предлагается анализатору скормить просто код анализатора без его входящих данных.

Исследуя математические функции, ты предпочтет иметь дело с уравнениями, а не каким-то набором значений. Можно определить область допустимых значений, экстремумы, разрывы и т.д.
Также и с кодом (помним про частично рекурсивные функции).

Здравствуйте, Nuzhny, Вы писали:

N>Исследуя математические функции, ты предпочтет иметь дело с уравнениями, а не каким-то набором значений. Можно определить область допустимых значений, экстремумы, разрывы и т.д.
N>Также и с кодом (помним про частично рекурсивные функции).

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

Здравствуйте, graniar, Вы писали:

A>>А ты в курсе, почему алгоритм называется "Диагонализатор"? Он диаги анализирует?

G>Наверное от слова диагональ, типа тестит диагональные элементы матрицы.

Это отсылка к Кантору. Очень сильное колдунство, лежит в основе мноооого чего, потому что фундаментальное. И поэтому странно читать вот такие наезды:

G>Только это доказательство какое-то совсем неубедительное.

Здравствуйте, Alekzander, Вы писали:

A>Очень сильное колдунство, лежит в основе мноооого чего, потому что фундаментальное.

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

A>И поэтому странно читать вот такие наезды:
G>>Только это доказательство какое-то совсем неубедительное.

Ну так весь смысл доказательства — убедить читателя. Почему бы не пожаловаться, если оно с этим не справляется.
Может конкретно это, приведенное в Вики доказательство — некорректно.

Здравствуйте, graniar, Вы писали:

G>Ну так весь смысл доказательства — убедить читателя.

Это математика, а не суд.

Здравствуйте, Alekzander, Вы писали:

A>Это математика, а не суд.

Перефразируя известный анекдот,
Я попросил их привести доказательство этой теоремы, на что мне было сказано: "У нас математикам верят на слово". Вот тогда-то во мне и открылся большой математический талант!

Здравствуйте, graniar, Вы писали:

G>Любые уравнения, производные и тд абстракции, все они имеют элементарный смысл, все можно приземлить конкретным примером типа бесконечно малых приращений.
G>Абстрагирование просто позволяет экономить вычислительные ресурсы, но оно не создает новых выводов.

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

Здравствуйте, Nuzhny, Вы писали:

N>Создаёт же. Исследовать бесконечности без соответствующего математического аппарата, а лишь конкретными значениями, ты не сможешь.

Бесконечности — это чистые абстракции, которые не имеют никакого отображения в реальности. И все их можно так или иначе заменить.

Для конкретного примера — допустим есть какое-то сложное выражение с тригонометрическими функциями. Пользуясь тригонометрическими тождествами мы можем его упростить и потом посчитать, разложив в степенные ряды. А можем сразу разложить в степенные ряды и посчитать эту громоздкую конструкцию не пользуясь никакими тригономтерическими тождествами. Результат будет тот же с точностью до погрешности вычисления.

Тоже самое, например, с интегралом. Можно вычислить аналитически, а можно посчитать численным методом.

Здравствуйте, graniar, Вы писали:
G>Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и анализируемую машину.
Поздравляю, вы напоролись на контр-интуитивное поведение бесконечностей.
Все доказательства проблемы останова неявно содержат в себе предположение о том, что как программа, так и её состояние, никак не ограничены по размеру.

Если бы это было не так, то у нас есть совершенно очевидный алгоритм, который прекрасно работает:
1 делаем два экземпляра нашей машины, A и B, инициализируем каждый переданной нам программой и входными данными
2 делаем 1 шаг вычислений на машине А
3 делаем 2 шага вычислений на машине B
4 сравниваем состояние машин:
— если хотя бы одна из них остановилась — программа останавливается
— если ни одна не остановилась, но состояния совпали — программа зацикливается
— иначе — продолжаем с шага 2.

Если пространство состояний машины конечно, то наш алгоритм закончит своё выполнение за конечное количество шагов.

А вот если это пространство — бесконечно, как у МТ, то машина может бесконечно переходить во всё новые и новые состояния, не останавливаясь и не зацикливаясь. И после каждого шага мы по-прежнему не будем знать, остановится она, зациклится, или так и продолжит бесконечное ациклическое выполнение.

Здравствуйте, graniar, Вы писали:

G>Для конкретного примера — допустим есть какое-то сложное выражение с тригонометрическими функциями. Пользуясь тригонометрическими тождествами мы можем его упростить и потом посчитать, разложив в степенные ряды. А можем сразу разложить в степенные ряды и посчитать эту громоздкую конструкцию не пользуясь никакими тригономтерическими тождествами. Результат будет тот же с точностью до погрешности вычисления.
G>Тоже самое, например, с интегралом. Можно вычислить аналитически, а можно посчитать численным методом.

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

Здравствуйте, Sinclair, Вы писали:

S>Поздравляю, вы напоролись на контр-интуитивное поведение бесконечностей.

Имхо, "настоящие бесконечности" (в отличие от бесконечно малых/больших но конечных), это бессмысленная, вводящая в заблуждение, синтаксическая конструкция.
Везде, где можно, лучше обходиться без них.

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

Но первоначальное состояние то ограничено.

Более того, самые простые начальные состояния явно можно проанализировать аналитически.
Значит, если теорема о неразрешимости остановки верна, есть условие некоторого минимального начального размера, или минимальной Колмогоровской сложности состояния.

А что, если переформулировать проблему без бесконечностей, но чтобы она по прежнему имела тот же практический смысл?

S>Если пространство состояний машины конечно, то наш алгоритм закончит своё выполнение за конечное количество шагов.

А если пространство состояний конечно, но наш алгоритм должен закончить свое выполнение за очень большое, но зависящее от начального размера время, например C*exp(exp(size))?

Здравствуйте, Nuzhny, Вы писали:

N>Нет, это так не работает. Есть устойчивость вычислений, не всё можно вычислить приближённо и рядами. Сначала функцию исследуют на устойчивость, подбирают конкретные методы. Ты сходу не сможешь функцию Бесселя рядами Тейлора посчитать, потому что там в середине ряда будет большой факториал. И вообще, очень много неустойчивых решений, которые преодолеваются как раз аналитическим исследованием.

Ну наверное есть какие-то другие элементарные пути. В конце-концов, все практически значимые вопросы относятся к моделированию физической реальности и сама эта реальность может выступать в роли вычисления. Ну это уже пошло больше в область философии, материализм vs идеализм.

Здравствуйте, graniar, Вы писали:

G>Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".

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

Здравствуйте, Sinclair, Вы писали:

S> Если пространство состояний машины конечно, то наш алгоритм закончит своё выполнение за конечное количество шагов.
Бесконечности тут побоку.
Ты просто переформулировал Проблему Останова в проблему определить — конечно ли пространство состояний данной МТ или нет. Иными словами. Вот даётся тебе некий произвольный алгоритм — можно ли его как-то проверить _алгоритмически_ и узнать, что "пространство состояний машины конечно"?

С таким же успехом сабж можно "опровергнуть" сабж ограничивая не память (как ты выразился "пространство состояний"), а время — мол, если в N шагов не влезло — значит считаем, что зациклилось. Толку правда тоже никакого.

И собственно всё. Та же ж, только в профиль.

Здравствуйте, cppguard, Вы писали:

C>А вот если взять подмножество МТ в виде реальных архитектур да ещё и добавить ограничений (например, запретить безусловный переход), то всё отлично поддаётся анализу, и терминируемость доказывается.

Реальных архитектур, имеешь в виду с ограничением по используемой памяти? В стиле, как Sinclair выше привел, или нечто более практичное?

Здравствуйте, cppguard, Вы писали:

c> G>Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".
c> Тоже пытался понять, но забил, когда понял, что у нас так-то машина Тьюринга, в которой лента памяти бесконечная. А вот если взять подмножество МТ в виде реальных архитектур да ещё и добавить ограничений (например, запретить безусловный переход), то всё отлично поддаётся анализу, и терминируемость доказывается.
Не доказывается. Если не хватило ресурсов, то это просто означает, что не хватило данных ресурсов. Ведь остаётся возможность, что если дать ещё чуток ресурсов (без всяких бесконечностей, они тут не нужны), вдруг внезапно алгоритм таки отработает.

Здравствуйте, ·, Вы писали:
·>Бесконечности тут побоку.
·>Ты просто переформулировал Проблему Останова в проблему определить — конечно ли пространство состояний данной МТ или нет.
Противоречие выделено.
·> Иными словами. Вот даётся тебе некий произвольный алгоритм — можно ли его как-то проверить _алгоритмически_ и узнать, что "пространство состояний машины конечно"?
Инженеров интересует не "произвольный алгоритм", а программа на реальном языке программирования, выполняющаяся на реальной машине.
У реальных машин конечность пространства состояний встречается гораздо чаще, чем бесконечность.

Здравствуйте, graniar, Вы писали:

G>Но первоначальное состояние то ограничено.
Это несущественно. Даже если начальное состояние — пустое, программа может функционировать бесконечно долго, не зацикливаясь и не останавливаясь.
G>А если пространство состояний конечно, но наш алгоритм должен закончить свое выполнение за очень большое, но зависящее от начального размера время, например C*exp(exp(size))?
Он будет заканчивать своё выполнение за очень большое, не зависящее от начального размера время O(2^size).

G>возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет

В принципе — возможно.

https://www.studmed.ru/anderson-r-dokazatelstvo-pravilnosti-programm_9fec4703b60.html

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, graniar, Вы писали:

G>>Но первоначальное состояние то ограничено.
S>Это несущественно. Даже если начальное состояние — пустое, программа может функционировать бесконечно долго, не зацикливаясь и не останавливаясь.

Почему это несущественно? Анализатор имеет конечный размер и его аргумент то же. Бесконечности не нужны. Синтаксическая конструкция о рекурсивном скармливании анализатору самого себя не имеет смысла.

S>Он будет заканчивать своё выполнение за очень большое, не зависящее от начального размера время O(2^size).

Не, ну так не интересно, ведь вся соль проблемы в том, что анализатор должен находить нетривиальный способ предсказания остановки.
Попробую еще раз переформулировать проблему без бесконечностей:

Существует алгоритм-анализатор, который для любого начального состояния машины размером S, ограниченного в памяти размером M >> S,
может предсказать останавливаемость за количество шагов T. Причем, S << T << M

Здравствуйте, Sinclair, Вы писали:

S> ·>Бесконечности тут побоку.
S> ·>Ты просто переформулировал Проблему Останова в проблему определить — конечно ли пространство состояний данной МТ или нет.
S> Противоречие выделено.
Это не противоречие, а твоё неявное допущение.

S> ·> Иными словами. Вот даётся тебе некий произвольный алгоритм — можно ли его как-то проверить _алгоритмически_ и узнать, что "пространство состояний машины конечно"?
S> Инженеров интересует не "произвольный алгоритм", а программа на реальном языке программирования, выполняющаяся на реальной машине.
S> У реальных машин конечность пространства состояний встречается гораздо чаще, чем бесконечность.
Т.е. инженер докажет, что программа на машине с 1Мб памяти — зацикливается (ловит OOM и идёт в цикл). Толку только ноль. Как себя будет вести эта же программа на 2Мб памяти — всё равно неизвестно.
В общем сабж тут в полный рост.

Здравствуйте, graniar, Вы писали:

G>Почему это несущественно? Анализатор имеет конечный размер и его аргумент то же. Бесконечности не нужны.
В таком случае проблема останова разрешима.

G>Не, ну так не интересно, ведь вся соль проблемы в том, что анализатор должен находить нетривиальный способ предсказания остановки.
Не факт, что такой способ существует.
G>Попробую еще раз переформулировать проблему без бесконечностей:
G>Существует алгоритм-анализатор, который для любого начального состояния машины размером S, ограниченного в памяти размером M >> S,
G>может предсказать останавливаемость за количество шагов T. Причем, S << T << M
Это было бы слишком шикарно, чтобы быть правдой.

Эмпирическое правило вычислимости: все мало-мальски интересные задачи либо невычислимы, либо NP-полны.
А вы хотите не просто полиномиальности, а линейности алгоритма.

Здравствуйте, ·, Вы писали:
·>Это не противоречие, а твоё неявное допущение.
Допущение чего? Вы путаете причину и следствие.

·>Т.е. инженер докажет, что программа на машине с 1Мб памяти — зацикливается (ловит OOM и идёт в цикл).
Нет. Для программы, которая выполняется на машине с 1мб памяти, очень легко проверить впадаемость в цикл — я привёл способ. Никакого другого способа выполняться бесконечно у неё нету.

·>Толку только ноль. Как себя будет вести эта же программа на 2Мб памяти — всё равно неизвестно.
Точно так же проверяем программу на машине с 2Мб памяти.

Но можно поступить проще — если у нас программа написана на ассемблере x86, то нам достаточно проверить её на "машине" с памятью размером 2⁶⁴.

Здравствуйте, Sinclair, Вы писали:

S> ·>Это не противоречие, а твоё неявное допущение.
S> Допущение чего? Вы путаете причину и следствие.
"Если пространство состояний машины конечно" — это допущение эквивалентное тому, что программа останавливается.

S> ·>Т.е. инженер докажет, что программа на машине с 1Мб памяти — зацикливается (ловит OOM и идёт в цикл).
S> Нет. Для программы, которая выполняется на машине с 1мб памяти, очень легко проверить впадаемость в цикл — я привёл способ. Никакого другого способа выполняться бесконечно у неё нету.
Впадаемость в цикл — это не критерий для сабж.

S> ·>Толку только ноль. Как себя будет вести эта же программа на 2Мб памяти — всё равно неизвестно.
S> Точно так же проверяем программу на машине с 2Мб памяти.
И? Как она себя поведёт на 3Мб памяти? Т.е. проверить зависнет ли программа — запустить, подождать определённое кол-во времени. Эти манипуляции с шагом-двумя ничего нового не сообщат.

S> Но можно поступить проще — если у нас программа написана на ассемблере x86, то нам достаточно проверить её на "машине" с памятью размером 2⁶⁴.
Зато она себя может начать вести себя по-другому на двух таких машинах соединённых сетью.

Пример. Можно легко написать простой алгоритм, который перебирает числа и если a^n+b^n==c^n , то завершает. Ты запустил эту прогу на компьютере x86 с терабайтом памяти. Она не вышла, твой обнаружитель циклов ничего не обнаружил. Какой из этого можно сделать вывод? Завериштся ли эта прога на двух терабайтах памяти?

Здравствуйте, graniar, Вы писали:

G>Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?

Здравствуйте, graniar, Вы писали:

G>Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.
G>Типа доказано, что нет.

Ключевое слово — "за конечное время". Без этого программу можно просто запустить и подождать, остановится ли она.

G>Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".

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

Здравствуйте, graniar, Вы писали:

G>Ну наверное есть какие-то другие элементарные пути. В конце-концов, все практически значимые вопросы относятся к моделированию физической реальности и сама эта реальность может выступать в роли вычисления. Ну это уже пошло больше в область философии, материализм vs идеализм.

Физическая реальность слишком сложна. Вся наша аналитика — это попытка упростить ее до модели, с которой можно работать разумом

Здравствуйте, graniar, Вы писали:

G>Имхо, "настоящие бесконечности" (в отличие от бесконечно малых/больших но конечных), это бессмысленная, вводящая в заблуждение, синтаксическая конструкция.
G>Везде, где можно, лучше обходиться без них.

Тогда придется, например, помнить о дискретности физического мира. Считать площадь участка земли не в сотках, а в количестве песчинок, зерен глины и дождевых червячков, которые эту площадь составляют. Не знаю даже, что и проще.

Здравствуйте, graniar, Вы писали:

G>Существует алгоритм-анализатор, который для любого начального состояния машины размером S, ограниченного в памяти размером M >> S,
G>может предсказать останавливаемость за количество шагов T. Причем, S << T << M

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

Здравствуйте, Sinclair, Вы писали:

S>Инженеров интересует не "произвольный алгоритм", а программа на реальном языке программирования, выполняющаяся на реальной машине.
S>У реальных машин конечность пространства состояний встречается гораздо чаще, чем бесконечность.

С другой стороны, поскольку состояние программы имеет физический носитель, то изменение состояния требует некоторой энергии, и, из-за дискретности нашего мира, эта энергия имеет теоретический минимум (реальные машины потребляют гораздо больше).

И я читал где-то, что чтобы просто последовательно перебрать все состояния N-битного счетчика, не хватит всей энергии вселенной. Причем N какое-то совсем небольшое, в районе то ли 128, то ли 256 бит.

А у меня в программе обычно больше 4-х переменных типа int

Здравствуйте, Pzz, Вы писали:

Pzz>Тогда придется, например, помнить о дискретности физического мира. Считать площадь участка земли не в сотках, а в количестве песчинок, зерен глины и дождевых червячков, которые эту площадь составляют. Не знаю даже, что и проще.

Это как раз пример безусловно полезных "бесконечно малых/больших конечностей". А "настоящие бесконечности", это когда всякие парадоксы получаются типа суммы Рамануджана, обсуждаемой в соседнем топике.

Здравствуйте, Pzz, Вы писали:

Pzz>Суть этого доказательства в том, что каким бы умным не был анализатор, сложность входной программы завсегда можно поднять на недосягаемую для него высоту. Например, скормив его себе самому.

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

Здравствуйте, kov_serg, Вы писали:

_>Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
_>если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?

Ничто не мешает анализатору быть суперинтеллектом, аналитически доказывающим теорему Ферма.

Здравствуйте, Pzz, Вы писали:

G>>Существует алгоритм-анализатор, который для любого начального состояния машины размером S, ограниченного в памяти размером M >> S,
G>>может предсказать останавливаемость за количество шагов T. Причем, S << T << M

Pzz>Существует. Заключается в запуске этой программы и ожидании, пока она либо не остановится, либо не переберет все свои возможные состояния. Только этот алгоритм настолько медленный, что лишен практического смысла

Тогда T = O(2^M), что противоречит условию S << T << M

Здравствуйте, Sinclair, Вы писали:


G>>Не, ну так не интересно, ведь вся соль проблемы в том, что анализатор должен находить нетривиальный способ предсказания остановки.
S>Не факт, что такой способ существует.

Ну так это же и есть суть проблемы. Определить, есть такой способ или нет.
Смысл именно в том, чтобы найти эквивалентную формулировку проблемы останова, где можно обойтись без парадоксов бесконечностей, типа сумм Рамануджана.

S>Эмпирическое правило вычислимости: все мало-мальски интересные задачи либо невычислимы, либо NP-полны.
S>А вы хотите не просто полиномиальности, а линейности алгоритма.

Отнюдь.
Если анализатор окажется NP-полной проблемой, или даже S << T = O(2^exp(S)) << M, это тоже будет очень шикарно.

Здравствуйте, graniar, Вы писали:

g> _>Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
g> _>если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?
g> Ничто не мешает анализатору быть суперинтеллектом, аналитически доказывающим теорему Ферма.
Сабж мешает же.

Здравствуйте, ·, Вы писали:

g>> Ничто не мешает анализатору быть суперинтеллектом, аналитически доказывающим теорему Ферма.
·>Сабж мешает же.

Сабж то как раз и требуется доказать или опровергнуть.

Здравствуйте, graniar, Вы писали:
G>Ну так это же и есть суть проблемы. Определить, есть такой способ или нет.
Ставлю $100 на NP-completeness. Это переместит проблему в область "математически разрешимо, но коммерчески невыгодно".

G>Если анализатор окажется NP-полной проблемой, или даже S << T = O(2^exp(S)) << M, это тоже будет очень шикарно.
В этой формуле нет размера программы. Вы включаете саму программу в S? Это, в принципе, логично, т.к. код у нас всё равно эквивалентен данным. Можно записать 42 в "область параметров" и сделать ldarg.0; а можно просто сделать ldc 42 безо всяких параметров.
В общем, NP-complete решение не интересно совсем.
Если оно окажется NP-complete, то нас всё ещё будут интересовать приближённые решения с лучшей асимптотикой.

Здравствуйте, Pzz, Вы писали:
Pzz>И я читал где-то, что чтобы просто последовательно перебрать все состояния N-битного счетчика, не хватит всей энергии вселенной. Причем N какое-то совсем небольшое, в районе то ли 128, то ли 256 бит.
Даже 64 — уже очень много. См. байку про шахматы.
Pzz>А у меня в программе обычно больше 4-х переменных типа int
На практике нетривиальные циклы встречаются не так уж и часто; поэтому если нас интересует прикладная надёжность, то решение с двумя бегунами и общим таймаутом вполне адекватно.
Таймаут у нас предоставляет страховочную сетку для нетривиальных случаев; а благодаря наличию детектора зацикливания эту сетку можно переместить достаточно далеко от старта.
Тогда у нас есть 100% гарантия того, что неудачный код не съест безлимитный ресурс, плюс некоторая уверенность в том, что простые косяки не станут бесполезно прогревать воздух в течение миллиардов операций.

Здравствуйте, ·, Вы писали:
·>"Если пространство состояний машины конечно" — это допущение эквивалентное тому, что программа останавливается.
Нет. Даже при конечности пространства состояний программа может никогда не останавливаться.
Вот вам минимальный пример:

while(true);

·>Впадаемость в цикл — это не критерий для сабж.
Для конечного пространства состояний — критерий. Для бесконечного — увы.

·>И? Как она себя поведёт на 3Мб памяти? Т.е. проверить зависнет ли программа — запустить, подождать определённое кол-во времени. Эти манипуляции с шагом-двумя ничего нового не сообщат.
Сообщат. "Определённое количество времени" как раз ничего не говорит — может быть, надо было просто подождать ещё секундочку, и программа бы успешно остановилась. А может быть — наоборот, она за это время уже миллион раз прошла через то же состояние, и детектор циклов бы давно её поймал.

·>Зато она себя может начать вести себя по-другому на двух таких машинах соединённых сетью.
Две машины соединённых сетью эквивалентны одной машине с пространством состояний 265.

·>Пример. Можно легко написать простой алгоритм, который перебирает числа и если a^n+b^n==c^n , то завершает. Ты запустил эту прогу на компьютере x86 с терабайтом памяти. Она не вышла, твой обнаружитель циклов ничего не обнаружил.
Этого не может быть. Либо она впадает в цикл, либо выходит. Каким образом вы себе представляете "неостановку" программы на машине конечного размера?

·>Какой из этого можно сделать вывод?
Можно сделать вывод о том, что я плохо объяснил вам принцип работы детектора циклов.

Здравствуйте, graniar, Вы писали:

G>Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.

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

Если же машина Тьюринга конечна (с конечной лентой), то у нее конечное число состояний, которые можно просто перечислить. Значит и программа (содержимое ленты) может быть только конечной. Соответственно, можно простым запуском за конечное время понять, куда мы попадаем из текущего состояния: в состояние "СТОП" или в одно из конечного числа ранее пройденных и сохраненных в некоем списке состояний (что означает бесконечный цикл). Т.е. на каждой итерации работы машины берем ее полное состояние, ищем в списке, и если оно там есть — мы зациклились, если нет — сохраняем новое состояние в списке и идем дальше.

Здравствуйте, kov_serg, Вы писали:
G>>Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
_>Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
_>если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?
Для начала невредно вспомнить, что Ферма имел в виду целые числа.
А в компьютере никаких "целых чисел" нет.
Обычная арифметика работает не с Z, а кольцом вычетов по модулю 2^N.
Арифметика с "бесконечными целыми" всё ещё работает с целыми вполне себе ограниченного размера.
Поэтому никакая реальная программа не сможет перебрать "все целые числа".
Построение анализатора, который бы проверял воображаемую программу для воображаемой машины, невозможно.
А вот построение анализатора, который бы проверял реальную программу на реальной машине — теоретически возможно.
И если мы реализовали перебор корректно, то программа успешно переберёт все доступные ей целые числа и остановится.
А если мы допустили в программе косяк, то она впадёт в цикл и её поймает детектор циклов.

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

Здравствуйте, anonymouse2, Вы писали:
A>Если же машина Тьюринга конечна (с конечной лентой), то у нее конечное число состояний, которые можно просто перечислить. Значит и программа (содержимое ленты) может быть только конечной. Соответственно, можно простым запуском за конечное время понять, куда мы попадаем из текущего состояния: в состояние "СТОП" или в одно из конечного числа ранее пройденных и сохраненных в некоем списке состояний (что означает бесконечный цикл). Т.е. на каждой итерации работы машины берем ее полное состояние, ищем в списке, и если оно там есть — мы зациклились, если нет — сохраняем новое состояние в списке и идем дальше.
Даже список не нужен — просто запускаем вторую машину вдвое быстрее.

Здравствуйте, Sinclair, Вы писали:

Pzz>>А у меня в программе обычно больше 4-х переменных типа int
S>На практике нетривиальные циклы встречаются не так уж и часто; поэтому если нас интересует прикладная надёжность, то решение с двумя бегунами и общим таймаутом вполне адекватно.

На практике есть много полезных частных случаев, поддающихся автоматизированному анализу. Поэтому статические анализаторы кода — полезный инструмент. Но не всемогущий.

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

Здравствуйте, Sinclair, Вы писали:

Pzz>>На практике есть много полезных частных случаев, поддающихся автоматизированному анализу. Поэтому статические анализаторы кода — полезный инструмент. Но не всемогущий.
S>Ну... Да. В целом, мир уныл и безнадёжен. Одно из частных проявлений этого всеобщего принципа — это как раз ограничение вычислимости.

Наоборот, по-моему. Именно ограниченность мира делает возможным применение инженерной выдумки. Если бы у нас была золотая рыбка, которая исполняет любые наши желания, вот тогда, действительно, мир был бы уныл и безнадежен. Зачем к чему-то стремиться, если и так всё есть?

S>Т.е. если мы сделаем такой язык программирования (ну или машину — что примерно одно и то же), на котором любую программу можно статически отверифицировать, то он будет не Тьюринг-полным.

Такой язык уже сделали, Agda незывается

S>А, значит, будут существовать какие-то программы, которые можно написать для МТ, но нельзя — для нашей машины.

Да. И в этом нет ничего плохого.

S>Ну, и, естественно, окажется, что как раз самые интересные задачи — именно такие Неразрешимые на нашем "доказуемом языке".

Можно компактно собрать неразрешимые в кучку, и там их компактно разрешить, человеческим разумом, без автоматического доказатора. А всякую унылую обвязку, которой обычно шибко дофига, и она сложная в том смысле, что требует кропотливости, но не обязательно сложная алгоритмически, оставить автомату.

Здравствуйте, Sinclair, Вы писали:

S> ·>"Если пространство состояний машины конечно" — это допущение эквивалентное тому, что программа останавливается.
S> Нет. Даже при конечности пространства состояний программа может никогда не останавливаться.
Сабж не для минимальных известных примеров, а для общего случая. На вход подаётся произвольный код и для него надо определить сабж.

S> ·>Впадаемость в цикл — это не критерий для сабж.
S> Для конечного пространства состояний — критерий. Для бесконечного — увы.
Это просто другая задача. С тем же результатом.
Есть множество задач, которые алгоритмически эквивалентны проблеме остановки. Так вот, твоя задача "укладывается ли код в конечное число состояний" — эквивалентна сабжу.

S> ·>И? Как она себя поведёт на 3Мб памяти? Т.е. проверить зависнет ли программа — запустить, подождать определённое кол-во времени. Эти манипуляции с шагом-двумя ничего нового не сообщат.
S> Сообщат. "Определённое количество времени" как раз ничего не говорит — может быть, надо было просто подождать ещё секундочку
Бинго! Ровно то же с твоим ограничением по памяти. Надо было просто дать ещё один байтик, и программа бы успешно остановилась.

S> ·>Зато она себя может начать вести себя по-другому на двух таких машинах соединённых сетью.
S> Две машины соединённых сетью эквивалентны одной машине с пространством состояний 265.
Именно! Ты ошибся утверждая, что "достаточно проверить её на "машине" с памятью размером 2⁶⁴". Нет. Не достаточно даже для x86.

S> ·>Пример. Можно легко написать простой алгоритм, который перебирает числа и если a^n+b^n==c^n , то завершает. Ты запустил эту прогу на компьютере x86 с терабайтом памяти. Она не вышла, твой обнаружитель циклов ничего не обнаружил.
S> Этого не может быть. Либо она впадает в цикл, либо выходит. Каким образом вы себе представляете "неостановку" программы на машине конечного размера?
Ты игнорируешь третью альтернативу "не влезло в твоё произвольное ограничение по памяти".
Ты исподтишка подменяешь исходную задачу и вместо решения для данной задачи "a^n+b^n==c^n" ты выдаёшь решение для "a^n+b^n==c^n, n<2^64". Но это не даёт ничего для решения данной задачи.

S> ·>Какой из этого можно сделать вывод?
S> Можно сделать вывод о том, что я плохо объяснил вам принцип работы детектора циклов.
Да я знаю это, алгоритм черепахи и зайца называется или вроде того.

Здравствуйте, graniar, Вы писали:

g> g>> Ничто не мешает анализатору быть суперинтеллектом, аналитически доказывающим теорему Ферма.
g> ·>Сабж мешает же.
g> Сабж то как раз и требуется доказать или опровергнуть.
Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.

Здравствуйте, ·, Вы писали:
·>Сабж не для минимальных известных примеров, а для общего случая. На вход подаётся произвольный код и для него надо определить сабж.
Непонятно, почему вы противопоставляете общему случаю "минимальные известные примеры".
Непонятно, как именно на практике вы собрались "подать на вход произвольный код". В МТ это возможно — но это математика, там "существуют" такие штуки, как программы бесконечной длины.

·>Это просто другая задача. С тем же результатом.
Вы путаете результат и постановку.
·>Есть множество задач, которые алгоритмически эквивалентны проблеме остановки. Так вот, твоя задача "укладывается ли код в конечное число состояний" — эквивалентна сабжу.
Я такую задачу не ставил. Я говорю о машинах, которые "похожи" на Машину Тьюринга примерно также, как регистры процессора — на целые числа.
То есть ещё до того, как мы начали рассматривать какой-либо код, мы уже знаем, что пространство состояний — конечно.

·>Бинго! Ровно то же с твоим ограничением по памяти. Надо было просто дать ещё один байтик, и программа бы успешно остановилась.
Невозможно "дать ещё один байтик" программе, в которой адресация памяти сделана при помощи 32х-разрядных указателей.

·>Именно! Ты ошибся утверждая, что "достаточно проверить её на "машине" с памятью размером 2⁶⁴". Нет. Не достаточно даже для x86.
Достаточно, если программа не собирается общаться по сети.

·>Ты игнорируешь третью альтернативу "не влезло в твоё произвольное ограничение по памяти".
Что значит "не влезло"? Как вы себе это представляете?
·>Ты исподтишка подменяешь исходную задачу и вместо решения для данной задачи "a^n+b^n==c^n" ты выдаёшь решение для "a^n+b^n==c^n, n<2^64". Но это не даёт ничего для решения данной задачи.
Не исподтишка, а вполне открыто. Мне кажется, что от вашего внимания ускользает важный факт — на реальной машине эту задачу перебором решить невозможно. В принципе.
А решаемость этой задачи на воображаемой машине сама по себе не очень интересна — потому, что решение-то тоже воображаемое.

S>> Можно сделать вывод о том, что я плохо объяснил вам принцип работы детектора циклов.
·>Да я знаю это, алгоритм черепахи и зайца называется или вроде того.
Но почему-то вам кажется, что я предлагаю анализировать программы для МТ, а не программы для ограниченных машин.

Здравствуйте, Pzz, Вы писали:
Pzz>Можно компактно собрать неразрешимые в кучку, и там их компактно разрешить, человеческим разумом, без автоматического доказатора.
А вот это уже опирается на предположение о том, что человеческий разум вычислительно мощнее автоматического доказатора.
То есть на трансцендентную природу человеческого сознания

Лично я в это не верю — я верю в тезис Чёрча. Так что всё, что мы можем компактно сделать — это совершить акт веры. Типа "мы принимаем P < NP без строгого доказательства".

Здравствуйте, Sinclair, Вы писали:

Pzz>>Можно компактно собрать неразрешимые в кучку, и там их компактно разрешить, человеческим разумом, без автоматического доказатора.
S>А вот это уже опирается на предположение о том, что человеческий разум вычислительно мощнее автоматического доказатора.
S>То есть на трансцендентную природу человеческого сознания

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

S>Лично я в это не верю — я верю в тезис Чёрча. Так что всё, что мы можем компактно сделать — это совершить акт веры. Типа "мы принимаем P < NP без строгого доказательства".

Мы еще можем изобретать новые сущности.

Здравствуйте, graniar, Вы писали:

G>Реальных архитектур, имеешь в виду с ограничением по используемой памяти? В стиле, как Sinclair выше привел, или нечто более практичное?

Возможно, неправильно выразился. На практике, если нужно доказать алгоритм, то берут конкретную архитектуру и конкретный алгоритм. Если нужно, то модифицируют его. Постановку задачу останова часто неправильно понимают из-за запутанной формулировки. Кажется, что теорема гласит "терминируемость программы невозможно доказать", а в реальности — невозможно доказать терминируемость в общем случае, поэтому и доказательство вида "вот есть программа, для которой невозможно доказать, что она остановится". Но, скажем, int main() { return 0; } вполне себе доказуема в плане останова. Таким образом ценность теоремы в том, что она говорит учёным "не пытайтесь найти универсальный способ анализа алгоритма на предмет останова, корректности и т.д. — в общем случае это невозможно".

И в этом плане сабж перекликается с печально известной гипотезой P = NP. В интернетах любят пугать квантовыми компьютерами и тем роковым днём, когда P = NP будет доказано, и сотни банков падут по всему миру, вода поднимается на 33 метра, а живые позавидуют мёртвым. А на деле, если доказать, что P = NP, то никоим образом полиномиальный алгоритм факторизации простых чисел не возникнет сам собой, его ещё нужно будет придумать.

Здравствуйте, Pzz, Вы писали:
Pzz>Нет. Просто человек может придумать новый способ доказательства на ходу, а доказатор будет пользоваться теми, которые в него предыдущие человеки заложили.
Или придумает новый способ доказательства на ходу. Почему нет?

Pzz>Мы еще можем изобретать новые сущности.
Ничуть не больше, чем МТ.

Здравствуйте, Sinclair, Вы писали:

S>В общем, NP-complete решение не интересно совсем.

Оно либо NP-complete, либо неразрешимо. Просто потому-что любую NP-полную задачу можно решить простым перебором с размером начального состояния O(n). Впрочем наверное и вообще ограничением по памяти тоже O(n).

Коммерчески может и неинтересно, а академически — еще как. Это все-таки более обширный класс задач. И если окажется, что они все эквивалентны NP — это очень круто.
Да и даже принципиальная разрешимость — тоже круто. Там же вроде много всего завязано на неразрешимости, надо будет все пересматривать.

Здравствуйте, Sinclair, Вы писали:

S> ·>Сабж не для минимальных известных примеров, а для общего случая. На вход подаётся произвольный код и для него надо определить сабж.
S> Непонятно, почему вы противопоставляете общему случаю "минимальные известные примеры".
S> Непонятно, как именно на практике вы собрались "подать на вход произвольный код".
На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.

S> В МТ это возможно — но это математика, там "существуют" такие штуки, как программы бесконечной длины.
Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.

S> ·>Есть множество задач, которые алгоритмически эквивалентны проблеме остановки. Так вот, твоя задача "укладывается ли код в конечное число состояний" — эквивалентна сабжу.
S> Я такую задачу не ставил. Я говорю о машинах, которые "похожи" на Машину Тьюринга примерно также, как регистры процессора — на целые числа.
S> То есть ещё до того, как мы начали рассматривать какой-либо код, мы уже знаем, что пространство состояний — конечно.
Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов). Да, это полезно, но полезность довольно ограниченная.

S> ·>Бинго! Ровно то же с твоим ограничением по памяти. Надо было просто дать ещё один байтик, и программа бы успешно остановилась.
S> Невозможно "дать ещё один байтик" программе, в которой адресация памяти сделана при помощи 32х-разрядных указателей.
Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти. Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.

S> ·>Именно! Ты ошибся утверждая, что "достаточно проверить её на "машине" с памятью размером 2⁶⁴". Нет. Не достаточно даже для x86.
S> Достаточно, если программа не собирается общаться по сети.
Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.

S> ·>Ты игнорируешь третью альтернативу "не влезло в твоё произвольное ограничение по памяти".
S> Что значит "не влезло"? Как вы себе это представляете?
Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.

S> ·>Ты исподтишка подменяешь исходную задачу и вместо решения для данной задачи "a^n+b^n==c^n" ты выдаёшь решение для "a^n+b^n==c^n, n<2^64". Но это не даёт ничего для решения данной задачи.
S> Не исподтишка, а вполне открыто. Мне кажется, что от вашего внимания ускользает важный факт — на реальной машине эту задачу перебором решить невозможно. В принципе.
Почему ты так решил-то, что в принципе? Вот задачу четырёх красок решили перебором. Если мы поперебирали чего-то — и таки нашли решение, то нам просто повезло. А если перебор не нашел решения, то мы ничего не знаем, и решение неизвестно. Никакие циклодетекторы нам не помогут. Т.е. твой циклодетектор (и любой другой алгоритм) будет давать не два ответа, как ты обещаешь, а три: "да", "нет", "хз".

S> А решаемость этой задачи на воображаемой машине сама по себе не очень интересна — потому, что решение-то тоже воображаемое.
В смысле "вооброжаемое"? Вполне конкретное. Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны. Требуется выдать результат в виде "да, есть такие 4 числа", "нет таких чисел". Очень конкретно, ничего воображать не надо.

S> S>> Можно сделать вывод о том, что я плохо объяснил вам принцип работы детектора циклов.
S> ·>Да я знаю это, алгоритм черепахи и зайца называется или вроде того.
S> Но почему-то вам кажется, что я предлагаю анализировать программы для МТ, а не программы для ограниченных машин.
Не для ограниченных машин в принципе (каждая машина может иметь разные ограничения), а для данной конкретной машины. Притом ответ уже заранее известен — на данном компе любой алгоритм остановится, т.к. кол-во ресурсов ограничено. Твой анализатор только лишь детектит определённый паттерн поведения и обнаруживает цикл состояний и в _некоторых_ случаях может выдать ответ с меньшим расходом ресурсов, чем тупой полный прогон проги. Т.е. это просто алгоритм обнаружения циклов. Сабж он не решает.

Здравствуйте, ·, Вы писали:

g>> Сабж то как раз и требуется доказать или опровергнуть.
·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.

Так собственно топик про то, что доказан не убедительно и предлагается найти более убедительное доказательство без парадоксов с бесконечностями.
Собственно я даже не понял, причем тут вообще бесконечности, но предложил предположительно-эквивалентную формулировку без них.

Здравствуйте, Sinclair, Вы писали:

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

Так, стоп. А причем здесь вообще бесконечности?
Если программа конечного размера и она завершается, она завершается спустя конечное время.
Для заданного начального размера программ существует такое число M, что все программы, если они завершаются, то завершаются за меньшее число шагов.

Соответственно, анализатор, который тупо выполняет ее M шагов и является корректным анализатором.
Другой вопрос, как узнать это число M, но оно существует, а значит и существует соответствующая программа-анализатор.

Здравствуйте, graniar, Вы писали:

g> g>> Сабж то как раз и требуется доказать или опровергнуть.

g> ·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.
g> Так собственно топик про то, что доказан не убедительно и предлагается найти более убедительное доказательство без парадоксов с бесконечностями.
В доказательстве сабжа никаких парадоксов с бесконечностями нет. На всякий случай приведу само доказательство:

Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером N, получив на вход число N. Пусть K — это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.

g> Собственно я даже не понял, причем тут вообще бесконечности, но предложил предположительно-эквивалентную формулировку без них.
Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал.

Здравствуйте, cppguard, Вы писали:

c> G>Реальных архитектур, имеешь в виду с ограничением по используемой памяти? В стиле, как Sinclair выше привел, или нечто более практичное?
c> А на деле, если доказать, что P = NP, то никоим образом полиномиальный алгоритм факторизации простых чисел не возникнет сам собой, его ещё нужно будет придумать.
Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее.

Здравствуйте, ·, Вы писали:

·>Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал.

Это меня Sinclair запутал.

А anonymouse2, как оказалось сразу суть проблемы уловил. Вот вам и авторитетность. Как говорится, иногда "устами младенца глаголет истина".

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

А в формулировке задачи (взял в этот раз с англоязычного для надежности) ничего про начальный размер программы не говорится:

The overall goal is to show that there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x; that is, the following function h (for "halts") is not computable

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

То есть, как сказал anonymouse2,

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

Здравствуйте, graniar, Вы писали:

g> ·>Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал.
g> Это меня Sinclair запутал.
Да он сам запутался, похоже.

g> А anonymouse2, как оказалось сразу суть проблемы уловил. Вот вам и авторитетность. Как говорится, иногда "устами младенца глаголет истина".
А я так и не понял что за проблема у которой надо улавливать суть.

g> Соответственно, какое бы большое число M мы не взяли, есть достаточно большая программа, которая потребует больше шагов для завершения.
Не то, что "большая программа". А вообще неизвестно какая, практически любая. И маленькие программы могут требовать оооооооочень много шагов. Функцию Аккермана погляди — всего ~3 строчки кода.

g> проанализировать любую программу и предсказать, зависнет она или нет, нельзя. Просто потому что "любая" программа может быть бесконечной.
Это не очень корректное высказывание. Нет бесконечного натурального числа. Так и нет бесконечной программы. Всё тут конечное.
Множество всех программ|чисел — бесконечно.

Здравствуйте, ·, Вы писали:

·>А я так и не понял что за проблема у которой надо улавливать суть.

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

Скорее всего, я не прав. Надеюсь услышать в чем.

Здравствуйте, graniar, Вы писали:

g> ·>А я так и не понял что за проблема у которой надо улавливать суть.
g> Проблема в некорректной формулировке сабжа.
g> А если добавить условие ограниченности размера начального состояния анализируемой программы, проблема остановки разрешима самым тривиальным способом.
Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера.

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

g> Ну и заново открывает поле для незавершенных исследований более эффективных способов, которые были прекращены после публикации некорректного доказательства.
Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные?

Здравствуйте, ·, Вы писали:

g>> А если добавить условие ограниченности размера начального состояния анализируемой программы, проблема остановки разрешима самым тривиальным способом.
·>Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера.

Не уверен, что распарсил. Может ты имел ввиду, промежуточное состояние? Потому-что начальное состояние может быть забито рэндомом.

И по-любому, сама программа тоже занимает место. Так-что начальное состояние нулевого размера — это тривиальная нулевая МТ, останавливающаяся после 0 ходов.

·>Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные?

Вот именно его некорректности и посвящен данный топик.

Здравствуйте, ·, Вы писали:

·>Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее.

Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности. И что метод математической индукции там не помогает и алгоритм для N элементов не годится для N+1.

Здравствуйте, graniar, Вы писали:

g> ·>Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее.
g> Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности.
Все NP-полные задачи — это задачи одного класса сложности. По определению.

Здравствуйте, graniar, Вы писали:

g> ·>Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера.
g> Не уверен, что распарсил. Может ты имел ввиду, промежуточное состояние? Потому-что начальное состояние может быть забито рэндомом.
g> И по-любому, сама программа тоже занимает место. Так-что начальное состояние нулевого размера — это тривиальная нулевая МТ, останавливающаяся после 0 ходов.
Я значит не понял что за начальное состояние. Но это не важно, т.к. состояние — это только модель конкретной формализации алгоритма в виде МТ. Можно взять другую модель, лямбда-исчисление, или диофантовы уравнения — в них никаких состояний нет вообще, но ничего не изменится, результат сабжа — тот же.

g> ·>Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные?
g> Вот именно его некорректности и посвящен данный топик.
Но ты так и не привёл его, поэтому неясно корректность чего ты хочешь обсуждать и зачем.
Прочитай корректное доказательство, есть и в вики, и в куче книжек.

Здравствуйте, ·, Вы писали:

g>> Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности.
·>Все NP-полные задачи — это задачи одного класса сложности. По определению.

Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.

Здравствуйте, ·, Вы писали:

·>Но ты так и не привёл его, поэтому неясно корректность чего ты хочешь обсуждать и зачем.

Привел ссылку на статью в вики и что конкретно мне не нравится. https://rsdn.org/forum/education/8546713

Автор: graniar
Дата: 21.06.23

Здравствуйте, graniar, Вы писали:

g> ·>Но ты так и не привёл его, поэтому неясно корректность чего ты хочешь обсуждать и зачем.
g> Привел ссылку на статью в вики и что конкретно мне не нравится. https://rsdn.org/forum/education/8546713

Автор: graniar
Дата: 21.06.23

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

Здравствуйте, graniar, Вы писали:

g> ·>Все NP-полные задачи — это задачи одного класса сложности. По определению.
g> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
O(f(N)) == O(f(N+k))

Здравствуйте, ·, Вы писали:

g>> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
·>Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
·>O(f(N)) == O(f(N+k))

Это было в поддержку аргумента оппонента про то, что доказательство P=NP может не помочь решать NP-полные задачи.

Здравствуйте, ·, Вы писали:

·>Ты просто неправильно понимаешь доказательство.

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

В формулировке ничего не говорится про ограничение на размер начального состояния анализируемой машины.

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

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

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

Здравствуйте, graniar, Вы писали:

g> ·>Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
g> ·>O(f(N)) == O(f(N+k))
g> Это было в поддержку аргумента оппонента про то, что доказательство P=NP может не помочь решать NP-полные задачи.
Угу. И как выяснили — не может.

Здравствуйте, graniar, Вы писали:

g> ·>Ты просто неправильно понимаешь доказательство.
g> Ну ок, опустим пока непонятное колдунство. В процессе обсуждения выплыла интересная деталь:
g> В формулировке ничего не говорится про ограничение на размер начального состояния анализируемой машины.
Я не очень понимаю что за такой размер, на что он влияет и зачем о нём должно говориться.

g> Но оказывается, если задать верхнюю границу, сколь угодно большую, то проблема имеет тривиальное решение.
Не "задавать верхнюю границу", а ограничивать мощность вычислителя, сводя его на класс ниже чем МТ. Да, например, для Конечных Автоматов проблемы остановки нет. Но КА слишком слабые для решения большинства практических задач.

g> Вот это сильно вводит в заблуждение. Я, например, долгое время считал, что программа фиксированной начальной длины не разрешима в принципе.
Док-во сабжа использует нумерацию всех программ — однозначное сопоставление числа каждой программе. Можно, например, просто текст программ сортировать по алфавиту. И суть в том, что совершенно неважно как именно присваиваются номера. Совершенно неважно какой длины программа. Результат сабжа от этого не зависит.
Можно переписывать программы на разных языках — МТ, лямбда-функции, РАМ-машина, что угодно — тоже не важно. Результат тот же.

g> Допускаю, что среди множества доказательств других проблем, опирающихся на проблему останова, могут оказаться связанные с этим ошибки.
g> Это как с код-стайлом, чем ляпать побыстрее лишь бы работало, имеет смысл писать понятнее, чтоб при сопровождении у людей не возникало проблем.
Это я не понял.

Здравствуйте, ·, Вы писали:

·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.
Дык полно таких задач. Например гипотеза Коллатца.

Здравствуйте, Sinclair, Вы писали:

S>Ни в одном из этих случаев мы так и не получим доказательства теоремы Ферма.
S>Единственная надежда — на то, что мы вдруг получим опровержение теоремы, найдя контрпример, влезающий в ограничения реальной машины.

Ну вот простая задача которая может остановиться, очень не сразу.

a^3+b^3+c^3 = 42 где a,b,c целые числа

не тривиальное решение:

a=-80538738812075974
b=80435758145817515
c=12602123297335631

было затрачено 1,3 миллиона часов расчёта в глобальной вычислительной сети Charity Engine

немного спутал с другой задачей вот:

a/(b+c)+b/(a+c)=c/(a+b)

a=18800081
b=1481089
c=19214131

Здравствуйте, ·, Вы писали:

·>На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.
Алгоритм детектирования циклов ничего по базе не ищет.

·>Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.
Именно в МТ они и существуют.

·>Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов).
Вы опять путаете математический аппарат регекспов с их реализацией. Обломить детектор циклов на ограниченной машине невозможно.

·>Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти.
Дело не в количестве планок памяти, а в ограничениях языка программирования.
Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.

·>Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.
В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.

·>Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.
Очень просто узнать — машина, на которой исполняется программа, лишена устройств ввода-вывода.

·>Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.
Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.

·>Почему ты так решил-то, что в принципе?
Потому, что невозможно перебрать множество целых чисел.

·>Вот задачу четырёх красок решили перебором.
Ну так она и не была сформулирована в терминах целых чисел.

·>Если мы поперебирали чего-то — и таки нашли решение, то нам просто повезло. А если перебор не нашел решения, то мы ничего не знаем, и решение неизвестно. Никакие циклодетекторы нам не помогут. Т.е. твой циклодетектор (и любой другой алгоритм) будет давать не два ответа, как ты обещаешь, а три: "да", "нет", "хз".
Нет, ровно два. Математику не обманешь.

·>В смысле "вооброжаемое"? Вполне конкретное.
Воображаемое — в том смысле, что вы просто представляете себе "ну вот будут такие четыре числа". Как будет выглядеть запись этих четырёх чисел в реальной физической машине?

·>Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны.
Конечно нужны. Вы же не знаете заранее, какого размера будут эти числа. Значит, под них нужно отводить неограниченную память. Вот вам и бесконечность.

·>Не для ограниченных машин в принципе (каждая машина может иметь разные ограничения), а для данной конкретной машины. Притом ответ уже заранее известен — на данном компе любой алгоритм остановится, т.к. кол-во ресурсов ограничено.
Нет конечно. Вот вам алгоритм, который не остановится на данном компе:

while(true);

·>Твой анализатор только лишь детектит определённый паттерн поведения и обнаруживает цикл состояний и в _некоторых_ случаях может выдать ответ с меньшим расходом ресурсов, чем тупой полный прогон проги. Т.е. это просто алгоритм обнаружения циклов. Сабж он не решает.
Тупой полный прогон проги, в которой есть бесконечный цикл, не даст вообще ничего. А прогон детектора циклов даст совершенно точный ответ — потому что никаких других "паттернов поведения" у программы на такой машине быть не может.

Здравствуйте, Sinclair, Вы писали:

S> ·>На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.
S> Алгоритм детектирования циклов ничего по базе не ищет.
Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.

S> ·>Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.
S> Именно в МТ они и существуют.
"Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. "
Алфавит и множество состояний — конечны. Правил перехода будет Q*A штук. Т.е. конечно число.
Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.

S> ·>Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов).
S> Вы опять путаете математический аппарат регекспов с их реализацией. Обломить детектор циклов на ограниченной машине невозможно.
Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа. При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.

S> ·>Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти.
S> Дело не в количестве планок памяти, а в ограничениях языка программирования.
S> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
Ага, но тогда она не сможет выполнять некоторые алгоритмы.

S> ·>Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.
S> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.

S> ·>Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.
S> Очень просто узнать — машина, на которой исполняется программа, лишена устройств ввода-вывода.
Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.

S> ·>Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.
S> Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.
Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.

S> ·>Почему ты так решил-то, что в принципе?
S> Потому, что невозможно перебрать множество целых чисел.
Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.

S> ·>Вот задачу четырёх красок решили перебором.
S> Ну так она и не была сформулирована в терминах целых чисел.
Какая разница в каких терминах она сформулирована?!

S> ·>не два ответа, как ты обещаешь, а три: "да", "нет", "хз".
S> Нет, ровно два. Математику не обманешь.
Значит ты себя обманываешь.

S> ·>В смысле "вооброжаемое"? Вполне конкретное.
S> Воображаемое — в том смысле, что вы просто представляете себе "ну вот будут такие четыре числа". Как будет выглядеть запись этих четырёх чисел в реальной физической машине?
В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.

S> ·>Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны.
S> Конечно нужны. Вы же не знаете заранее, какого размера будут эти числа. Значит, под них нужно отводить неограниченную память. Вот вам и бесконечность.
Если ты заранее знаешь, что именно _нужно_, то ответ на вопрос ты уже знаешь. В этом задача анализатора и заключается. Вот для теоремы ферма, как выяснилось — да, нужно. А для четырёх красок — не нужно, достаточно памяти для нескольких тысяч карт.

S> ·>Не для ограниченных машин в принципе (каждая машина может иметь разные ограничения), а для данной конкретной машины. Притом ответ уже заранее известен — на данном компе любой алгоритм остановится, т.к. кол-во ресурсов ограничено.
S> Нет конечно. Вот вам алгоритм, который не остановится на данном компе:
S>

S> while(true);
S>

Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.

S> ·>Твой анализатор только лишь детектит определённый паттерн поведения и обнаруживает цикл состояний и в _некоторых_ случаях может выдать ответ с меньшим расходом ресурсов, чем тупой полный прогон проги. Т.е. это просто алгоритм обнаружения циклов. Сабж он не решает.
S> Тупой полный прогон проги, в которой есть бесконечный цикл, не даст вообще ничего. А прогон детектора циклов даст совершенно точный ответ — потому что никаких других "паттернов поведения" у программы на такой машине быть не может.
Если детектор покажет отсутствие цикла на данном кол-ве памяти, но программа продолжает работать, то ответ "хз", т.к. прога может таки завершиться если дать ещё один байт.

Здравствуйте, ·, Вы писали:

·>Т.е. это не корректность доказательства мы обсуждаем, а корректность твоих убеждений.
Я, оказывается, финитист.

Здравствуйте, ·, Вы писали:
S>> Алгоритм детектирования циклов ничего по базе не ищет.
·>Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.
Описанный алгоритм — это динамический анализатор.

·>Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.
Состояние МТ — это комбинация Q и состояния ленты. Лента — бесконечна.

·>Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа.
В константу раз.
·>При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.
Это если ограничить машину только вычислением регекспов.

S>> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
·>Ага, но тогда она не сможет выполнять некоторые алгоритмы.
Ну и что? В реальности машин с бесконечной памятью не бывает, что означает недоступность для нас "некоторых алгоритмов". И ничего — индустрия жива и даже прибыльна.

S>> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
·>Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.
Пока что мы всё ещё о математике, а не о прикладных решениях. Для юзера NP-полная задача малоотличима от невычислимой.

·>Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.
Мы всё ещё говорим о математике. Мне неважно, на каких машинах будет исполняться программа, если я статически проверил, что в ней нет обращения к IO.

S>> Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.
·> Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.
Да хоть два массива указателей. 32-битная машина специально реализована так, чтобы иметь возможность эмулировать безлимитность памяти.
А если нас интересует решение проблемы останова, то у нас другая постановка задачи.

S>> Потому, что невозможно перебрать множество целых чисел.
·>Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.
Ну так все карты и не нужно. Решение задачи четырёх красок свелось к набору доказательств для относительно небольшого множества вариантов локальной топологии.
Именно поэтому его и удалось получить. Если бы математики попробовали доказать эту теорему путём лобового перебора всех карт, то точно так же не получили бы никакого решения.
·>Какая разница в каких терминах она сформулирована?!
Большая. Если вы хотите решать перебором задачу, где нужно перебирать все целые числа, то вы обречены.

·>Значит ты себя обманываешь.


·>В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.
Ну так МТ построить-то невозможно. "Инженерные заморочки" — это как раз и есть "приземление" абстрактных математических концепций в реальный мир.
В реальном мире "числа" имеют вполне конечную разрядность.

·>Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.
Нет конечно. Остановка — это выполнение команды HALT. Даже если выключить электричество, никакого HALT выполнено не будет.

·>Если детектор покажет отсутствие цикла на данном кол-ве памяти, но программа продолжает работать, то ответ "хз", т.к. прога может таки завершиться если дать ещё один байт.
Мы ходим по кругу. Программе, написанной в терминах ограниченной памяти, невозможно "дать ещё один байт".

Здравствуйте, Sinclair, Вы писали:

S> S>> Алгоритм детектирования циклов ничего по базе не ищет.
S> ·>Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.
S> Описанный алгоритм — это динамический анализатор.
Ок, пусть, не важно как он называется. В первую очередь это просто алгоритм поиска цикла в списке, ну да, он применён к состояниям некоего вычислителя. Важно то, что этот "анализатор" не имеет ничего общего с Анализатором, который используется в док-ве сабжа и никоим образом док-во не опровергает.

S> ·>Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.
S> Состояние МТ — это комбинация Q и состояния ленты. Лента — бесконечна.
А что такое Q по-твоему?! В любом случае, это какая-то странная терминология, откуда ты её взял — неясно, она неправильная и вызывает путаницу. Я использую общепринятую:

Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина.

И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
Там просто отсутствует какое либо ограничение на движение головки — каждое правило перехода содержит команду движения головки — влево или вправо. Всё. Ни в МТ, ни в сабже никакие бесконечности не используются.

S> ·>Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа.
S> В константу раз.
Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.

S> ·>При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.
S> Это если ограничить машину только вычислением регекспов.
Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.

S> S>> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
S> ·>Ага, но тогда она не сможет выполнять некоторые алгоритмы.
S> Ну и что? В реальности машин с бесконечной памятью не бывает, что означает недоступность для нас "некоторых алгоритмов". И ничего — индустрия жива и даже прибыльна.
Они становятся доступны, если запрограммировать алгоритм по-другому. Впрочем, в любом случае сабж никак не запрещает существованию индустрии.

S> S>> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
S> ·>Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.
S> Пока что мы всё ещё о математике, а не о прикладных решениях. Для юзера NP-полная задача малоотличима от невычислимой.
Под словом "пракика" я и понимал прикладные решения. А в математике всё равно — ограничение по времени или по памяти.

S> ·>Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.
S> Мы всё ещё говорим о математике. Мне неважно, на каких машинах будет исполняться программа, если я статически проверил, что в ней нет обращения к IO.
Если у неё ограничена память, то это конечный автомат с т.з. математики.

S> ·> Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.
S> Да хоть два массива указателей. 32-битная машина специально реализована так, чтобы иметь возможность эмулировать безлимитность памяти.
Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.

S> А если нас интересует решение проблемы останова, то у нас другая постановка задачи.
Не понял. Решение проблемы останова — известно, т.к. есть док-во.

S> S>> Потому, что невозможно перебрать множество целых чисел.
S> ·>Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.
S> Ну так все карты и не нужно. Решение задачи четырёх красок свелось к набору доказательств для относительно небольшого множества вариантов локальной топологии.
Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.

S> Именно поэтому его и удалось получить. Если бы математики попробовали доказать эту теорему путём лобового перебора всех карт, то точно так же не получили бы никакого решения.
Ты не поверишь, но теорему Ферма тоже доказали без лобового перебора всех чисел.
Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.

S> ·>Какая разница в каких терминах она сформулирована?!
S> Большая. Если вы хотите решать перебором задачу, где нужно перебирать все целые числа, то вы обречены.
Дык сабж как раз о том, что неизвестно, нужно ли перебрать всё или не нужно!
Как выяснилось, что ни для теоремы ферма, ни для раскраски карт — не нужно.
Но ты можешь найти кучу задач для которых тупо неизвестно. Проблема Гольдбаха, например.

S> ·>В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.
S> Ну так МТ построить-то невозможно. "Инженерные заморочки" — это как раз и есть "приземление" абстрактных математических концепций в реальный мир.
S> В реальном мире "числа" имеют вполне конечную разрядность.
Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.

S> ·>Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.
S> Нет конечно. Остановка — это выполнение команды HALT. Даже если выключить электричество, никакого HALT выполнено не будет.
Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?

S> ·>Если детектор покажет отсутствие цикла на данном кол-ве памяти, но программа продолжает работать, то ответ "хз", т.к. прога может таки завершиться если дать ещё один байт.
S> Мы ходим по кругу. Программе, написанной в терминах ограниченной памяти, невозможно "дать ещё один байт".
Так и в ограниченной по времени программе невозможно дать ещё одну секунду.
Ещё раз повторю. Это эквивалентные ограничения.
Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".

Здравствуйте, ·, Вы писали:

·>Ок, пусть, не важно как он называется. В первую очередь это просто алгоритм поиска цикла в списке, ну да, он применён к состояниям некоего вычислителя. Важно то, что этот "анализатор" не имеет ничего общего с Анализатором, который используется в док-ве сабжа и никоим образом док-во не опровергает.
Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.

·>

·>Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина.

·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
Эмм, кто-то из нас невнимательно читает.

В состав машины Тьюринга входит неограниченная в обе стороны лента

Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.

S>> В константу раз.
·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?

·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?

·>Они становятся доступны, если запрограммировать алгоритм по-другому. Впрочем, в любом случае сабж никак не запрещает существованию индустрии.
Отож.

·>Под словом "пракика" я и понимал прикладные решения. А в математике всё равно — ограничение по времени или по памяти.
Ок.
·>Если у неё ограничена память, то это конечный автомат с т.з. математики.
Угу.
·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.

·>Не понял. Решение проблемы останова — известно, т.к. есть док-во.

— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетинившись. — Мы хотим знать, как ее решать.

(С) АБС.

·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
Это просто означает, что "решение" при помощи полного перебора вообще решением не является.

·>Ты не поверишь, но теорему Ферма тоже доказали без лобового перебора всех чисел.
Отчего ж не поверю — поверю
·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
"Забить в базу" не так легко, как кажется.
1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
2. алгоритм вычисления этой формулы может быть запрограммирован по-разному. Простого "побитового" сравнения кода программы недостаточно — нужно доказать, что некое вычисление эквивалентно этой формуле. Если я не ошибаюсь, то это — частный случай теоремы Райса. Так что упс.

·>Но ты можешь найти кучу задач для которых тупо неизвестно. Проблема Гольдбаха, например.
А ещё я могу найти кучу функций, которые являются невычислимыми. Несмотря на то, что однозначность решения легко доказать.

·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.

·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
Ни в какой. Эта МТ не останавливается.
А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.

·>Ещё раз повторю. Это эквивалентные ограничения.
·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся". Какой смысл в таком "детекторе"?

Здравствуйте, Sinclair, Вы писали:

S>Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.
Верно. И выдаёт результат не относящийся к сабжу.

S>·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
S>Эмм, кто-то из нас невнимательно читает.
S>

S>В состав машины Тьюринга входит неограниченная в обе стороны лента

Это не _определение_ МТ. Открой мат-формализацию МТ и ткни пальцем где там ∞.

S>Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.
И перестаёт быть МТ и формализацией алгоритма.

S>·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
S>Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?
Нет. Я сказал, что проще тупо запустить регулярку и подождать когда она закончится, чем запускать её под твоим циклоанализатором который просто интерпретирует эту же регулярку дважды и не даёт никакого полезного результата.

S>·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
S>А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?
Зацикливаться конечный автомат не может. Он всегда завершает свою работу.

S>·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
S>Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.
Это ты что-то сочиняешь. Оракл это вполне определённая конструкция в ТА: https://en.wikipedia.org/wiki/Oracle_machine
Машине Тьюринга не надо давать бесконечную память (что бы это ни значило) — посмотри на сам формализм МТ. Надо просто выполнять движение головки вправо-влево.

S>·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
S>Это просто означает, что "решение" при помощи полного перебора вообще решением не является.
Для некоторых задач — является. Начали перебирать и таки нашли решение.

S>·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
S>"Забить в базу" не так легко, как кажется.
Потому что сабж.

S>1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
Я имею в виду программу for(a,b,c,n in 2..){if(a^n+b^n=c^n) print(1);} — напечатает ли эта программа "1"? Поможет ли твой циклодетектор ответить на этот вопрос?

S>2. алгоритм вычисления этой формулы может быть запрограммирован по-разному. Простого "побитового" сравнения кода программы недостаточно — нужно доказать, что некое вычисление эквивалентно этой формуле. Если я не ошибаюсь, то это — частный случай теоремы Райса. Так что упс.
Это частный случай сабжа (точнее этот вопрос сводится к сабжу).
И ты немного путаешь опять. Для неких вычислений доказать эквивалентность таки можно алгоритмически. Невозможно построить алгоритм, который сравнит любые данные вычисления. Т.е. результатом любой возможной реализации алгоритма проверки эквивалентности будет "да", "нет", "хз". Всё ровно так же как и с твоим циклодетектором. Потому что сабж.

S>·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
S>Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.
Так назови его, если сможешь. Вон некоторые до Graham's number досчитали. Ты почему-то считаешь, что числа непременно надо поразрядно представлять. Можно и символьные выражения использовать. Число записанное как "2^1000" — занимает всего 6 байт.
А достаточно в коде появится int64 счётчику и твой циклодетектор станет абсолютно бесполезен на практике. Что и происходит в большинстве реальных случаев, твой анализатор будет отвечать "цикл не найден" почти всегда. Вот это уже подлянка Райса.

S>·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
S>Ни в какой. Эта МТ не останавливается.
S>А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.
Только это уже другая программа будет. Т.е. вместо исходной задачи f(n) ты неявно анализируешь f(n), n<N, но почему-то заявляешь, что результат анализа даёт информацию об исходной задаче.

S>·>Ещё раз повторю. Это эквивалентные ограничения.
S>·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
S>Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся".
Не понял с чего это вдруг. В худшем случае, просто будет требовать в константу раз больше памяти.

S>Какой смысл в таком "детекторе"?
Ровно такой же, какой в твоём циклодетекторе.