Какова точно проблема остановки?

РЕДАКТИРОВАТЬ (намного позже, чем исходный ответ): MarkCC из Хорошая математика, Плохая математика недавно написал отличное обсуждение проблемы остановки с бетоном примеры.

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

Другими словами, можете ли вы написать программа, называемая останавливающимся оракулом, HaltingOracle (программа, ввод), который возвращает истину, если программа (ввод) будет в конечном итоге остановка, и которая возвращается ложь, если нет?

Ответ: нет, нельзя.

Ответ на вопросы о том, является ли входной сигнал для проблемы остановки релевантным или отвлекающим маневром: Да, вход важен. Кроме того, кажется, есть некоторая путаница в том, что я вижу, что «бесконечный» используется там, где «произвольно» более правильно.

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

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

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

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

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

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

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

Итак, ввод в Deceiver на самом деле верно?

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

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

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

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

Итак, ввод в Deceiver на самом деле верно?

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

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

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

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

Итак, ввод в Deceiver на самом деле Я пошел по пути злонамеренных манипуляций с вводом, чтобы создать неразрешимую проблему. Пример Марка гораздо более элегантен, он использует останавливающийся оракул для победы над самим собой:

Итак, ввод в Deceiver на самом деле Я пошел по пути злонамеренных манипуляций с вводом, чтобы создать неразрешимую проблему. Пример Марка гораздо более элегантен, он использует останавливающийся оракул для победы над самим собой:

Итак, ввод в Deceiver на самом деле список из двух элементов: первый это предлагаемый останавливающийся оракул. В второй - еще один ввод. Что за останавливающийся убийца спрашивает оракула: «Как вы думаете, я остановлюсь на вводе i?». Если оракул говорит: «Да, ты остановка », затем программа перейдет в бесконечная петля. Если оракул говорит: «Нет, ты не остановишься », затем он останавливается. Так что нет независимо от того, что говорит оракул, это

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

Исходный ответ:

Из великой Википедии :

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

Алан Тьюринг доказал в 1936 году, что общий алгоритм решения проблемы остановки проблема для всех возможных программ-вводов пары не могут существовать. Мы говорим, что проблема остановки неразрешима Машины Тьюринга. Коупленд (2004) приписывает фактическое прекращение срока проблема для Мартина Дэвиса.

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

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

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

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

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

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

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

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

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. .. Однако доказательств этому нет. Итак, прямо сейчас единственный способ определить, заканчивается ли число при вводе в последовательность градин, - это фактически вычислить его , пока вы не дойдете до 1.

Это ключ к тому, как I ] понять проблему остановки. Насколько я понимаю, вы не можете наверняка знать, что программа остановится / не остановится, если вы не запустите программу . Итак, любая программа, которую вы пишете, которая может дать вам ответ наверняка на проблему остановки,

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

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

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

Как ваша программа решает гипотезу Коллатца ?

Из Programming Pearls , Джон Бентли

4.6 Проблемы

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

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

Вы перечислили несколько простых случаев.

Теперь подумайте о том, чтобы обдумать все остальные случаи.

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

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

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

It's a variant of the halting dog problem, except with programs instead of dogs and halting instead of barking.

Вот программа, которую проблема остановки никогда не сможет решить.

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

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

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

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

В википедии есть хорошее доказательство Проблемы с остановкой .

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

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

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

Подумайте внимательно .

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

In reference to the sub-point "people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task"", I'll add this detail:

The posts that say that you cannot algorithmically compute whether an arbitrary program will halt are absolutely correct for a Turing Machine.

The thing is, not all programs require Turing Machines. These are programs that can be computed with a conceptually "weaker" machine --- for example, regular expressions can be embodied entirely by a Finite State Machine, which always halts on input. Isn't that nice?

I wager that when the people say "add one loop", they're trying to express the idea that, when a program is complex enough, it requires a Turing Machine, and thus the Halting Problem (as an idea) applies.

This may be slightly tangential to the question, but I believe, given that detail in the question, this was worth pointing out. :)

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

Отличный пример Тьюринга был самореферентным. Предположим, есть программа, которая может исследовать другую и определить, остановится она или нет. Подайте САМ программу проверки останавливающейся программы в средство проверки программы остановки - что она должна делать?

«Если вы просто добавите один цикл, у вас будет программа остановки и, следовательно, вы не сможете автоматизировать задачу»

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

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

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

Пример программы, которая может или не может остановиться (в 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;

Учитывая каждое целое число> = 1, остановится ли эта программа? Что ж, до сих пор это сработало, но нет теоремы, которая говорит, что он будет останавливаться для каждого целого числа.

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

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

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

Пока много интересных конкретных примеров / аналогий. Если вы хотите углубиться в предысторию, есть хорошая книга по оригинальной статье Тьюринга, The Annotated Turing , Чарльза Петцольда

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

Это забито до смерти настолько хорошо, что на самом деле существует поэтическое доказательство , написанное в стиле Льюиса Кэрролла доктора Сьюз Джеффри Пуллума (он из Language Log известности)

Забавные вещи. Вот пример:

Вот трюк, который я воспользуюсь - и его просто сделать.
Я определю процедуру, которую назову Q,
который будет использовать предсказания P об остановке успеха
чтобы вызвать ужасную логическую неразбериху.

...

Независимо от того, как P может работать, Q вычерпает его:
Q использует вывод P, чтобы заставить P выглядеть глупо.
Что бы ни сказал P, он не может предсказать Q:
P прав, когда он неверен, и ложен, когда он верен!

Вот простое объяснение доказательства того, что проблема остановки неразрешима.

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

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

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

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

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

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