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

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

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

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

Джек Коупленд (2004) приписывает введение термина « проблема остановки» работе Мартина Дэвиса в 1950-х годах. ^[1]

Фон [ править ]

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

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

пока (правда) продолжить

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

печать "Привет, мир!"

действительно останавливается.

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

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

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

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

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

Распространенные ошибки [ править ]

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

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

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

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

Мински, однако, отмечает, что компьютер с миллионом мелких деталей, каждая из которых имеет два состояния, будет иметь как минимум 2 ^{миллиона} возможных состояний:

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

Мински утверждает, что, хотя машина может быть конечной, конечные автоматы «имеют ряд теоретических ограничений»:

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

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

История [ править ]

Этот раздел имеет формат списка , но может читаться лучше как проза . Вы можете помочь, преобразовав этот раздел , если это необходимо. Доступна помощь по редактированию . ( Февраль 2020 г. )

Проблема остановки исторически важна, потому что это была одна из первых проблем, неразрешимость которых была доказана . (Доказательство Тьюринга было опубликовано в мае 1936 г., тогда как доказательство неразрешимости проблемы лямбда-исчисления Алонзо Чёрчем было опубликовано уже в апреле 1936 г. [Church, 1936].) Впоследствии были описаны многие другие неразрешимые проблемы.

Хронология [ править ]

• 1900: Давид Гильберт ставит свои «23 вопроса» (теперь известные как проблемы Гильберта ) на Втором Международном конгрессе математиков в Париже. «Из них вторым было доказательство непротиворечивости« аксиом Пеано », от которых, как он показал, зависела строгость математики». (Ходжес, стр. 83, комментарий Дэвиса у Дэвиса, 1965, стр. 108)
• 1920–1921: Эмиль Пост исследует проблему остановки для систем тегов , рассматривая ее как кандидата на неразрешимость. ( Абсолютно неразрешимые проблемы и относительно неразрешимые утверждения - описание предвкушения , Дэвис, 1965, стр. 340–433.) Его неразрешимость была установлена ​​намного позже Марвином Мински (1967).
• 1928: Гильберт переформулирует свою «Вторую проблему» на Болонском международном конгрессе. (Рейд, стр. 188–189) Ходжес утверждает, что он задал три вопроса: например, №1: была ли математика завершена ? №2: Была ли математика последовательной ? №3: Была ли математика разрешимой ? (Ходжес стр. 91). Третий вопрос известен как Entscheidungsproblem (проблема решения). (Ходжес стр. 91, Пенроуз стр. 34)
• 1930: Курт Гёдель объявляет доказательство как ответ на первые два вопроса Гильберта 1928 года [ср. Reid p. 198]. «Сначала он [Гильберт] был только рассержен и разочарован, но затем он начал пытаться конструктивно разобраться с проблемой ... Сам Гёдель почувствовал - и выразил мысль в своей статье, - что его работа не противоречит формалистической точке зрения Гильберта. вид »(Рид стр. 199)
• 1931: Гёдель издает «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (перепечатано в Davis, 1965, стр. 5ff).
• 19 апреля 1935 г .: Алонзо Черч публикует «Неразрешимую проблему элементарной теории чисел», в которой он определяет, что означает эффективное вычисление функции . Такая функция будет иметь алгоритм, и «... факт завершения работы алгоритма становится фактически известным ...» (Дэвис, 1965, стр. 100)
• 1936: Черч публикует первое доказательство неразрешимости проблемы Entscheidungs . ( Заметка о проблеме Entscheidungsproblem , перепечатано в Davis, 1965, стр. 110.)
• 7 октября 1936 г. Получена статья Эмиля Поста "Конечные комбинаторные процессы. Формулировка I". Пост добавляет к своему «процессу» инструкцию «(C) Stop». Он назвал такой процесс «типом 1 ... если процесс, который он определяет, завершается для каждой конкретной проблемы». (Дэвис, 1965, стр. 289 и далее).
• 1937: статья Алана Тьюринга « О вычислимых числах в приложении к проблеме Entscheidungspro» выходит в печать в январе 1937 г. (перепечатана в Davis, 1965, стр. 115). Доказательство Тьюринга отходит от вычисления с помощью рекурсивных функций и вводит понятие вычисления с помощью машины. Стивен Клини (1952) называет это одним из «первых примеров проблем, связанных с решением, которые оказались неразрешимыми».
• 1939: Дж. Баркли Россер замечает существенную эквивалентность «эффективного метода», определенного Геделем, Черчем и Тьюрингом (Россер в Дэвисе, 1965, стр. 273, «Неформальное изложение доказательств теоремы Гёделя и теоремы Черча»).
• 1943: В статье Стивен Клини заявляет, что «при создании полной алгоритмической теории мы делаем то, что мы делаем, это описываем процедуру ... которая обязательно завершается, и таким образом, чтобы по ее результату мы могли прочитать однозначный ответ:« Да ». 'или' Нет 'на вопрос' Верно ли значение предиката? '".
• 1952: Клини (1952) Глава XIII («Вычислимые функции») включает обсуждение неразрешимости проблемы остановки для машин Тьюринга и переформулирует ее в терминах машин, которые «в конечном итоге останавливаются», то есть останавливаются: «... нет никакого алгоритм для принятия решения о том, останавливается ли в конечном итоге какая-либо конкретная машина при запуске из любой данной ситуации ". (Клини (1952) стр. 382)
• 1952: « Мартин Дэвис считает вероятным, что он впервые использовал термин« проблема остановки »в серии лекций, которые он прочитал в Лаборатории систем управления в Университете Иллинойса в 1952 году (письмо Дэвиса Коупленду, 12 декабря 2001 г.). " (Сноска 61 в Copeland (2004), стр. 40 и далее)

Формализация [ править ]

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

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

Представление в виде набора [ править ]

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

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

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

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

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

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

Концепция доказательства [ править ]

Доказательство неразрешимости проблемы остановки является доказательством от противного . Чтобы проиллюстрировать концепцию доказательства, предположим, что существует общая вычислимая функция halts (f), которая возвращает true, если подпрограмма f останавливается (при запуске без входов), и возвращает false в противном случае. Теперь рассмотрим следующую подпрограмму:

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

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

Метод , используемый в доказательстве называется диагонализацией - г делает противоположное тому , что привалы говорит г должен делать. Разница между этим наброском и фактическим доказательством состоит в том, что в фактическом доказательстве вычислимая функция останова не принимает непосредственно подпрограмму в качестве аргумента; вместо этого он берет исходный код программы. Фактическое доказательство требует дополнительной работы для решения этой проблемы. Более того, фактическое доказательство избегает прямого использования рекурсии, показанной в определении g .

Эскиз доказательства [ править ]

Приведенная выше концепция показывает общий метод доказательства; в этом разделе будут представлены дополнительные сведения. Общая цель - показать, что не существует общей вычислимой функции, которая решает, останавливается ли произвольная программа i на произвольном входе x ; то есть следующая функция h не вычислима (Penrose 1990, p. 57–63):

${\ displaystyle h (i, x) = {\ begin {cases} 1 & {\ text {if}} {\ text {program}} i {\ text {останавливается при вводе}} x, \\ 0 & {\ text { в противном случае.}} \ end {case}}}$

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

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

${\ displaystyle g (i) = {\ begin {cases} 0 & {\ text {if}} f (i, i) = 0, \\ {\ text {undefined}} & {\ text {в противном случае.}} \ конец {case}}}$

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

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

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

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

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

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

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

В любом случае 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 .

Теория вычислимости [ править ]

Типичный метод доказательства неразрешимости проблемы - это метод редукции ^{[ требуется пояснение ]} . Для этого достаточно показать, что, если решение новой проблемы было найдено, его можно было бы использовать для решения неразрешимой проблемы путем преобразования экземпляров неразрешимой проблемы в экземпляры новой проблемы. Поскольку мы уже знаем, что никакой метод не может решить старую проблему, никакой метод не может решить и новую проблему. Часто новая проблема сводится к решению проблемы остановки. (Тот же метод используется для демонстрации того, что проблема является NP-полной , только в этом случае вместо демонстрации отсутствия решения она демонстрирует отсутствие полиномиального временирешение, предполагая, что P ≠ NP .)

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

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

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

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

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

Теоремы Гёделя о неполноте [ править ]

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

Более слабая форма теоремы может быть доказана из неразрешимости проблемы остановки следующим образом. Предположим, что у нас есть обоснованная (и, следовательно, непротиворечивая) и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах . Затем мы можем построить алгоритм, который перечислит все эти утверждения. Это означает, что существует алгоритм 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 ) или его отрицание, мы всегда будем останавливаться, и, более того, ответ, который он нам дает, будет истинным (по обоснованности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма быть не может, отсюда следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.

Обобщение [ править ]

Многие варианты проблемы остановки можно найти в учебниках по вычислимости (например, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft and Ullman 1979, Börger 1989). Обычно их неразрешимость следует путем редукции из стандартной задачи остановки. Однако некоторые из них имеют более высокую степень неразрешимости . Следующие два примера типичны.

Остановка на всех входах [ править ]

Универсальная проблема остановки , также известный (в теории рекурсии ) в совокупности , является проблема определения, будет ли данная компьютерная программа остановить для каждого входа (название совокупности происходит от эквивалентного вопроса о том , вычисленная функция общего числа ). Эта проблема не только неразрешима, как проблема остановки, но и в высшей степени неразрешима. С точки зрения арифметической иерархии она является полной (Börger 1989, p. 121).${\ displaystyle \ Pi _ {2} ^ {0}}$

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

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

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

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

Расчет с потерями [ править ]

Потери машин Тьюринга является машиной Тьюринга , в котором часть ленты может недетерминированно исчезнуть. Проблема остановки разрешима для машины Тьюринга с потерями, но не примитивно рекурсивна . ^{[6] : 92}

Машины Oracle [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Алан Тьюринг , О вычислимых числах, с приложением к проблеме Entscheidungsproedings , Proceedings of the London Mathematical Society , Series 2, Volume 42 (1937), pp 230–265, doi : 10.1112 / plms / s2-42.1.230 . - Алан Тьюринг, О вычислимых числах, в приложении к Entscheidungsproblem. Поправка , Труды Лондонского математического общества, Серия 2, том 43 (1938), стр 544-546, DOI : 10,1112 / ПНИЛИ / s2-43.6.544 . Бесплатная онлайн-версия обеих частей Это эпохальная статья, в которой Тьюринг определяет машины Тьюринга , формулирует проблему остановки и показывает, что она (а такжеEntscheidungsproblem ) неразрешима.
• Сипсер, Майкл (2006). «Раздел 4.2: Проблема остановки» . Введение в теорию вычислений (второе изд.). PWS Publishing. С.  173–182 . ISBN 0-534-94728-X.
• c2: Проблема с остановкой
• Церковь, Алонсо (1936). «Неразрешимая проблема элементарной теории чисел». Американский журнал математики . 58 (2): 345–363. DOI : 10.2307 / 2371045 . JSTOR  2371045 .
• Б. Джек Коупленд изд. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7 . 
• Дэвис, Мартин (1965). Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях . Нью-Йорк: Raven Press.. Статья Тьюринга занимает третье место в этом томе. Среди статей - Годель, Черч, Россер, Клини и Пост.
• Дэвис, Мартин (1958). Вычислимость и неразрешимость . Нью-Йорк: Макгроу-Хилл..
• Альфред Норт Уайтхед и Бертран Рассел , Principia Mathematica to * 56, Cambridge at University Press, 1962. Что касается проблемы парадоксов, то авторы обсуждают проблему того, что множество не может быть объектом ни в одной из своих «определяющих функций», в в частности, «Введение, гл. 1, стр. 24« ... трудности, возникающие в формальной логике », и гл. 2.I.« Принцип порочного круга », стр. 37ff, и гл. 2.VIII.« Противоречия ». "стр. 60ff.
• Мартин Дэвис , «Что такое вычисления», в « Математике сегодня» , Линн Артур Стин, Vintage Books (Random House), 1980. Замечательная небольшая статья, возможно, лучшая из когда-либо написанных о машинах Тьюринга для неспециалистов. Дэвис сводит машину Тьюринга к гораздо более простой модели, основанной на модели вычислений Поста. Обсуждает доказательство Чайтина . Включает небольшие биографии Эмиля Поста , Джулии Робинсон .
• Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967. См. Главу 8, раздел 8.2 «Неразрешимость проблемы остановки».
• Роджер Пенроуз , Новый разум императора: о компьютерах, умах и законах физики , Oxford University Press , Oxford England, 1990 (с исправлениями). Ср. Глава 2, «Алгоритмы и машины Тьюринга». Чрезмерно сложное представление (см. Статью Дэвиса для лучшей модели), но полное представление машин Тьюринга и проблемы остановки, а также лямбда-исчисления Черча.
• Джон Хопкрофт и Джеффри Уллман , Введение в теорию автоматов, языки и вычисления , Addison-Wesley, Reading Mass, 1979. См. Главу 7 «Машины Тьюринга». Книга, посвященная машинной интерпретации «языков», NP-полноте и т. Д.
• Эндрю Ходжес , Алан Тьюринг: Загадка , Саймон и Шустер , Нью-Йорк. Ср. Глава «Дух истины» для истории, ведущей к его доказательству, и его обсуждения.
• Констанс Рид , Гильберт , Коперник: Springer-Verlag, Нью-Йорк, 1996 г. (впервые опубликовано в 1970 г.). Увлекательная история немецкой математики и физики с 1880-х по 1930-е годы. На его страницах появляются сотни имен, знакомых математикам, физикам и инженерам. Возможно, омрачено отсутствием явных ссылок и несколькими сносками: Рид утверждает, что ее источниками были многочисленные интервью с теми, кто лично знал Гильберта, а также письма и статьи Гильберта.
• Эдвард Бельтрами , что такое случайное? Случайность и порядок в математике и жизни , Коперник: Springer-Verlag, Нью-Йорк, 1999. Хорошее, нежное чтение для математически склонных неспециалистов, ставит более сложные вещи в конец. В нем есть модель машины Тьюринга. Обсуждает вклады Чайтина .
• Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, ISBN 9780191620805
• Эрнест Нагель и Джеймс Р. Ньюман , Доказательство Гёделя , Издательство Нью-Йоркского университета, 1958. Замечательные статьи об очень трудном предмете. Для математически подкованного неспециалиста. Обсуждает генценовский «s доказательство на страницах 96-97 и сносках. В приложениях кратко обсуждаются аксиомы Пеано , а читатели мягко знакомятся с формальной логикой.
• Тейлор Бут , Последовательные машины и теория автоматов , Wiley, New York, 1967. Cf. Глава 9, Машины Тьюринга. Трудная книга, рассчитанная на инженеров-электриков и технических специалистов. Обсуждает рекурсию, частичную рекурсию со ссылкой на машины Тьюринга, проблему остановки. В нем есть модель машины Тьюринга . Ссылки в конце главы 9 охватывают большинство старых книг (с 1952 по 1967 годы, включая авторов Мартина Дэвиса, Ф. К. Хенни, Х. Гермеса, С. К. Клини, М. Мински, Т. Радо) и различных технических статей. См. Примечание в разделе «Программы занятого бобра».
• Программы занятых бобров описаны в Scientific American, август 1984 г., также март 1985 г., стр. 23. Ссылка в Booth приписывает их Радо Т. (1962), О невычислимых функциях, Bell Systems Tech. J. 41. Бут также определяет проблему занятого бобра Rado в задачах 3, 4, 5, 6 главы 9, с. 396.
• Дэвид Болтер , Человек Тьюринга: Западная культура в компьютерный век , Издательство Университета Северной Каролины, Чапел-Хилл, 1984. Для широкого читателя. Может быть датирован. Есть еще одна (очень простая) модель машины Тьюринга.
• Эгон Бёргер. «Вычислимость, сложность, логика». Северная Голландия, 1989 г.
• Стивен Клини , Введение в метаматематику , Северная Голландия, 1952. Глава XIII («Вычислимые функции») включает обсуждение неразрешимости проблемы остановки для машин Тьюринга. В отход от терминологии Тьюринга о машинах без круговорота без холостого хода, Клини вместо этого обращается к машинам, которые «останавливаются», то есть останавливаются.
• Свен Кёлер, Кристиан Шиндельхауэр, Мартин Циглер, Об аппроксимации реальных проблем с остановкой , стр. 454-466 (2005) ISBN 3540281932 Лекционные заметки Springer в томе 3623 компьютерных наук: Неразрешимость проблемы остановки означает, что не на все случаи можно ответить правильно ; но, может быть, «некоторые», «многие» или «большинство» могут? С одной стороны, постоянный ответ «да» будет правильным бесконечно часто, и неправильным также бесконечно часто. Чтобы сделать вопрос разумным, рассмотрите плотность примеров, которые могут быть решены. Оказывается, это существенно зависит от рассматриваемой системы программирования . 
• Логические ограничения машинной этики с последствиями для летального автономного оружия - статья, обсуждаемая в: Означает ли проблема остановки отсутствие моральных роботов?
• Николас Дж. Дарас и Фемистокл М. Рассиас , Современная дискретная математика и анализ: с приложениями в криптографии, информационных системах и моделировании Springer, 2018. ISBN 978-3319743240 . Глава 3 Раздел 1 содержит качественное описание проблемы остановки, доказательство от противного и полезное графическое представление проблемы остановки. 

Внешние ссылки [ править ]

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