Всякий раз, когда люди спрашивают о проблеме остановки, поскольку это относится к программированию, люди отвечают "Если вы просто добавляете один цикл, у вас есть программа остановки и, следовательно, вы не можете автоматизировать задачу"
Имеет смысл. Если ваша программа имеет бесконечный цикл, тогда, когда ваша программа запущена, вы не можете узнать, продолжает ли программа хрустнуть ввод, или если она просто циклически бесконечна.
Но некоторые из них кажутся противоположными интуитивными. Что делать, если я пишу решатель проблемы с остановкой, в качестве исходного кода которого используется исходный код. [email protected]$ ./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 или больше, программа остановится. На всех остальных входах он снова запустится".
Это означает, что даже с сотнями входов один должен быть в состоянии перечислить условия, на которых программа остановится. Действительно, когда я пишу программу, я всегда убеждаюсь, что у кого-то есть возможность ее прекратить! Я не говорю, что созданный список условий тривиально создавать, но для меня это не кажется невозможным. Вы можете вводить данные от пользователя, использовать их для расчета индексов указателей и т.д. - но это просто добавляет к числу условий, гарантирующих завершение работы программы, не делает невозможным их перечисление.
Так что же такое проблема с остановкой? Что я не понимаю о том, что мы не можем написать проблему для обнаружения бесконечных циклов? Или, почему "циклы" такие часто цитируемые примеры?
UPDATE
Итак, позвольте мне немного изменить вопрос: что такое проблема с остановкой, как это относится к компьютерам? И тогда я отвечу на некоторые из комментариев:
Многие говорили, что программа должна иметь дело с "любым произвольным вводом". Но в компьютерах нет ни одного произвольного ввода. Если я вводю только один байт данных, то у меня есть только 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;
}
Итак, для этого примера мы можем написать программу, чтобы сделать точную противоположность нашего метода магической остановки. Если мы каким-то образом определим, что данная программа остановится, мы просто прыгаем в бесконечный цикл; в противном случае, если мы определим, что программа находится в бесконечном цикле, мы заканчиваем программу.
И снова, если вы намеренно напишите программу, содержащую бесконечный цикл... "Решение проблемы с остановкой" - это спорный вопрос, не так ли?
