Вопрос по computer-science, halting-problem – Что именно является проблемой остановки?

52

Всякий раз, когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: «Если вы просто добавите один цикл, вы получите программу остановки и, следовательно, вы не сможете автоматизировать».task& Quot;

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

Но кое-что из этого кажется нелогичным. Что, если бы я писал программу решения проблем, которая принимает исходный код.[email protected]$ ./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;
}

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

Опять же, если вы намеренно напишите программу, которая содержит бесконечный цикл ... "решение проблемы остановки" это спорный вопрос, не так ли?

Множество вопросов, а не один, который действительно отвечает на оригинальный вопрос. doubleOrt
Суть вашего последнего примера (с методом DeterminesHalt) в том, что ваш методWRONG в этом случае. Например, если вы запустите Main на Main.java, это будет равносильно тому, чтобы сказать: «Эта программа останавливается, если она работает вечно, и работает вечно, если она останавливается». Парадокс! Будьте осторожны: ваш компьютер может растаять. agorenst
Вы не должны использовать программы на Си, чтобы показать проблемы вычислительной теории. Важно, чтобы вы выбрали очень простую модель, чтобы ее было легче понять. Вы можете составить так много странных случаев с реальными языками программирования, что становится почти невозможно понять. Этого не происходит с Turingmachines или WHILE-Programms или & # xB5; -рекурсивными функциями. И, в конце концов, они одинаково мощны для любого нормального языка программирования. pmr
Напишите программу, которая завершается только тогда, когда она находит решение открытого вопроса; как скажем, первое идеальное нечетное число. Теперь примените свою технику для решения проблемы остановки к этой программе. Проблема остановки не о циклах, а о теории вычислений. Kevin Montrose♦
@Kevin, или даже лучше, взять в качестве входных данных программу, которая вычисляет последнее идеальное число. Это может остановиться, а может и нет. Не было доказано, что ряд бесконечен или конечен. Bob Cross

Ваш Ответ

22   ответа
0

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

0

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

51

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

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.

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

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

Тот факт, что вы не можете контролироватьinput для программы это не очень важно, потому что, учитывая любую (программа, вход) пару (P, I), вы можете тривиально создать новую программу Q, которая не требует ввода и выполняет точно то же, что и P для I. (и спрашивает, останавливается ли Q .)
@ ShreevatsaR, я согласен, что любой конкретный вклад исчисляется по степени. Общий набор возможных входов не является. Однако я согласен с вами, что недостаточно сказать «эй, а что, если я жестко закодировал ввод? Тогда я буду на Easy Street! ;-)
Нет, множество всех PxI все еще счетно бесконечно. (Декартово произведение любых двух счетных множеств счетно!) Я не говорю, что проблема тривиализирована, напротив, я объяснял, что «вход» часть не то, что делает проблему трудной; даже просто решить, являются ли программы, которые не останавливают ввод, неразрешимыми.
@ Донал, нет, вы не можете. Вы принимаете априорные знания. Вы не знаете, какой вклад я собираюсь предоставить заранее, и у меня есть полная свобода ввода. После того, как я предоставлю ввод, вы можете переписать программу так, как если бы этот ввод был заранее заданной константой, но это было бы пустой тратой времени. Вы не решаете общую проблему в этот момент, вы пытаетесь решить один конкретный пример. Это равносильно высказыванию «если я уже знаю ответ, я могу доказать его правильность».
Входные данные для машины Тьюринга представляют собой последовательность символов на входной ленте и, таким образом, являются счетными. (Для программы, независимо от того, является ли ее ввод последовательностью цифр или чем-то еще, набор всех «определяемых чисел» все еще исчисляется.) Что касается проблемы остановки, то ввод является счетным. (Тамis модель «реальных вычислений»; представленный Blum-Shub-Smale, но я не знаком с ним, и он, кажется, не очень используется.) Я не думаю, что этот момент стоит подчеркнуть, просто пытаясь избежать идеи, что «Если я пишите только программы, которые не принимают ввода, я могу решить, остановятся ли они & quot; :-)
7

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 году, но это не доказательство.

+1 хотя бы за упоминание очень богатой области проверки программ. Конечно, проблема остановки вообще неразрешима, но существует большой класс программ, которыеcan быть доказано, чтобы остановить.
Посмотрите на понятие завершенных функций в функциональном языке, называемом Idris, как пример того, как это встроено в компилятор.
5

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

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

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

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

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

Это зависит от того, может ли программа показываться примитивно-рекурсивной или нет. С помощью PR-программы (или ее эквивалента в каком-то другом стиле программирования) можно показать, что каждый цикл завершается, потому что вы можете найти метрику того, сколько работы ему осталось сделать, которая монотонно уменьшается. Но помимо PR существуют общие рекурсивные функции, в которых такие метрики неизвестны, и проблема остановки показывает, почему нет алгоритма для нахождения таких метрик.
1
2

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.

1

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

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

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

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

29

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

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

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

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

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

может кто-нибудь объяснить. H (p3, p3) и p2 (p2).
Да, это хороший ответ, но, пожалуйста, добавьте объяснение, взяв несколько случаев.
Как вы доказываете, что такая программа p3 существует? Если такой программы p3 не существует, p2 никогда не останавливается.
Я ненавижу, когда это происходит.
когда h принимает p2, p2, это делает вывод, что намерение p2 является рекурсивным, поскольку оно, очевидно, продолжает делегировать работу повторяющимся шаблонам и говорит, что оно не прекратится, нет необходимости запускать программу, вы просто используете исчисление языка и сделать выводы о том, как взаимодействуют последовательности преобразований среды. единственными неразрешимыми программами, по-видимому, являются программы с неразрешимыми алгебрами, такими как целые числа, двойные числа, если такие условия O (n) или выше, они неразрешимы, поскольку мы не можем показать, что они завершаются без их запуска.
2

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

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

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

Конечно ... это практически не решаемо. Но это теоретически решаемо. А кому не нравится немного бесполезная теория?
Вы можете рассмотреть DFA компьютеров, и тогда да, проблема остановки решаема. Однако я бы не назвал это практичным ни при каких обстоятельствах. Если вы рассматриваете жесткий диск как часть конечного автомата, вы получаете больше состояний, чем вы когда-либо могли бы перечислить.
О, Боже. Вам нужно подумать о том, во сколько возможных состояний может попасть компьютер с 4 ГБ ОЗУ!
Нет, теоретически это не решаемо, вот и весь смысл! И зачем в него вливать жесткие диски? Выясните, сколько состояний может находиться в C-64. Кстати, во всей вселенной всего 10 ^ 80 атомов.
Моя точка зрения в основном подразумевалась как «забавный факт», но я также намеревался проиллюстрировать некоторые различия между теорией и реальностью. Когда вы ДОКАЗЫВАЕТЕ, что проблема остановки является неразрешимой, вы фактически доказываете ее для машины Тьюринга. Проблема останова доказуемо разрешима на реальном компьютере. Если бы у вас была машина Тьюринга, чтобы запустить вторичную программу на имитируемом компьютере, то машина Тьюринга в конечном итоге гарантированно остановится и, таким образом, решит проблему остановки (на симулированном компьютере).
1

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

4.6 Problems

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

while x != 1 do
    if even(x)
        x = x/2
    else
        x = 3*x +1
для более подробного объяснения этой проблемы см. например:cecm.sfu.ca/organics/papers/lagarias  Дело в том, что это еще не доказано. Кстати: спасибо, что заставил меня искать проблему, хе-хе, я просто должен был знать.
это похоже на небольшую, легкую проблему. Но, сюрприз! Это открытая проблема математики: - Я написал в основном для удовольствия и как вызов;)
0

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

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

9

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

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

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 в противном случае?

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

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

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

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

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 к проблеме остановки, пришлось бы на самом деле запустить программу.

4

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

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

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

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

Я согласен с @ Cypher2100. Посмотрите на ответ Графика Нуба выше, который демонстрирует полное доказательство.
Вы забыли противоречие. Запустите свой Main на себя: если он определит, что остановится, он будет работать вечно. Но если он решит, что он будет работать вечно, он остановится. Следовательно, определение не может быть выполнено, и DeterminesHalt не может существовать.
0

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

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

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

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

Мы все должны начать где-нибудь!
Если вы действительно решили это, я думаю, вы могли бы сделать лучше, чем rentacoder.com. :)
И проект назывался «Супер отладчик». Хех. Ссылка на публикацию:rentacoder.com/RentACoder/misc/BidRequests/…
0

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

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

3

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

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

5

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

@Bob: Спасибо за редактирование! Жирные пальцы.
@ n8wrl, нет проблем. Я сделал то же самое в своем ответе ....
Это ничего не доказывает: программа проверки остановки может просто сказать «Да, она останавливается». и здесь нет противоречия. Аргументis самоссылочный, но он более тонкий, чем то, что вы говорите.
40

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

Существует функциональный язык под названиемIdris это имеет понятиеcomplete функции, которые, как доказано, завершаются за конечное время с учетом любого ввода, соответствующего определению типа для функции. Компилятор сообщит, если ваша функцияcomplete.
+1 для нетривиальных тестовых случаев!
2

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

20

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!

Похожие вопросы