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

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

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

Ключевой частью формальной постановки проблемы является математическое определение компьютера и программы, обычно через машину Тьюринга . Затем доказательство показывает, что для любой программы f , которая может определять, останавливаются ли программы, существует «патологическая» программа g , для которой f делает неверное определение. В частности, g — это программа, которая при вызове с некоторыми входными данными передает свой собственный источник и свои входные данные в f и делает противоположное тому, что f предсказывает, что g будет делать. Поведение f на g показывает неразрешимость, поскольку это означает, что никакая программа f не решит проблему остановки во всех возможных случаях.

Фон

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

Например, в псевдокоде программа

while (true) continue

не останавливается; скорее, он продолжается вечно в бесконечном цикле . С другой стороны, программа

print "Hello, world!"

останавливается.

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

Последствия программирования

Некоторые бесконечные циклы могут быть весьма полезны. Например, циклы событий обычно кодируются как бесконечные циклы. ^[1] Однако большинство подпрограмм предназначены для завершения. ^[2] В частности, в жестких вычислениях в реальном времени программисты пытаются писать подпрограммы, которые не только гарантированно завершатся, но и гарантированно завершатся до заданного крайнего срока. ^[3]

Иногда эти программисты используют какой-либо язык программирования общего назначения (полный по Тьюрингу), но пытаются писать в ограниченном стиле, например, MISRA C или SPARK , что позволяет легко доказать, что полученные подпрограммы завершатся до указанного крайнего срока. ^{[ необходима цитата ]}

В других случаях эти программисты применяют правило наименьшей мощности — они намеренно используют компьютерный язык, который не является полностью полным по Тьюрингу. Часто это языки, которые гарантируют завершение всех подпрограмм, например Coq . ^{[ необходима цитата ]}

Распространенные ошибки

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

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

Проблема остановки теоретически разрешима для линейных ограниченных автоматов (LBA) или детерминированных машин с конечной памятью. Машина с конечной памятью имеет конечное число конфигураций, и поэтому любая детерминированная программа на ней должна в конечном итоге либо остановиться, либо повторить предыдущую конфигурацию: ^[4]

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

Однако компьютер с миллионом мелких деталей, каждая из которых имеет два состояния, будет иметь по крайней мере 2 1 ^{000 000} возможных состояний: ^[5]

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

Хотя машина может быть конечной, а конечные автоматы «имеют ряд теоретических ограничений»: ^[5]

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

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

История

В апреле 1936 года Алонзо Чёрч опубликовал своё доказательство неразрешимости проблемы в лямбда-исчислении . Доказательство Тьюринга было опубликовано позже, в январе 1937 года. С тех пор было описано много других неразрешимых проблем, включая проблему остановки, возникшую в 1950-х годах.

Хронология

• 1900 : Давид Гильберт задает свои «23 вопроса» (теперь известные как проблемы Гильберта ) на Втором международном конгрессе математиков в Париже. «Из них вторым было доказательство непротиворечивости « аксиом Пеано », от которых, как он показал, зависит строгость математики». ( 1900 ) ^[6]
• 1920  – 1921 : Эмиль Пост исследует проблему остановки для систем тегов , рассматривая ее как кандидата на неразрешимость. ^[7] Ее неразрешимость была установлена ​​гораздо позже Марвином Мински . ^[8] ( 1920 ) ( 1921 )
• 1928 : Гильберт переформулировал свою «Вторую проблему» на Болонском международном конгрессе. ^[9] Он поставил три вопроса: № 1: Была ли математика полной ? № 2: Была ли математика последовательной ? № 3: Была ли математика разрешимой ? ^[10] Третий вопрос известен как Entscheidungsproblem (проблема разрешимости). ^[11] ( 1928 )
• 1930 : Курт Гёдель объявляет доказательство в качестве ответа на первые два вопроса Гильберта 1928 года. ^[12] «Сначала он [Гильберт] был только зол и расстроен, но затем он начал пытаться конструктивно разобраться с проблемой... Сам Гёдель чувствовал — и выразил эту мысль в своей статье — что его работа не противоречит формалистической точке зрения Гильберта» ( 1930 ) ^[13]
• 1931 : Гёдель публикует «О формально неразрешимых предложениях Principia Mathematica и связанных с ними систем I» ( 1931 ) ^[14]
• 19 апреля 1935 г .: Алонзо Чёрч публикует «Неразрешимую проблему элементарной теории чисел», в которой предлагается, что интуитивное понятие эффективно вычислимой функции может быть формализовано общими рекурсивными функциями или, что эквивалентно, лямбда-определяемыми функциями . Он доказывает, что проблема остановки для лямбда-исчисления (т. е. имеет ли заданное лямбда-выражение нормальную форму ) не является эффективно вычислимой. ( 1935-04-19 ) ^[15]
• 1936 : Чёрч публикует первое доказательство того, что проблема Entscheidungsproblem неразрешима, используя понятие вычисления с помощью рекурсивных функций . ( 1936 ) ^[16]
• 7 октября 1936 г .: Получена статья Эмиля Поста ( 1936-10-07 ) ^{«Конечные комбинаторные процессы. Формулировка I». Пост добавляет к своему «процессу» инструкцию «(C) Stop». Он назвал такой процесс «типом 1... если определяемый им процесс завершается для каждой конкретной задачи». [17]}
• Май 1936  – январь 1937 : статья Алана Тьюринга «О вычислимых числах с приложением к Entscheidungsproblem» отправляется в печать в мае 1936 года и выходит в печать в январе 1937 года. ^[18] Тьюринг доказывает, что три проблемы неразрешимы: проблема «удовлетворения», проблема «печати» и Entscheidungsproblem . ^[19] Доказательство Тьюринга отличается от доказательства Чёрча тем, что вводит понятие вычисления машиной. Это один из «первых примеров проблем принятия решений, которые оказались неразрешимыми». ^{[20] [ нужна страница ]} ( 1936-05 ) ( 1937-01 )
• 1939 : Дж. Баркли Россер отмечает существенную эквивалентность «эффективного метода», определенного Гёделем, Чёрчем и Тьюрингом ( 1939 ) ^[21]
• 1943 : В своей статье Стивен Клини утверждает, что «при создании полной алгоритмической теории мы описываем процедуру... которая обязательно завершается, причем таким образом, что из ее результата мы можем получить определенный ответ «Да» или «Нет» на вопрос «Является ли значение предиката истинным?»». ( 1943 )
• 1952 : Клини включает обсуждение неразрешимости проблемы остановки для машин Тьюринга и переформулирует ее в терминах машин, которые «в конечном итоге останавливаются», т. е. останавливаются: «...не существует алгоритма для решения вопроса о том, остановится ли в конечном итоге любая данная машина, запущенная из любой данной ситуации ». ( 1952 ) ^[22]
• 1952 : Мартин Дэвис использует термин «проблема остановки» в серии лекций в Лаборатории систем управления в Университете Иллинойса в 1952 году. Вероятно, это первое подобное использование термина. ( 1952 ) ^[23]

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

Многие статьи и учебники относят определение и доказательство неразрешимости проблемы остановки к статье Тьюринга 1936 года. Однако это неверно. ^{[19] [24]} Тьюринг не использовал термины «остановка» или «остановка» ни в одной из своих опубликованных работ, включая статью 1936 года. ^[25] Поиск в академической литературе с 1936 по 1958 год показал, что первым опубликованным материалом, использующим термин «проблема остановки», был Роджерс (1957). Однако Роджерс говорит, что у него был черновик Дэвиса (1958), ^[19] а Мартин Дэвис утверждает во введении, что «эксперт, возможно, найдет некоторую новизну в расположении и трактовке тем», ^[26] поэтому терминология должна быть приписана Дэвису. ^{[19] [24]} Дэвис заявил в письме, что он ссылался на проблему остановки с 1952 года. ^[23] В книге Дэвиса это употребляется следующим образом: ^[27]

«[...] мы хотим определить, остановится ли [машина Тьюринга] Z, если ее поместить в заданное начальное состояние. Мы называем эту проблему проблемой остановки для Z. [...]

Теорема 2.2 Существует машина Тьюринга, проблема остановки которой рекурсивно неразрешима .

Связанной проблемой является задача печати для простой машины Тьюринга Z относительно символа S _i ".

Возможным предшественником формулировки Дэвиса является утверждение Клини 1952 года, которое отличается только формулировкой: ^{[19] [22]}

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

Проблема остановки эквивалентна по Тьюрингу как проблеме печати Дэвиса («печатает ли машина Тьюринга, начиная с заданного состояния, заданный символ?»), так и проблеме печати, рассмотренной в статье Тьюринга 1936 года («печатает ли машина Тьюринга, начиная с чистой ленты, заданный символ?»). Однако эквивалентность по Тьюрингу довольно свободна и не означает, что эти две проблемы одинаковы. Существуют машины, которые печатают, но не останавливаются, и останавливаются, но не печатают. Проблемы печати и остановки решают разные проблемы и демонстрируют важные концептуальные и технические различия. Таким образом, Дэвис просто скромничал, когда говорил: ^[19]

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

Формализация

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

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

Представление в виде набора

Традиционное представление задач принятия решений — это множество объектов, обладающих рассматриваемым свойством. Остановочное множество

K = {( i , x ) | программа i останавливается при запуске на входе x }

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

Этот набор рекурсивно перечислим , что означает, что существует вычислимая функция, которая перечисляет все пары ( i ,  x ), которые он содержит. Однако дополнение этого набора не является рекурсивно перечислимым. ^[28]

Существует много эквивалентных формулировок проблемы остановки; любой набор, степень Тьюринга которого равна степени проблемы остановки, является такой формулировкой. Примеры таких наборов включают:

• { i | программа i в конечном итоге останавливается при запуске с вводом 0}
• { i | существует вход x, такой что программа i в конечном итоге останавливается при запуске с входом x }.

Доказательство концепции

Кристофер Стрейчи набросал доказательство от противного , что проблема остановки неразрешима. ^{[29] [30]} Доказательство проводится следующим образом: предположим, что существует полная вычислимая функция halts(f) , которая возвращает true, если подпрограмма f останавливается (при запуске без входных данных), и возвращает false в противном случае. Теперь рассмотрим следующую подпрограмму:

def  g ():  если  останавливается ( g ):  loop_forever ()

halts(g) должен либо возвращать true, либо false, поскольку предполагалось, что halts является total . Если halts(g) возвращает true, то g вызовет loop_forever и никогда не остановится, что является противоречием. Если halts(g) возвращает false, то g остановится, поскольку он не вызовет loop_forever ; это также является противоречием. В целом, g делает противоположное тому, что halts говорит g , поэтому halts(g) не может возвращать значение истинности, которое согласуется с тем, останавливается ли g . Следовательно, первоначальное предположение о том, что halts является полной вычислимой функцией, должно быть ложным.

Набросок строгого доказательства

Концепция выше показывает общий метод доказательства, но вычислимая функция halts не принимает напрямую подпрограмму в качестве аргумента; вместо этого она принимает исходный код программы. Более того, определение g является самореферентным . Строгое доказательство решает эти проблемы. Общая цель состоит в том, чтобы показать, что не существует полной вычислимой функции , которая решает, останавливается ли произвольная программа i на произвольном входе x ; то есть следующая функция h (для «halts») не является вычислимой: ^[31]

${\displaystyle h(i,x)={\begin{cases}1&{\text{if }}{\text{ program }}i{\text{ halts on input }}x,\\0&{\text{otherwise.}}\end{cases}}}$

Здесь программа i относится к i- й программе в перечислении всех программ фиксированной Тьюринг-полной модели вычислений.

Возможные значения для общей вычислимой функции f, расположенной в двумерном массиве. Оранжевые ячейки — диагональ. Значения f ( i , i ) и g ( i ) показаны внизу; U указывает, что функция g не определена для конкретного входного значения.

Доказательство проводится путем прямого установления того, что никакая полностью вычислимая функция с двумя аргументами не может быть требуемой функцией h . Как и в наброске концепции, если задана любая полностью вычислимая бинарная функция f , следующая частичная функция g также вычислима некоторой программой e :

${\displaystyle g(i)={\begin{cases}0&{\text{if }}f(i,i)=0,\\{\text{undefined}}&{\text{otherwise.}}\end{cases}}}$

Проверка того, что g вычислима, основана на следующих конструкциях (или их эквивалентах):

• вычислимые подпрограммы (программа, вычисляющая f, является подпрограммой в программе e ),
• дублирование значений (программа e вычисляет входные данные i , i для f из входных данных i для g ),
• условное ветвление (программа e выбирает между двумя результатами в зависимости от значения, которое она вычисляет для f ( i , i )),
• не приводит к определенному результату (например, при бесконечном выполнении цикла),
• возвращает значение 0.

Следующий псевдокод для e иллюстрирует простой способ вычисления g :

процедура e ( i ) : если f ( i , i ) == 0 , то вернуть 0 , иначе цикл бесконечен            

Поскольку g частично вычислима, должна быть программа e , которая вычисляет g , исходя из предположения, что модель вычисления является полной по Тьюрингу. Эта программа является одной из всех программ, в которых определена функция остановки h . Следующий шаг доказательства показывает, что h ( e , e ) не будет иметь то же значение, что и f ( e , e ).

Из определения g следует , что должен иметь место только один из следующих двух случаев:

• f ( e , e ) = 0 и поэтому g ( e ) = 0. В этом случае программа e останавливается на входе e , поэтому h ( e , e ) = 1.
• f ( e , e ) ≠ 0 и поэтому g ( e ) не определено. В этом случае программа e не останавливается на входе e , поэтому h ( e , e ) = 0.

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

Это доказательство аналогично диагональному аргументу Кантора . Можно визуализировать двумерный массив с одним столбцом и одной строкой для каждого натурального числа, как указано в таблице выше. Значение f ( i , j ) помещается в столбец i , строку j . Поскольку предполагается, что f является полностью вычислимой функцией, любой элемент массива может быть вычислен с помощью f . Построение функции g можно визуализировать с помощью главной диагонали этого массива. Если массив имеет 0 в позиции ( i , i ), то g ( i ) равно 0. В противном случае g ( i ) не определено. Противоречие возникает из того факта, что есть некоторый столбец e массива, соответствующий самому g . Теперь предположим, что f была функцией остановки h , если g ( e ) определена ( в этом случае g ( e ) = 0), g ( e ) останавливается, поэтому f ( e,e ) = 1. Но g ( e ) = 0 только тогда, когда f ( e,e ) = 0, что противоречит f ( e,e ) = 1. Аналогично, если g ( e ) не определена, то функция остановки f ( e,e ) = 0, что приводит к g ( e ) = 0 при построении g . Это противоречит предположению, что g ( e ) не определена. В обоих случаях возникает противоречие. Следовательно, любая произвольная вычислимая функция f не может быть функцией остановки h .

Теория вычислимости

Типичный метод доказательства неразрешимости проблемы — свести проблему остановки к . Например, не может быть общего алгоритма, который решает, является ли данное утверждение о натуральных числах истинным или ложным. Причина этого в том, что утверждение о том, что определенная программа остановится при определенном вводе, можно преобразовать в эквивалентное утверждение о натуральных числах. Если алгоритм может найти истинностное значение каждого утверждения о натуральных числах, он, безусловно, может найти истинностное значение этого; но это определит, остановится ли исходная программа. ${\displaystyle P}$ ${\displaystyle P}$

Теорема Райса обобщает теорему о том, что проблема остановки неразрешима. Она утверждает, что для любого нетривиального свойства не существует общей процедуры принятия решения, которая для всех программ определяет, имеет ли частичная функция, реализованная входной программой, это свойство. (Частичная функция — это функция, которая не всегда может выдавать результат, и поэтому используется для моделирования программ, которые могут либо выдавать результаты, либо не останавливаться.) Например, свойство «остановка для входного значения 0» неразрешимо. Здесь «нетривиальный» означает, что множество частичных функций, удовлетворяющих свойству, не является ни пустым множеством, ни множеством всех частичных функций. Например, «остановка или неудача остановки при входном значении 0» явно верно для всех частичных функций, поэтому это тривиальное свойство и может быть решено алгоритмом, который просто сообщает «истина». Кроме того, эта теорема справедлива только для свойств частичной функции, реализованной программой; теорема Райса не применима к свойствам самой программы. Например, «остановка при вводе 0 в течение 100 шагов» не является свойством частичной функции, реализуемой программой, — это свойство программы, реализующей частичную функцию, и оно вполне разрешимо.

Грегори Хайтин определил вероятность остановки , представленную символом Ω , тип действительного числа, который неформально считается представляющим вероятность того, что случайно созданная программа остановится. Эти числа имеют ту же степень Тьюринга , что и проблема остановки. Это нормальное и трансцендентное число , которое можно определить , но нельзя полностью вычислить . Это означает, что можно доказать, что не существует алгоритма , который производит цифры Ω, хотя его первые несколько цифр можно вычислить в простых случаях.

Поскольку отрицательный ответ на проблему остановки показывает, что существуют проблемы, которые не могут быть решены машиной Тьюринга, тезис Чёрча–Тьюринга ограничивает то, что может быть достигнуто любой машиной, реализующей эффективные методы . Однако не все машины, мыслимые человеческим воображением, подчиняются тезису Чёрча–Тьюринга (например, машины-оракулы ). Открытым является вопрос о том, могут ли существовать реальные детерминированные физические процессы , которые в долгосрочной перспективе избегают моделирования машиной Тьюринга, и, в частности, может ли любой такой гипотетический процесс быть с пользой использован в форме вычислительной машины (гиперкомпьютера ) , которая могла бы решить проблему остановки для машины Тьюринга среди прочего. Также открытым является вопрос о том, участвуют ли какие-либо такие неизвестные физические процессы в работе человеческого мозга , и могут ли люди решить проблему остановки. ^[32]

Приближения

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

Некоторые результаты были получены по теоретической производительности эвристик проблемы остановки, в частности, доля программ заданного размера, которые могут быть правильно классифицированы рекурсивным алгоритмом. Эти результаты не дают точных чисел, поскольку доли невычислимы и также сильно зависят от выбора кодировки программы, используемой для определения «размера». Например, рассмотрим классификацию программ по их числу состояний и использование определенной модели вычисления «полубесконечной ленты Тьюринга», которая допускает ошибки (без остановки), если программа запускается с левой стороны ленты. Затем , по программам, выбранным равномерно по числу состояний. Но этот результат в некотором смысле «тривиален», поскольку эти разрешимые программы — это просто те, которые спадают с ленты, а эвристика заключается просто в прогнозировании отсутствия остановки из-за ошибки. Таким образом, казалось бы, несущественная деталь, а именно обработка программ с ошибками, может оказаться решающим фактором при определении доли программ. ^[33] ${\displaystyle \lim _{n\to \infty }P(x\,{\text{halts is decidable}}\mid x\,{\text{has}}\,n\,{\text{states}})=1}$ ${\displaystyle x}$

Чтобы избежать этих проблем, было разработано несколько ограниченных понятий «размера» программы. Плотная гёделевская нумерация назначает номера программам таким образом, что каждая вычислимая функция встречается в положительной дроби в каждой последовательности индексов от 1 до n, т. е. гёделизация φ плотна тогда и только тогда, когда для всех , существует такое, что . Например, нумерация, которая назначает индексы нетривиальным программам и всем другим индексам состояние ошибки не является плотной, но существует плотная гёделевская нумерация синтаксически правильных программ Brainfuck . ^[34] Плотная гёделевская нумерация называется оптимальной, если для любой другой гёделевской нумерации существует 1-1 полная рекурсивная функция и константа такие, что для всех , и . Это условие гарантирует, что все программы имеют индексы, не намного превышающие их индексы в любой другой гёделевской нумерации. Оптимальные гёделевские нумерации строятся путем нумерации входов универсальной машины Тьюринга . ^[35] Третье понятие размера использует универсальные машины, работающие с двоичными строками, и измеряет длину строки, необходимую для описания входной программы. Универсальная машина U — это машина, для которой для любой другой машины V существует общая вычислимая функция h такая, что . Оптимальная машина — это универсальная машина, которая достигает границы инвариантности сложности Колмогорова , т. е. для каждой машины V существует c такое, что для всех выходов x , если V -программа длины n выводит x , то существует U -программа не более длины, выдающая x . ^[36] ${\displaystyle i}$ ${\displaystyle c>0}$ ${\displaystyle \liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c}$ ${\displaystyle 2^{n}}$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle i}$ ${\displaystyle \alpha _{i}=\phi _{f(i)}}$ ${\displaystyle f(i)\leq ci}$ ${\displaystyle V(x)=U(h(x))}$ ${\displaystyle n+c}$

Мы рассматриваем частично вычислимые функции (алгоритмы) . Для каждого мы рассматриваем долю ошибок среди всех программ размера метрики не более , подсчитывая каждую программу , для которой не удается завершить работу, выдает ответ «не знаю» или выдает неправильный ответ, т.е. останавливается и выводит , или не останавливается и выводит . Поведение может быть описано следующим образом для плотных гёделизаций и оптимальных машин: ^{[34] [36]} ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle \epsilon _{n}(A)}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle A(x)}$DOES_NOT_HALT ${\displaystyle x}$ ${\displaystyle A(x)}$HALTS

• Для каждого алгоритма , . Другими словами, любой алгоритм имеет положительную минимальную частоту ошибок, даже если размер проблемы становится чрезвычайно большим. ${\displaystyle A}$ ${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$
• Существует такой, что для каждого алгоритма , . Другими словами, существует положительный коэффициент ошибок, при котором любой алгоритм будет работать хуже этого коэффициента ошибок сколь угодно часто, даже если размер проблемы будет расти бесконечно. ${\displaystyle \epsilon >0}$ ${\displaystyle A}$ ${\displaystyle \limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon }$
• ${\displaystyle \inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0}$. На словах, есть последовательность алгоритмов, такая, что частота ошибок становится произвольно близкой к нулю для определенной последовательности увеличивающихся размеров. Однако этот результат допускает последовательности алгоритмов, которые выдают неправильные ответы.
• Если мы рассмотрим только «честные» алгоритмы, которые могут быть неопределенными, но никогда не выдают неправильных ответов, то в зависимости от метрики может быть или не быть 0. В частности, это 0 для лево-тотальных универсальных машин, но для эффективно оптимальных машин это больше 0. ^[36] ${\displaystyle \inf _{A\,{\textrm {honest}}}\liminf _{n\to \infty }\epsilon _{n}(A)}$

Сложная природа этих границ обусловлена ​​колебательным поведением . Существуют редко встречающиеся новые разновидности программ, которые поступают в произвольно больших «блоках», и постоянно растущая доля повторений. Если блоки новых разновидностей полностью включены, частота ошибок составляет по крайней мере , но между блоками доля правильно классифицированных повторений может быть произвольно высокой. В частности, эвристика «подсчета», которая просто запоминает первые N входов и распознает их эквиваленты, позволяет достигать произвольно низкой частоты ошибок бесконечно часто. ^[34] ${\displaystyle \epsilon _{n}(A)}$ ${\displaystyle \epsilon }$

Теоремы Гёделя о неполноте

Концепции, поднимаемые теоремами Гёделя о неполноте , очень похожи на те, которые поднимаются проблемой остановки, и доказательства довольно похожи. Фактически, более слабая форма первой теоремы о неполноте является простым следствием неразрешимости проблемы остановки. Эта более слабая форма отличается от стандартной формулировки теоремы о неполноте, утверждая, что аксиоматизация натуральных чисел, которая является одновременно полной и обоснованной , невозможна. «Обоснованная» часть — это ослабление: это означает, что мы требуем, чтобы рассматриваемая аксиоматическая система доказывала только истинные утверждения о натуральных числах. Поскольку обоснованность подразумевает согласованность , эту более слабую форму можно рассматривать как следствие сильной формы. Важно отметить, что формулировка стандартной формы первой теоремы Гёделя о неполноте совершенно не касается истинностного значения утверждения, а касается только вопроса о том, можно ли найти его с помощью математического доказательства .

Более слабая форма теоремы может быть доказана из неразрешимости проблемы остановки следующим образом. ^[37] Предположим, что у нас есть обоснованная (и, следовательно, непротиворечивая) и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах . Тогда мы можем построить алгоритм, который перечисляет все эти утверждения. Это означает, что существует алгоритм N ( n ), который, учитывая натуральное число n , вычисляет истинное логическое утверждение первого порядка о натуральных числах, и что для всех истинных утверждений существует по крайней мере одно n такое, что N ( n ) дает это утверждение. Теперь предположим, что мы хотим решить, останавливается ли алгоритм с представлением a на входе i . Мы знаем, что это утверждение можно выразить с помощью логического утверждения первого порядка, скажем, H ( a , i ). Поскольку аксиоматизация является полной, следует, что либо существует n , такое что N ( n ) = H ( a , i ), либо существует n ′, такое что N ( n ′ ) = ¬ H ( a , i ). Таким образом, если мы будем итерировать по всем n, пока не найдем H ( a , i ) или его отрицание, мы всегда остановимся, и, более того, ответ, который он нам даст, будет истинным (по обоснованности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма не может быть, следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.

Обобщение

Множество вариантов проблемы остановки можно найти в учебниках по вычислимости. ^[38] Обычно эти проблемы являются RE-полными и описывают наборы сложности в арифметической иерархии , такие же, как стандартная проблема остановки. Таким образом, варианты неразрешимы, и стандартная проблема остановки сводится к каждому варианту и наоборот. Однако некоторые варианты имеют более высокую степень неразрешимости и не могут быть сведены к стандартной проблеме остановки. Следующие два примера являются общими. ${\displaystyle \Sigma _{1}^{0}}$

Остановка на всех входах

Универсальная проблема остановки , также известная (в теории рекурсии ) как тотальность , — это проблема определения того, остановится ли данная компьютерная программа для каждого ввода (название тотальность происходит от эквивалентного вопроса о том, является ли вычисляемая функция тотальной ). Эта проблема не только неразрешима, как проблема остановки, но и крайне неразрешима. С точки зрения арифметической иерархии она является -полной. ^[39] ${\displaystyle \Pi _{2}^{0}}$

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

Распознавание частичных решений

Существует множество программ, которые для некоторых входных данных возвращают правильный ответ на проблему остановки, в то время как для других входных данных они вообще не возвращают ответа. Однако проблема «данная программа p , является ли она частично останавливающимся решателем» (в описанном смысле) по крайней мере так же сложна, как и проблема остановки. Чтобы увидеть это, предположим, что существует алгоритм PHSR («частично останавливающийся решатель-распознаватель») для этого. Тогда его можно использовать для решения проблемы остановки следующим образом: чтобы проверить, останавливается ли входная программа x на y , постройте программу p , которая на входных данных ( x , y ) сообщает true и расходится на всех других входных данных. Затем проверьте p с помощью PHSR.

Приведенный выше аргумент сводит проблему остановки к распознаванию PHS, и таким же образом можно свести и более сложные проблемы, такие как остановка на всех входах , что подразумевает, что распознавание PHS не только неразрешимо, но и находится выше в арифметической иерархии , в частности, является -полным. ${\displaystyle \Pi _{2}^{0}}$

Вычисление с потерями

Машина Тьюринга с потерями — это машина Тьюринга, в которой часть ленты может недетерминированно исчезнуть. Проблема остановки разрешима для машины Тьюринга с потерями, но не примитивно рекурсивной . ^[40]

Машины Oracle

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

Смотрите также

• Занятой бобер
• Теорема Гёделя о неполноте
• Противоречие Брауэра–Гильберта
• сложность Колмогорова
• Проблема P против NP
• Анализ прекращения
• Наихудшее время выполнения

Примечания

1. Макконнелл, Стив (2004). Code Complete (2-е изд.). Pearson Education. стр. 374. ISBN 9780735636972.
2. Хуан, Хан-Вэй (2009). HCS12 / 9S12: Введение в программное и аппаратное взаимодействие. стр. 197. ... если программа застревает в определенном цикле, ... выясните, в чем проблема.
3. Саймон, Дэвид Э. (1999). Учебник по встроенному программному обеспечению. стр. 253. Поэтому для систем жесткого реального времени важно писать подпрограммы, которые всегда выполняются за одинаковое время или имеют четко идентифицируемый наихудший случай.
4. Минский 1967, стр. 24. курсив в оригинале
5. Минский 1967, стр. 25.
6. Hodges 1983, стр. 83; комментарий Дэвиса в Davis 1965, стр. 108
7. Абсолютно неразрешимые проблемы и относительно неразрешимые предложения – отчет об одном предвосхищении , перепечатано в Davis 1965, стр. 340–433
8. Минский 1967.
9. Рид 1996, стр. 188–189.
10. Ходжес 1983, стр. 91.
11. Ходжес 1983, стр. 91; Пенроуз 1989, стр. 34.
12. Рид 1996, стр. 198.
13. Рид 1996, стр. 199.
14. перепечатано в Davis 1965, стр. 5 и далее
15. Церковь 1936.
16. Заметка о проблеме Entscheidungsproblem , перепечатано в Davis 1965, стр. 110
17. Дэвис 1965, стр. 289 и далее.
18. перепечатано в Davis 1965, стр. 115
19. Лукас 2021.
20. Клини 1952.
21. Россер, «Неформальное изложение доказательств теоремы Гёделя и теоремы Чёрча», перепечатано в Davis 1965, стр. 223
22. Kleene 1952, стр. 382.
23. письмо Дэвиса Коупленду, 12 декабря 2001 г., сноска 61 в Copeland 2004, стр. 40
24. Copeland 2004, стр. 40.
25. Текстовый поиск в собрании сочинений Тьюринга: Good (1992), Gandy & Yates (2001), Ince (1992), Saunders (1992). Аналогично, у Ходжеса (1983) нет слова "halting" или слов "halting problem" в его индексе.
26. Дэвис 1958, стр. vii–viii.
27. Дэвис 1958, стр. 70–71.
28. Мур и Мертенс 2011, стр. 236–237.
29. Стрейчи, К. (1 января 1965 г.). «Невозможная программа». The Computer Journal . 7 (4): 313. doi : 10.1093/comjnl/7.4.313 .
30. Daylight, Edgar G. (16 апреля 2021 г.). «Проблема остановки и языковой подход к безопасности: похвала и критика от технического историка» (PDF) . Вычислимость . 10 (2): 141–158. doi :10.3233/COM-180217. S2CID  233329507 . Получено 26 августа 2021 г. .
31. Пенроуз 1989, стр. 57–63.
32. Коупленд 2004, стр. 15.
33. Хамкинс, Джоэл Дэвид; Мясников, Алексей (1 октября 2006 г.). «Проблема остановки разрешима на множестве асимптотической вероятности один» (PDF) . Notre Dame Journal of Formal Logic . 47 (4). doi :10.1305/ndjfl/1168352664. S2CID  15005164 . Получено 5 ноября 2022 г. .
34. Köhler, Sven; Schindelhauer, Christian; Ziegler, Martin (2005). "On Approximating Real-World Halting Problems". Основы теории вычислений . Конспект лекций по информатике. Том 3623. С. 454–466. doi :10.1007/11537311_40. ISBN 978-3-540-28193-1.
35. Линч, Нэнси (октябрь 1974 г.). «Приближения к проблеме остановки» (PDF) . Журнал компьютерных и системных наук . 9 (2): 143–150. doi :10.1016/S0022-0000(74)80003-6.
36. Bienvenu, Laurent; Desfontaines, Damien; Shen, Alexander (5 апреля 2016 г.). "Общие алгоритмы для проблемы остановки и оптимальные машины снова в моде". Logical Methods in Computer Science . 12 (2): 1. arXiv : 1505.00731 . doi :10.2168/LMCS-12(2:1)2016. S2CID  14763862.
37. Ааронсон, Скотт (21 июля 2011 г.). «Теорема Россера через машины Тьюринга». Shtetl-Optimized . Получено 2 ноября 2022 г.
38. например, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft & Ullman 1979, Börger 1989
39. Бёргер 1989, стр. 121.
40. Абдулла и Йонссон 1996, с. 92.

Ссылки

• Чёрч, Алонзо (1936). «Неразрешимая проблема элементарной теории чисел». American Journal of Mathematics . 58 (2): 345–363. doi :10.2307/2371045. JSTOR  2371045.
• Коупленд, Б. Джек, ред. (2004). Суть Тьюринга: основополагающие труды по вычислительной технике, логике, философии, искусственному интеллекту и искусственной жизни, а также секреты Энигмы . Оксфорд: Clarendon Press. ISBN 0-19-825079-7.
• Дэвис, Мартин (1965). Неразрешимое, основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Raven Press.. Статья Тьюринга — № 3 в этом томе. Среди статей — статьи Гёделя, Чёрча, Россера, Клини и Поста.
• Дэвис, Мартин (1958). Вычислимость и неразрешимость . Нью-Йорк: McGraw-Hill..
• Роджерс, Хартли (младший) (1957). Теория рекурсивных функций и эффективная вычислимость. Массачусетский технологический институт.
• Клини, Стивен Коул (1952). Введение в метаматематику . Северная Голландия. ISBN 0923891579.. Глава XIII («Вычислимые функции») включает обсуждение неразрешимости проблемы остановки для машин Тьюринга. Отступая от терминологии Тьюринга о машинах без кругов, не останавливающихся, Клини вместо этого ссылается на машины, которые «останавливаются», т. е. останавливаются.
• Лукас, Сальвадор (июнь 2021 г.). «Истоки проблемы остановки». Журнал логических и алгебраических методов в программировании . 121 : 100687. doi : 10.1016/j.jlamp.2021.100687. hdl : 10251/189460 . S2CID  235396831.
• Минский, Марвин (1967). Вычисление: конечные и бесконечные машины . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. ISBN 0131655639.. См. главу 8, раздел 8.2 «Неразрешимость проблемы остановки».
• Мур, Кристофер ; Мертенс, Стефан (2011). Природа вычислений. Oxford University Press. doi :10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2.
• Рид, Констанс (1996). Гильберт . Нью-Йорк: Copernicus. ISBN 0387946748.. Впервые опубликованная в 1970 году, захватывающая история немецкой математики и физики с 1880-х по 1930-е годы. На ее страницах появляются сотни имен, знакомых математикам, физикам и инженерам. Возможно, испорченная отсутствием явных ссылок и несколькими сносками: Рид утверждает, что ее источниками были многочисленные интервью с теми, кто лично знал Гильберта, а также письма и статьи Гильберта.
• Sipser, Michael (2006). "Раздел 4.2: Проблема остановки" . Введение в теорию вычислений (второе изд.). PWS Publishing. стр. 173–182. ISBN 0-534-94728-X.
• Тьюринг, AM (1937). «О вычислимых числах с приложением к Entscheidungsproblem». Труды Лондонского математического общества . s2-42 (1). Wiley: 230–265. doi :10.1112/plms/s2-42.1.230. ISSN  0024-6115. S2CID  73712.^{[ постоянная мертвая ссылка ]} , Turing, AM (1938). «О вычислимых числах с приложением к Entscheidungsproblem. Исправление». Труды Лондонского математического общества . s2-43 (1). Wiley: 544–546. doi :10.1112/plms/s2-43.6.544. ISSN  0024-6115.^{[ постоянная неработающая ссылка ]} Это эпохальная статья, в которой Тьюринг определяет машины Тьюринга , формулирует проблему остановки и показывает, что она (как и проблема Entscheidungsproblem ) неразрешима.
• Пенроуз, Роджер (1989). Новый разум императора: о компьютерах, разуме и законах физики (исправленное переиздание 1990 г.). Оксфорд: Oxford University Press. ISBN 0192861980.. См. Главу 2, «Алгоритмы и машины Тьюринга». Чрезмерно сложное изложение (см. статью Дэвиса для лучшей модели), но полное изложение машин Тьюринга и проблемы остановки, а также лямбда-исчисления Чёрча.
• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли. ISBN 81-7808-347-7.. См. главу 7 «Машины Тьюринга». Книга, посвященная машинной интерпретации «языков», NP-полноте и т. д.
• Ходжес, Эндрю (1983). Алан Тьюринг: загадка . Нью-Йорк: Саймон и Шустер. ISBN 0-671-49207-1.. См. главу «Дух истины» для истории, ведущей к его доказательству, и его обсуждения.
• Бёргер, Эгон (1989). Вычислимость, сложность, логика . Амстердам: Северная Голландия. ISBN 008088704X.
• Абдулла, Парош Азиз; Йонссон, Бенгт (1996). «Проверка программ с ненадежными каналами». Информация и вычисления . 127 (2): 91–101. doi : 10.1006/inco.1996.0053 .
• Собрание сочинений А.М. Тьюринга
  • Good, Irving John, ed. (1992). Чистая математика. Северная Голландия. ISBN 978-0-444-88059-8.
  • Ганди, РО; Йейтс, СЕМ, ред. (5 декабря 2001 г.). Математическая логика. Elsevier. ISBN 978-0-08-053592-0.
  • Инс, округ Колумбия, ред. (1992). Механический интеллект. Северная Голландия. ISBN 978-0-444-88058-1.
  • Saunders, PT, ред. (26 ноября 1992 г.). Морфогенез. Elsevier. ISBN 978-0-08-093405-1.

Дальнейшее чтение

• c2:Проблема остановки
• Альфред Норт Уайтхед и Бертран Рассел , Principia Mathematica к *56, Cambridge at the University Press, 1962. В отношении проблемы парадоксов авторы обсуждают проблему множества, не являющегося объектом ни в одной из его «определяющих функций», в частности «Введение, Гл. 1, стр. 24 «...трудности, возникающие в формальной логике», и Гл. 2.I. «Принцип порочного круга», стр. 37 и далее, и Гл. 2.VIII. «Противоречия», стр. 60 и далее.
• Мартин Дэвис , «Что такое вычисление», в Mathematics Today , Линн Артур Стин, Vintage Books (Random House), 1980. Замечательная небольшая статья, возможно, лучшая из когда-либо написанных о машинах Тьюринга для неспециалистов. Дэвис сводит машину Тьюринга к гораздо более простой модели, основанной на модели вычисления Поста. Обсуждает доказательство Хайтина . Включает небольшие биографии Эмиля Поста , Джулии Робинсон .
• Эдвард Бельтрами, Что такое случайность? Случайность и порядок в математике и жизни , Copernicus: Springer-Verlag, Нью-Йорк, 1999. Хорошее, приятное чтение для неспециалистов с математическими наклонностями, более сложные вещи помещены в конце. Содержит модель машины Тьюринга. Обсуждает вклад Хайтина .
• Эрнест Нагель и Джеймс Р. Ньюман , Доказательство Гёделя , New York University Press, 1958. Замечательное сочинение на очень сложную тему. Для неспециалистов, склонных к математике. Обсуждает доказательство Генцена на страницах 96–97 и в сносках. В приложениях кратко обсуждаются аксиомы Пеано , мягко знакомят читателей с формальной логикой.
• Daras, Nicholas J.; Rassias, Themistocles M. (2018). Современная дискретная математика и анализ: с приложениями в криптографии, информационных системах и моделировании . Cham, Швейцария. ISBN 978-3319743240.{{cite book}}: CS1 maint: location missing publisher (link). Глава 3 Раздел 1 содержит качественное описание проблемы остановки, доказательство от противного и полезное графическое представление проблемы остановки.
• Taylor Booth , Sequential Machines and Automata Theory , Wiley, New York, 1967. См. главу 9, Turing Machines. Сложная книга, предназначенная для инженеров-электриков и технических специалистов. Обсуждает рекурсию, частичную рекурсию со ссылкой на машины Тьюринга, проблему остановки. Содержит модель машины Тьюринга . Ссылки в конце главы 9 охватывают большинство старых книг (т. е. с 1952 по 1967 год, включая авторов Martin Davis, FC Hennie, H. Hermes, SC Kleene, M. Minsky, T. Rado) и различные технические статьи. См. примечание в разделе Busy-Beaver Programs.
• Программы Busy Beaver описаны в Scientific American за август 1984 г., а также за март 1985 г., стр. 23. Ссылка в Booth приписывает их Rado, T. (1962), On non-computable functions, Bell Systems Tech. J. 41. Booth также определяет задачу Busy Beaver Rado в задачах 3, 4, 5, 6 главы 9, стр. 396.
• Дэвид Болтер, Человек Тьюринга: Западная культура в компьютерную эпоху , Издательство Университета Северной Каролины, Чапел-Хилл, 1984. Для широкого круга читателей. Может быть устаревшей. Содержит еще одну (очень простую) модель машины Тьюринга.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, On approximating real-world halting problems , стр. 454-466 (2005) ISBN 3540281932 Springer Lecture Notes in Computer Science, том 3623: Неразрешимость проблемы остановки означает, что не на все случаи можно ответить правильно; но, может быть, на «некоторые», «многие» или «большинство» можно? С одной стороны, постоянный ответ «да» будет верным бесконечно часто и неверным также бесконечно часто. Чтобы сделать вопрос разумным, рассмотрим плотность случаев , которые можно решить. Оказывается, это существенно зависит от рассматриваемой системы программирования . 
• Логические ограничения машинной этики с последствиями для смертоносного автономного оружия — статья, обсуждаемая в: Означает ли проблема остановки отсутствие моральных роботов?

Внешние ссылки

• Вылавливание петлевого шпиона - поэтическое доказательство неразрешимости проблемы остановки
• анимационный фильм - анимация, объясняющая доказательство неразрешимости проблемы остановки
• Двухминутное доказательство второй по важности теоремы второго тысячелетия — доказательство всего в 13 строках
• haltingproblem.org — популярные видео и документы, объясняющие проблему остановки.