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

Question

Я прочитал несколько статей о больших вычислениях и проблеме остановки.Очевидно, что ВСЕ алгоритмы не могут сказать, остановятся ли они когда-либо, например:

while(System.in.readline()){

}

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

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

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

Кроме того, я ничего не говорил о языке программирования.А как насчет чисто функционального языка программирования?Можно ли там рассчитать?

Answer 1

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

Верхняя граница временной сложности ТМ говорит о порядке скорости, с которой число переходов, которые делает ТМ, увеличивается в соответствии с размером входных данных. В частности, если мы говорим, что TM выполняет алгоритм, который является O (f (n)) в худшем случае для входного размера n, мы говорим, что существуют такие n0 и c, что при n> n0 T (n) <= cf (n). Пока все хорошо. </p>

Теперь, что касается машин Тьюринга, то они могут не остановиться, то есть они могут работать вечно для некоторых входных данных. Ясно, что если для некоторого n *> n0 TM делает бесконечное число шагов, то не существует f (n), удовлетворяющих условию (с конечным n0, c), изложенному в последнем абзаце; то есть T (N)! = O (f (n)) для любого f. ХОРОШО; если бы мы могли с уверенностью сказать, что TM остановится для всех входов длины, по крайней мере, n0, для некоторых n0, мы свободны. Проблема в том, что это эквивалентно решению проблемы остановки.

Итак, мы заключаем следующее: если ТМ останавливается на входе n> n0 вечно, то мы не можем определить верхнюю границу сложности; кроме того, неразрешимой проблемой является алгоритмическое определение того, остановится ли TM на всех входах, превышающих фиксированное, конечное n0.

Answer 2

Причина, по которой невозможно ответить на вопрос " - программа 'while (System.in.readline ()) {}' остановится? " в том, что ввод не указан, поэтому в данном конкретном случае проблема заключается в отсутствии информации, а не в неразрешимости.

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

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

Кроме того, не существует конкретного экземпляра ' program + input ', который сам по себе неразрешим: с учетом конкретного экземпляра всегда можно (в принципе) построить алгоритм, который анализирует этот экземпляр и / или класс экземпляров, и вычисляет правильный ответ.

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

Я бы сказал, что большая буква " while (System.in.readline ()) {} " равна O (n), где n - размер ввода (можно увидеть программу в качестве основы, например, программы подсчета строк).

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

Таким образом, вопрос, который нужно задать, может быть следующим: « останавливает ли программа все возможные конечные входные данные, которые ей могут быть предоставлены? »

Если этот квестон можно свести к проблеме остановки или любой другой неразрешимой проблеме, то он неразрешим.

Оказывается, его можно уменьшить, как пояснено здесь: https://cs.stackexchange.com/questions/41243/halting-problem-reduction-to-halting-for-all-inputs

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

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