Что именно является проблемой остановки?

Всякий раз, когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: «Если вы просто добавите один цикл, вы получите программу остановки и, следовательно, вы не сможете автоматизировать».task& Quot;

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

Но кое-что из этого кажется нелогичным. Что, если бы я писал программу решения проблем, которая принимает исходный код.rascher@localhost$ ./haltingSolver source.c

Если мой код (source.c) выглядит так:

for (;;) {  /* infinite loop */  }

Похоже, моей программе было бы довольно легко это увидеть. & quot; Посмотри цикл и посмотри на условие. Если условие основано только на литералах, а не на переменных, то вы всегда знаете результат цикла. Если есть переменные (например, while (x & lt; 10)), посмотрите, были ли эти переменные когда-либо изменены. Если нет, то вы всегда знаете результат цикла. & Quot;

Конечно, эти проверки не будут тривиальными (вычисление арифметики указателей и т. Д.), Но это не кажется невозможным. например:

int x = 0
while (x < 10) {}

может быть обнаружен. наряду с - хотя и не тривиально

int x = 0
while (x < 10)
{
   x++;
   if (x == 10)
   {
      x = 0
   }
}

А как насчет ввода пользователя? Это кикер, это то, что делает программу непредсказуемой.

int x = 0;
while (x < 10) 
{
   scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}

Теперь моя программа может сказать: «Если пользователь введет 10 или больше, программа остановится. На всех других входах он снова зациклится. & Quot;

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

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

UPDATE

Итак, позвольте мне немного изменить вопрос: в чем проблема остановки?as it applies to computers? И тогда я отвечу на некоторые комментарии:

Многие люди говорят, что программа должна быть в состоянии справиться с «любым произвольным вводом». Но в компьютерах нет произвольного ввода. Если я введу только один байт данных, то у меня будет только 2 ^ 8 возможных входов. Итак, в качестве примера:

int c = getchar()

switch (c) {
   case 'q':
      /* quit the program */
}

Вдруг я только что учел все возможности. Еслиc имеет битовый шаблон 0x71, он делает одну вещь. Для всех других шаблонов он делает что-то еще. Даже программа, которая принимает произвольный ввод строки, никогда не бывает «произвольной», поскольку ресурсы конечны, что означает, что в то время как теория «произвольной» относится ... это не совсем один к одному с практикой.

Другой пример, на который ссылаются люди:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
    else 
        n /= 2;

Если n - 32-разрядное целое число ... тогда я могу визуально сказать вам, остановится ли это.

Я предполагаю, что это редактирование ни о чем не спрашивает, но самый убедительный пример, который я видел, этоэтот:

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

public bool DeterminesHalt(string filename, string[] args){
    //runs whatever program you tell it do, passing any args
    //returns true if the program halts, false if it doesn't
}

Теперь допустим, что мы пишем небольшой фрагмент кода, такой как ...

public static void Main(string[] args){
    string filename = Console.ReadLine(); //read in file to run from user
    if(DeterminesHalt(filename, args))
        for(;;);
    else
        return;
}

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

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

Ответы на вопрос(22)

Ваш ответ на вопрос