Каковы самые простые примеры программ, которые мы не знаем, заканчиваются ли они?

27

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

MaiaVictor
источник
Вы противоречите в своих ответах ..... Спасибо! Но программа остановки предполагает знание источника. ... Если это правда, вы ответили на свой вопрос. Программа остановки уже знает. Представьте себе систему, контролирующую знак, он всегда горит и мигает, когда он отключается? Сбой питания, выключатель питания или во время последовательности вспышки. Или с учетом резервного аккумулятора и генератора, никогда.
htm11h
Я бы добавил, что проблема остановки - это проблема, только если вы не поставили верхнюю границу времени. Конечно, на практике нет никакой разницы между получением ответа слишком поздно, чтобы быть полезным, и никогда не получая ответа. Вы можете спросить, вернет ли программа ответ в течение нескольких шагов, например, определение правильности в реальном времени. Если вы не можете гарантировать своевременный ответ, то у вас просто есть программа, в которой нет гарантии правильности.
Роб
1
@Rob Это не совсем так. Если вы не знаете, остановится ли машина, вы можете подождать, пока она не остановится; после тысячелетия вы все равно не будете знать, прекратится ли это, скажем, на следующий день.
Кайл Стрэнд,
@KyleStrand Я согласен с тобой. Но я также говорю, что на практике это полностью раздутый вопрос, потому что все реалистичные вычисления ограничены сроками (от миллисекунд до месяцев). Если вам нужен ответ в течение 5 секунд, чтобы он был полезен, единственное, что имеет значение, - можете ли вы гарантировать ответ в течение 5 секунд. Предположим, что вы можете гарантировать ответ, учитывая неопределенное количество времени для вычисления. Это было бы бесполезной гарантией.
Роб

Ответы:

41

Довольно простым примером может служить программа, проверяющая гипотезу Коллатца :

f(n)={HALT,if n is 1f(n/2),if n is evenf(3n+1),if n is odd

Это известно , чтобы остановить по до , по крайней мере , но в целом это открытая проблема.n5×2605.764×1018

npostavs
источник
9
Чтобы подчеркнуть мою точку зрения из комментария под вопросом: проблема " останавливается ли для всех ?" вычислим . f(n)n
Рафаэль
6
@KyleStrand Смотрите здесь .
Рафаэль
10
@KyleStrand, Рафаэль на 100% правильный. Это распространенное заблуждение. Вы должны тщательно проследить, что говорится в определении, и тогда вы обнаружите, что ваша интуиция не совсем соответствует определению. Согласно определению вычислимости, достаточно того, что существует машина Тьюринга для ее вычисления - не имеет значения, знаем ли мы, что это за машина Тьюринга. При первом взгляде на это многие студенты думают, что это обман, но это не так - это всего лишь следствие определения.
DW
2
@KyleStrand Вы должны избавиться от идеи, что программа должна решить проблему . Это не. Он просто должен вывести ответ, что является тривиальной задачей. Алгоритмически проблемы с конечными наборами экземпляров скучны, так как мы можем жестко закодировать ответы. (И даже если мы не знаем ответов, мы все равно знаем, что существует правильный алгоритм.) В общем, показывая, что для чего-то не существует алгоритма, вы не можете делать какие-либо предположения о том, как это происходит. Работа. Наше отсутствие воображения не дает доказательства.
Рафаэль
2
@KyleStrand Afaik, я использую стандартное определение вычислимости, которому его учат сегодня (и, на самом деле, десятилетиями). Я рекомендую вам усвоить ответы и связанный материал и поработать там, где вы ошиблись. Мне и другим не имеет смысла повторять одно и то же снова и снова. Еще одна попытка: определение вычислимости изначально экзистенциально, а не конструктивно. Пока вы думаете в рамках классической логики, совершенно не нужно иметь возможность передавать «решающий» алгоритм - мы просто должны показать, что есть один, который дает правильные ответы.
Рафаэль
31

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

«Мы» не являются алгоритмом =) Не существует общего алгоритма, который мог бы определить, останавливается ли данная программа для каждой программы .

Каковы самые простые (самые маленькие) известные примеры таких программ?

Рассмотрим следующую программу:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

Функция is_perfect проверяет, является ли n идеальным числом . Неизвестно, существуют ли какие-то нечетные совершенные числа, поэтому мы не знаем, останавливается ли эта программа или нет.

avsmal
источник
7
Мы алгоритм.
PyRulez
3
@PyRulez нет никаких доказательств того, что вычислительная мощность человеческого разума эквивалентна машине Тьюринга. Доказательство не работает, например, неизвестно, как симулировать один разум в другом.
avsmal
1
@avsmal Хорошо, но крайне маловероятно, что мы способны к гиперкомпьютерам.
PyRulez
2
@PyRulez Джон Лукас и Роджер Пенроуз предположили, что человеческий разум может быть результатом какого-то квантовомеханически улучшенного «неалгоритмического» вычисления. Это сильное предположение. Но, по крайней мере, наш разум может иметь некоторый источник неопределенности. И этого достаточно, чтобы сломать доказательство: невозможно опровергнуть «рандомизированную» (для некоторого подходящего определения того, что рандомизированное среднее) машину Тьюринга, если неизвестно, останавливается ли она.
avsmal
5
Квантовые вычисления считаются гиперкомпьютерами? Я предположил, что квантовые компьютеры могут быть идеально смоделированы машинами Тьюринга - чуть медленнее.
MaiaVictor
10

Ты пишешь:

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

Это не sequitur, в обоих направлениях. Вы уступаете распространенному заблуждению, к которому стоит обратиться.

Для любой фиксированной программы ее проблема остановки («Всегда ли останавливается?») Всегда разрешима, потому что ответ - «да» или «нет». Даже если вы не можете сказать, что это, вы знаете, что один из двух тривиальных алгоритмов всегда отвечает «да», соответственно. «нет» решает проблему останова.PPP

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

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

Еще немного связанных чтения:


Итак, вы видите, что ваш фактический вопрос (как повторяется ниже) не имеет ничего общего с тем, является ли проблема остановки вычислимой. Вообще.

Каковы самые простые (самые маленькие) известные примеры [программ, которые мы не знаем, чтобы остановить или зациклить]?

Это само по себе является правильным вопросом; другие дали хорошие ответы. По сути, вы можете преобразовать каждое утверждение с неизвестным значением истинности в пример, при условии, что оно имеет значение истинности:S

g(n)={1,S true,g(n+1),else.

Конечно, это не очень "естественно".


  1. Не обязательно все , но «многие» в некотором смысле. Бесконечно много, по крайней мере.
Рафаэль
источник
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Рафаэль
Чтобы попытаться перефразировать это для моего собственного понимания, правильно ли сказать, что, хотя нет уникального алгоритма, который может определить, останавливается ли какая-либо произвольная заданная программа, вполне может существовать некоторый программный алгоритм для решения проблемы остановки любой возможной программы?
Асад Саидуддин
@AsadSaeeduddin Это «хуже»: для каждого данного конечного набора программ проблема остановки является тривиальной . Каждое конечное множество разрешимо.
Рафаэль
7

Любая открытая проблема, касающаяся существования числа с определенными свойствами, порождает такую ​​программу (ту, которая ищет такое число). Например, возьмите гипотезу Коллатца; поскольку мы не знаем, правда ли это, мы также не знаем, завершается ли следующая программа:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  
Клаус Дрегер
источник
6

Учитывая, что проблема занятого бобра не решена для машины Тьюринга с 5 состояниями и 2 символами, должна быть машина Тьюринга только с пятью состояниями и только двумя символами, которые не были показаны для остановки или нет при запуске для пустой ленты , Это очень короткая, лаконичная и закрытая программа.

не-а-пользователь
источник
0

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

Вход: n . Вывод: Y / N существует не менее n двойных простых чисел.

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

Другой пример, возьмите гипотезу Римана и рассмотрите этот язык:

Вход: n . Вывод: Y / N существует не менее n нетривиальных нулей дзета-функции Римана.

алгоритм ищет нетривиальные нули (код не особенно сложен, он похож на поиск корней, и есть другие относительно простые эквивалентные формулировки, которые в основном вычисляют суммы «четности» всех простых чисел, меньших x и т. д.) и останавливается, если он находит n из них и, опять же, неизвестно, является ли этот язык разрешимым, а разрешение «почти» эквивалентно решению гипотезы Римана.

Теперь, как насчет еще более впечатляющего примера? ( Предостережение, вероятно , более спорным, а)

Входные данные: c: Выходные данные: Да / Нет, существует алгоритм O (n c ) для SAT.

аналогично, разрешение разрешимости этого языка почти эквивалентно проблеме P vs NP . однако в этом случае есть менее очевидный случай для «простого» кода.

ВЗН
источник
1
Неужели даунотер объяснит, что не так с этим ответом?
MaiaVictor
2
Ваш "двойной главный" язык является разрешимым. Если есть только конечное число из них, ответ "Да" дляn NNnNNa,b,can+bn=cnnN=2
vonbrand
3
Я не downvoter, но все претензии в этом ответе неверны. Все три из этих проблем доказуемо разрешимы (без необходимости делать какие-либо недоказанные предположения). Для чего, внимательно изучите ответ Рафаэля.
DW
Хорошо, может быть, для ввода необходимо указать TM, и алгоритм решит, вычислит ли TM проблему. нужно подумать об этом больше ... думаю, что есть какой-то простой рецепт для таких проблем, в основном связывающий открытые проблемы с неразрешимыми языками ... но согласился, что это редко документируется / формулируется в ссылках CS ... нашли только несколько разбросанных ссылки ... или, возможно, входные данные являются доказательством, и язык проверяет, является ли доказательство правильным ... другие ответы с высоким рейтингом упоминают нечетные совершенные числа, проблему коллатца и т. д. ... программы неизвестны для остановки или не для определенных констант ,
15:30
извините за путаницу! по некоторым соображениям, утверждения верны в том виде, в котором они описывают простые программы, о которых известно, что они не заканчиваются (для всех входных данных) (т. е. исходный вопрос), и провал общей идеи, набросанной / указанной DW, пытается преобразовать каждую в неразрешимые языки. продолжит размышлять над этой последней конструкторской идеей в поисках удачной. Другой способ взглянуть на это состоит в том, что проблемы можно рассматривать как отдельные экземпляры / входные данные для решателя проблемы остановки, но на самом деле (как известно, не эквивалентно) самой проблеме остановки.
vzn
0

1n1050

1020

gnasher729
источник