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