Всякий раз, когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: «Если вы просто добавите один цикл, вы получите программу остановки и, следовательно, вы не сможете автоматизировать».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;
}

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

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