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

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

что называется градом чисел. Эти числа образуют последовательность с этими правилами

f(n) is odd  -  f(n+1) = 3*f(n)+1
f(n) is even -  f(n+1) = f(n)/2
,

В настоящее время предполагается, что все начальные точки в конечном итоге достигнут 1, а затем повторяются4,2,1,4,2,1,4,2,1... Однако этому нет никаких доказательств. Так что сейчас единственный способ определить, заканчивается ли число при подаче в последовательность града, - этоactually compute it пока вы не достигнете 1.

Это ключ к тому, какI понять проблему остановки. Насколько я понимаю, это то, что вы не можетеfor sure знать, что программа будет / не остановится, если выactually run the program, Так что любая написанная вами программа может дать вам ответfor sure к проблеме остановки, пришлось бы на самом деле запустить программу.

что проблема остановки неразрешима.

Предположим, у вас есть программа H, которая вычисляет, останавливается ли программа. H принимает два параметра, первый - описание программы, P, а второй - вход, I. H возвращает true, если P останавливается на входе I, и false в противном случае.

Теперь напишите программу, p2, которая принимает, как вводит описание другой программы, p3. p2 вызывает H (p3, p3), затем зацикливается, если H возвращает true и останавливается в противном случае.

Что происходит, когда мы запускаем p2 (p2)?

Он должен зацикливаться и останавливаться одновременно, вызывая взрыв вселенной.

проблема с собакой, кроме программ вместо собак и остановки вместо лая.

ОтПрограммирование ЖемчугДжон Бентли

4.6 Problems

5. Докажите, что эта программа завершает работу, когда ее вход x является положительным целым числом.

while x != 1 do
    if even(x)
        x = x/2
    else
        x = 3*x +1

Теперь подумайте о всех остальных случаях.

Существует бесконечное количество возможных сценариев, вам придется перечислить их все.

Если, конечно, вы не могли бы обобщить это.

Вот тут и возникает проблема остановки. Как вы ее обобщаете?

http://en.wikipedia.org/wiki/Halting_problem, особенноhttp://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof чтобы понять, почему эта проблема не может быть решена алгоритмическим способом.

If you just add one loop, you've got the halting program and therefore you can't automate task;

Похоже на кого-то, кто обобщает применение проблемы остановки. Есть множество определенных циклов, которые вы можете доказать, что они прерываются. Существует исследование, которое может выполнять проверку завершения для широких классов программ. Например, в Coq вы ограничены программами, которые вы можете прекратить. У Microsoft есть исследовательский проект под названием Terminator, который использует различные приближения, чтобы доказать, что программы будут прекращены.

Но помните, что проблема остановки не только в игрушечных примерах. Ни один из них не решает общую проблему остановки, потому что они не работают для каждой программы.

Проблема в том, что проблема остановки говорит о том, что существуют программы, о которых вы не можете знать, завершатся ли они без их запуска, а это означает, что вы никогда не сможете решить, останавливаются ли они.

Пример программы, которая может или не может остановить (в Haskell):

collatz 1 = ()
collatz !n | odd n     = collatz (3 * n + 1)
           | otherwise = collatz (n `div` 2)

или в чем-то более доступном:

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

При каждом целом числе & gt; = 1 остановится ли эта программа? Ну, это сработало до сих пор, но нет теоремы, которая говорит, что она остановится для каждого целого числа. У нас естьconjecture из-заЛотар Коллатц это восходит к 1937 году, но это не доказательство.

что есть программа, которая может исследовать другую и определить, остановится она или нет. Загрузите программу проверки остановки самостоятельно, в программу проверки остановки - что она должна делать?

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

Посты, в которых говорится, что вы не можете алгоритмически вычислить, остановится ли произвольная программа, абсолютно верны для машины Тьюринга.

Дело в том, что не все программы требуют машин Тьюринга. Это программы, которые могут быть вычислены с концептуально «слабее» машина --- например, регулярные выражения могут быть полностью реализованы конечным автоматом, которыйalways останавливается на входе. Разве это не хорошо?

Держу пари, что когда люди говорят «добавить один цикл», они пытаются выразить идею, что, когда программа достаточно сложна, она требует машины Тьюринга, и, таким образом, применима проблема остановки (как идея).

Это может быть немного касательно вопроса, но я считаю, что, учитывая эту деталь в вопросе, на это стоило указать. :)

A proof from another perspective

Предположим, мы получили процессор с инструкциями вроде mov, add, jmp, но без in или out. И у нас есть память. В отличие от других процессоров, у этого есть другой регистр, называемыйparaReg, Этот регистр похож на файл, мы можем перемещать в него неограниченное количество контента, получать его размер, искать его в середине, удалять из него часть контента, что делается с помощью некоторых дополнительных инструкций.

Прежде чем мы начнем, давайте определимся с некоторыми словами.program это набор инструкций, который является строкой. Перед запуском программы мы очищаем все регистры и память до нуля, кроме paraReg, который содержит параметр (строку), а затем помещаем программу в нулевую ячейку памяти и устанавливаем регистр ip в ноль.process когда программа запущена.

Теперь проблема остановки может быть сформулирована так: для любой программы, называемой proObj (если она принимает параметр para0, мы добавляем в первую строку инструкцию: mov paraReg, para0), есть ли программа, которая принимает proObj в качестве параметр и может решить, будет ли proObj остановлен, когда proObj начнет работать с параметром paraReg, установленным на ноль?

Предположим, мы получили такую программу, которая называется p1. Затем мы можем создать другую программу с именем p2, которая принимает параметр para0. Через p1 мы можем сказать, остановится ли программа, содержимое которой para0, а ее параметр para0, остановится или нет. (Мы делаем это таким образом. Создайте программу, первая строка которой - [mov paraReg, para0], остальное - para0. Назовите эту программу pro0. Затем мы устанавливаем paraReg в pro0 и вызываем p1.) Если она остановится, мы позволим p2 войти в бесконечный цикл, в противном случае мы позволим p2 остановиться.

Если мы поместим p2 в paraReg и запустим p2, процесс остановится или нет? Если он останавливается из определения p2, мы знаем, что когда мы помещаем p2 в paraReg и запускаем p2, он не должен останавливаться; аналогично, если он не останавливается, мы знаем, что когда p2 помещается в paraReg и запускается p2, он должен останавливаться. Тогда мы можем сказать, что нет p2 и нет p1.

вам необходимо разработать алгоритм, который мог бы определить,any arbitrary программа останавливаетсяfor any arbitrary inputа не только относительно простые случаи в ваших примерах.

но я не видел, чтобы кто-то обращал внимание на тот факт, что в некотором роде сочетания теории и практичности проблема остановки действительно разрешима.

Итак, прежде всего, проблема остановки - это в основном задача написания программы, которая берет любую произвольную вторую программу и определяет, остановится ли вторичная программа на произвольном вводе. Итак, вы говорите: «Да, эта программа остановится на этом входе». или "Нет, это не победит". И на самом деле, это неразрешимо в общем случае (другие люди, кажется, уже предоставили доказательства этого) на машине Тьюринга. Реальная проблема заключается в том, что вы можете как-то выяснить, собирается ли что-то останавливаться, запустив его (просто подождите, пока он не остановится), но вы не можете действительно выяснить, не собирается ли что-то останавливаться при его запуске ( просто продолжай ждать вечно).

Это проблема машины Тьюринга, которая по определению имеет бесконечное количество памяти и, следовательно, бесконечно много состояний. Однако наши компьютеры имеют только ограниченный объем памяти. На компьютере всего несколько битов. Поэтому, если бы вы могли каким-либо образом отслеживать все предыдущие состояния (битовые конфигурации), которые вы видели во время работы программы, вы можете гарантировать, что ваша программа проверки никогда не войдет в бесконечный цикл. Если вторичная программа в конце концов останавливается, вы говорите "Да, эта программа остановится на этом вводе". Если вы видите одну и ту же битовую конфигурацию дважды, прежде чем она остановится, вы знаете "Нет, она не победит". Вероятно, не имеет большого технического значения, но хорошо знать, что во многих случаях это действительно "трудно" Те проблемы, с которыми мы сталкиваемся, сложнее в теории, чем в практике.

напротив, автоматизированное тестирование будет мало практического применения в разработке программного обеспечения (доказательство того, что программа останавливается, не доказывает, что онаcorrectи в любом случае гипотетический алгоритм обеспечивает доказательство только для данного конечного ввода, тогда как реальный разработчик программного обеспечения был бы более заинтересован в тесте дляall возможные конечные входы).

Скорее проблема остановки была одной из первых, чтобы быть доказаннойundecidableЭто означает, что не существует алгоритма, который работает в общем случае. Другими словами, Тьюринг доказал более 70 лет назад, что есть некоторые проблемы, которые компьютеры не могут решить - не только потому, что правильный алгоритм еще не найден, но и потому, что такой алгоритм не может существовать логически.

Проблема остановки в википедии.

Чтобы точно проиллюстрировать, почему простого применения некоторой техники к циклам недостаточно, рассмотрим следующую программу (псевдокод):

int main()
{
  //Unbounded length integer
  Number i = 3;

  while(true)
  {
    //example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc.
    Number[] divisiors = GetUniquePositiveDivisiors(i);
    Number sum = 0;
    foreach(Number divisor in divisiors) sum += divisor;

    if(sum == i) break;

    i+=2;
  }
}

Можете ли вы придумать подход, который вернет true, если этот код остановится, и false в противном случае?

Хорошо подумай.

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

poetic proof, написанные в стилеLewis Carroll Доктор Сьюз Джеффри Пуллум (он изЯзык Журнал известность).

Прикольные вещи. Вот вкус:

Here’s the trick that I’ll use – and it’s simple to do.
I’ll define a procedure, which I will call Q,
that will use P’s predictions of halting success
to stir up a terrible logical mess.

...

No matter how P might perform, Q will scoop it:
Q uses P’s output to make P look stupid.
Whatever P says, it cannot predict Q:
P is right when it’s wrong, and is false when it’s true!

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

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;
}

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

Независимо от того, сколько проверок ввода вы делаете, нет никакого возможного решения, чтобы определить, останавливается ли КАЖДАЯ программа, написанная или нет.

что вам нужно написать программу, которая выполняет следующие действия: - принимает произвольную программу - определяет, останавливает ли программа заданный произвольный конечный ввод в программу

Тем не менее, это действительно высокая планка. Существует много частичных решений проблемы остановки, но нет общего решения. Что еще хуже, даже найти программы, которые частично решают проблему остановки, как известно, сложно:

BBC h2g2 статья о проблеме остановки

Если вы действительно решили проблему остановки, то вам нужно работать на таких сайтах, как rentacoder.com. Несколько месяцев назад на одном из них было сообщение от пользователя ATuring, предложившего контракт для решения проблемы остановки. :)

глубиться в фон, есть хорошая книга на оригинальной статье Тьюринга,Аннотированная ТьюрингЧарльз Петцольд.

В соответствующем сообщении «в сторону», в действительности, в Интернете есть очень интересное эссе,Кто может назвать большее число? который наносит на машины Тьюринга и функции Аккермана.

который косит газон любого, кто не косит свой собственный газон, и спросить себя, действительно ли он косит свой собственный газон.

Хорошая математика, плохая математика недавно написалотличная дискуссия проблемы остановки с конкретными примерами.

The halting problem is basically a formal way of asking if you can tell whether or not an arbitrary program will eventually halt.

In other words, can you write a program called a halting oracle, HaltingOracle(program, input), which returns true if program(input) would eventually halt, and which returns false if it wouldn’t?

The answer is: no, you can’t.

Following up on questions about whether the input to the Halting problem is relevant or a red herring: Yes, the input is important. Also, there seems to be some confusion in that I see "infinite" being used where "arbitrary" is more correct.

Practical example: Представьте, что вы работаете в позиции QA, и вы должны написать программу проверки остановки (он же оракул), которая подтвердит это для любогоarbitrary Программа написана командой разработчиков (D) и любойarbitrary вход, предоставленный конечным пользователем (I), программа D в конечном итоге остановится, когда будет введен ввод I.

Cue manager voice: "Хо-хо, эти глупые пользователи, давайте удостоверимся, что независимо от того, какой мусор они печатают, наши серверные задачи никогда не окажутся в бесконечном цикле. Сделай так, код обезьяна! & Quot;

Это кажется отличной идеей, верно? Вы не хотите, чтобы ваш сервер зависал, верно?

Что говорит вам проблема остановки, так это то, что перед вами стоит неразрешимая задача. Вместо этого, в этом конкретном случае, вам нужно планировать задачи, которые выполняются с превышением порогового времени, и быть готовыми к их отмене.

Марк использует код вместо ввода, чтобы проиллюстрировать проблему:

def Deciever(i):
  oracle = i[0]
  in = i[1]
  if oracle(Deceiver, i):
    while True:
      continue
  else:
    return i

В моем обсуждении в комментариях я пошел путем злонамеренного манипулирования вводом, чтобы вызвать неразрешимую проблему. Пример Марка гораздо более элегантен, он использует оракула, чтобы победить себя:

So, the input to Deceiver is actually a list of two elements: the first one is a proposed halting oracle. The second is another input. What the halting killer does is ask the Oracle: “Do you think I’ll halt for input i?”. If the oracle says, “Yes, you’ll halt”, then the program goes into an infinite loop. If the oracle says “No, you won’t halt”, then it halts. So no matter what the oracle says, it’s wrong.

Говоря иначе, без обмана, переформатирования входных данных, исчисляемой / неисчисляемой бесконечности или каких-либо других отвлекающих факторов, Марк написал фрагмент кода, который может победитьany остановка оракула. Вы не можете написатьoracle что отвечает на вопросDeceiver когда-либо останавливается

Original answer:

От великогоВикипедия:

In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis.

Одним из критических моментов является то, что вы не можете контролировать ни программу, ни ввод. Вам вручают их, и вы сами отвечаете на вопрос.

Отметим также, что машины Тьюринга являются основой для эффективных моделей вычислимости. Иными словами, все, что вы делаете на современных компьютерных языках, может быть сопоставлено с этими архетипическими машинами Тьюринга. В результате, проблема остановки неразрешима на любом полезном современном языке.

что вы пишете алгоритм, который может проверять любой произвольный фрагмент кода и сообщать, останавливается ли он.

Теперь дай свой алгоритм самому проверить.

ВАШ ОТВЕТ НА ВОПРОС