Когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: «Если вы просто добавите один цикл, у вас есть программа остановки и, следовательно, вы не сможете автоматизировать задачу».
Имеет смысл. Если ваша программа имеет бесконечный цикл, тогда, когда ваша программа работает, у вас нет возможности узнать, обрабатывает ли программа ввод или просто бесконечно зацикливается.
Но кое-что из этого кажется нелогичным. Что, если бы я писал программу решения проблем с остановкой, которая принимает исходный код в качестве входных данных. rascher@localhost$ ./haltingSolver source.c
Если мой код (source.c) выглядит так:
for (;;) { /* infinite loop */ }
Похоже, моей программе было бы довольно легко это увидеть. "Посмотрите цикл и посмотрите на условие. Если условие основано только на литералах, а не на переменных, вы всегда знаете результат цикла. Если есть переменные (например, while (x‹ 10)), посмотрите, есть ли эти переменные когда-либо изменяются. Если нет, то вы всегда знаете результат цикла ".
Конечно, эти проверки не были бы тривиальными (вычисление арифметики указателей и т. Д.), Но они не кажутся невозможными. например:
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 или больше, программа останавливается. При всех остальных вводах она повторяется снова».
Это означает, что даже с сотнями входов каждый должен иметь возможность перечислить условия, при которых программа остановится. Действительно, когда я пишу программу, я всегда убеждаюсь, что у кого-нибудь есть возможность ее завершить! Я не говорю, что итоговый список условий тривиально создать, но мне это не кажется невозможным. Вы можете получать данные от пользователя, использовать их для вычисления индексов указателей и т. Д., Но это просто увеличивает количество условий, гарантирующих завершение программы, и не делает невозможным их перечисление.
Так в чем именно проблема остановки? Что я не понимаю в идее, что мы не можем написать задачу для обнаружения бесконечных циклов? Или почему «петли» являются таким часто цитируемым примером?
ОБНОВЛЕНИЕ
Итак, позвольте мне немного изменить вопрос: в чем проблема остановки применительно к компьютерам? И затем я отвечу на некоторые комментарии:
Многие говорят, что программа должна иметь возможность обрабатывать «любой произвольный ввод». Но в компьютерах никогда не бывает произвольного ввода. Если я ввожу только один байт данных, то у меня есть только 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;
}
Итак, для этого примера мы можем написать программу, которая будет делать полную противоположность нашему магическому методу остановки. Если мы каким-то образом определяем, что данная программа остановится, мы просто переходим в бесконечный цикл; в противном случае, если мы определяем, что программа находится в бесконечном цикле, мы завершаем программу.
С другой стороны, если вы намеренно напишете программу, содержащую бесконечный цикл ... «решение проблемы остановки» - это своего рода спорный вопрос, не так ли?
