Разрешимость "делится на n с 23?"

Toma Radu-Petrescu спросил: 13 июня 2018 в 05:31 в: algorithm

У меня есть следующая проблема:

Пусть n - натуральное число, n > 10 ^ 100. Является ли n делимым с 23?

Является ли эта проблема полуразрешимой или разрешимой?

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

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


3 ответа

Есть решение
jacobm ответил: 13 июня 2018 в 05:59

Вы правы. Проблема заключается decidable , если вы можете написать алгоритм, который для любого ввода будет всегда принимать решение в конечном итоге. Для проблемы "n divisible на 23?" Рассмотрим следующий (плохой) алгоритм: начните с i = 1 и проверьте, меньше ли 23 * i , больше или равно n.

  • Если это меньше, чем n, increment i.
  • Если он равен n, верните true.
  • Если он больше, чем n, верните false.

Независимо от того, насколько велик n, этот алгоритм всегда будет выплюнуть ответ в конце концов, потому что вы можете только увеличивать i конечный количество раз до 23 * i больше, чем n. Это может занять огромное количество времени, но для целей разрешимости нам все равно. Поэтому этот алгоритм всегда принимает решение; таким образом, проблема разрешима.

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

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

Таким образом, существует алгоритм для проблемы с остановкой, который всегда возвращает true, если фактический ответ верен , но работает вечно, если фактический ответ ложный. Поэтому проблема с перекрытием является полуприемной.

Lakshay Garg ответил: 13 июня 2018 в 05:57
return (n % 23 == 0)

Не считается ли это алгоритмом? Кажется разрешимым для меня.

Пожалуйста, см. ответ Германн Дёппес , вы не хотите предполагать вычислимость модуля.

Bacon Bits ответил: 13 июня 2018 в 05:43
Я думаю, дело в том, что n - это число, которое слишком велико для деления, что и делает оператор modulo. Имейте в виду, что IEEE 754 недостаточно точен, чтобы представлять наименее значащие цифры.
Lakshay Garg ответил: 13 июня 2018 в 05:46
Но почему IEEE 754 имеет какое-либо отношение к разрешимости? В конце концов, число будет больше, чем мы могли бы сохранить, но это не мешает алгоритму быть разрешимым. Пока число имеет конечную длину, машина turing остановится и примет решение.
Hermann Döppes ответил: 13 июня 2018 в 05:54
Ну, но вы все равно можете пропустить это. Если я не могу принять разрешимость делимости, почему я должен считать вычислимость остатка?
Lakshay Garg ответил: 13 июня 2018 в 05:59
Я согласен с тем, что мой ответ предполагает вычислимость работы модуля (что легко продемонстрировать). Я обновляю свой ответ, чтобы отразить этот факт. Спасибо за указание на это.
Hermann Döppes ответил: 13 июня 2018 в 05:43

Да, это разрешимо. Чтобы дать более простой аргумент, чем Lakshay Garg:

  • Вы можете перечислить все числа k = 0, 1, 2, 3, 4, 5, ...
  • Вы можете умножьте их на 23.
  • Теперь идет интересный шаг:
    • Если 23 k меньше n, попробуйте следующее k.
    • Если 23 k = n, то n делится на 23. DONE.
    • Если 23 k больше n, мы можем остановиться, как и с любым дальнейшим k, мы будем превышать n дальше. Если мы не найдем k = n / 23 по этой точке, то нет и n равно not , делящемуся на 23. DONE.

Так как 23 n больше n, мы достигнем последнего последнего момента, когда k = n, что означает, что эта процедура завершается.