Проблема с остановкой утверждает, что нет алгоритма, который бы определял, останавливается ли данная программа. Как следствие, должны быть программы, о которых мы не можем сказать, прекращаются они или нет. Каковы самые простые (самые маленькие) известные примеры таких программ?
computability
turing-machines
halting-problem
MaiaVictor
источник
источник
Ответы:
Довольно простым примером может служить программа, проверяющая гипотезу Коллатца :
Это известно , чтобы остановить по до , по крайней мере , но в целом это открытая проблема.n 5×260≈5.764×1018
источник
«Мы» не являются алгоритмом =) Не существует общего алгоритма, который мог бы определить, останавливается ли данная программа для каждой программы .
Рассмотрим следующую программу:
Функция is_perfect проверяет, является ли n идеальным числом . Неизвестно, существуют ли какие-то нечетные совершенные числа, поэтому мы не знаем, останавливается ли эта программа или нет.
источник
Ты пишешь:
Это не sequitur, в обоих направлениях. Вы уступаете распространенному заблуждению, к которому стоит обратиться.
Для любой фиксированной программы ее проблема остановки («Всегда ли останавливается?») Всегда разрешима, потому что ответ - «да» или «нет». Даже если вы не можете сказать, что это, вы знаете, что один из двух тривиальных алгоритмов всегда отвечает «да», соответственно. «нет» решает проблему останова.P P P
Только если вы требуете, чтобы алгоритм решал проблему остановки для всех программ, вы можете показать, что такой алгоритм не может существовать.
Теперь, зная, что проблема Остановки неразрешима, не подразумевает, что есть какие-то программы, которые никто не может доказать или завершить. Даже если вы не более мощны, чем машина Тьюринга (что является лишь гипотезой, а не доказанным фактом), все, что мы знаем, это то, что ни один алгоритм / человек не может предоставить такое доказательство для всех программ. Может быть другой человек, который может принять решение для каждой программы.
Еще немного связанных чтения:
Итак, вы видите, что ваш фактический вопрос (как повторяется ниже) не имеет ничего общего с тем, является ли проблема остановки вычислимой. Вообще.
Это само по себе является правильным вопросом; другие дали хорошие ответы. По сути, вы можете преобразовать каждое утверждение с неизвестным значением истинности в пример, при условии, что оно имеет значение истинности:S
Конечно, это не очень "естественно".
источник
Любая открытая проблема, касающаяся существования числа с определенными свойствами, порождает такую программу (ту, которая ищет такое число). Например, возьмите гипотезу Коллатца; поскольку мы не знаем, правда ли это, мы также не знаем, завершается ли следующая программа:
источник
Учитывая, что проблема занятого бобра не решена для машины Тьюринга с 5 состояниями и 2 символами, должна быть машина Тьюринга только с пятью состояниями и только двумя символами, которые не были показаны для остановки или нет при запуске для пустой ленты , Это очень короткая, лаконичная и закрытая программа.
источник
вопрос сложный, потому что разрешимость (формализация / обобщение проблемы остановки в CS-эквиваленте) связана с языками, поэтому ее необходимо переписать в этом формате. на это, похоже, не особо указывают, но многие открытые проблемы в математике / CS могут быть легко преобразованы в проблемы (языки) с неизвестной разрешимостью. это из-за тесного соответствия между доказательством теорем и (не) анализом разрешимости. например (чем-то похожий на другой ответ с нечетными совершенными числами), возьмите гипотезу о двойных простых числах, которая датируется греками (более 2 тысячелетий назад) и является предметом значительных недавних исследований, например, Чжаном / Тао. преобразовать его в алгоритмическую задачу следующим образом:
алгоритм ищет двойные простые числа и останавливается, если находит n из них. неизвестно, является ли этот язык разрешимым. Решение проблемы двойных простых чисел (которая спрашивает, существует ли конечное или бесконечное число) также разрешило бы разрешимость этого языка (если он также доказан / обнаружен, сколько существует, если он конечен).
Другой пример, возьмите гипотезу Римана и рассмотрите этот язык:
алгоритм ищет нетривиальные нули (код не особенно сложен, он похож на поиск корней, и есть другие относительно простые эквивалентные формулировки, которые в основном вычисляют суммы «четности» всех простых чисел, меньших x и т. д.) и останавливается, если он находит n из них и, опять же, неизвестно, является ли этот язык разрешимым, а разрешение «почти» эквивалентно решению гипотезы Римана.
Теперь, как насчет еще более впечатляющего примера? ( Предостережение, вероятно , более спорным, а)
аналогично, разрешение разрешимости этого языка почти эквивалентно проблеме P vs NP . однако в этом случае есть менее очевидный случай для «простого» кода.
источник
источник