Почему действительно так важна проблема остановки?

149

Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Википедия [статья] [1] правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

Мне кажется, что доказательство проблемы остановки является не чем иным, как так называемым «парадоксом», самореферентным (по крайней мере, циклическим) противоречием так же, как парадокс лжеца. Единственный вывод, который она делает, заключается в том, что функция остановки восприимчива к таким некорректным вопросам.

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

4 года спустя : когда я написал это, я только что посмотрел это видео . Программист получает несколько программ, должен определить, какие из них заканчиваются, и видео продолжает объяснять, почему это невозможно. Я был разочарован, потому что я знал, что, учитывая некоторые произвольные программы, есть некоторая возможность, что главный герой сможет доказать, прекратились ли они. Понятие общности как-то потеряно. Разница заключается в том, что «некоторые программы не могут быть завершены», и «ни одна из программ не может быть подтверждена». Многие алгоритмы формально продемонстрированы для этого. Неспособность сделать это различие по каждой отдельной ссылке, которую я нашел в Интернете, заключалась в том, как я пришел к названию этого вопроса. По этой причине я очень ценю ответ это переопределяет функцию остановки как троичную вместо логической.

казарка
источник
16
«детерминированная машина с конечной памятью» скучна, поскольку это не более чем конечный автомат; они не полезны для моделирования расчетов в целом. Что касается проблемы остановки: это конкретный пример для функции, которая не является вычисляемой (по Тьюрингу). Если вас устраивает неконструктивное доказательство, оно вам «не нужно». Это все еще имеет историческое значение, хотя.
Рафаэль
16
Тем не менее, ваш вопрос выглядит как плохо информированный. Возможно, вы захотите освежить свои основы теории вычислимости (которая бросит вызов вашей интуиции, основанной на реальности, а не на моделях, обсуждаемых там). Смотрите наши справочные вопросы для начала. Если вам требуются дополнительные «доказательства» того, что ваша интуиция (насколько позволяет теория) фатально ошибочна, прочитайте этот вопрос .
Рафаэль
12
«Вы можете использовать алгоритм, который определяет, будет ли связанный список зацикливаться, чтобы реализовать функцию остановки с пространственной сложностью O (1)», - но если вы хотите решить проблему для компьютера с 2 ГБ памяти, вам понадобится более 2 ^ 2000000000 шагов и компьютер побольше.
user2357112
11
Давным-давно я беседовал с другом о проблеме остановки, и кто-то, сидевший рядом, спросил: «Что такое проблема остановки, это важно?» и мой друг повернулся к нему и сказал: «Если бы мы могли решить проблему остановки, мы могли бы строить города на облаках». Это правда.
Фрэнсис Дейви,
8
@emory Утверждение бессмысленно верно: P => Qверно для любого Q, если мы знаем, что Pоно ложно (и мы знаем, что проблема остановки не разрешима). С таким же успехом Фрэнсис мог сказать: «Если бы мы могли решить проблему остановки, мы могли бы найти лекарство от самой смерти». Это способ определения логического смысла.
Амаллой

Ответы:

217

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

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

У вас есть JavaScript с некоторыми переменными с высоким уровнем безопасности, а некоторые с низким уровнем безопасности. Вы хотите убедиться, что злоумышленник не может получить информацию с высоким уровнем безопасности. Это тоже просто проблема остановки.

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

У вас есть антивирусная программа, и вы хотите увидеть, выполняет ли она когда-либо вредоносную инструкцию. На самом деле просто проблема остановки.

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

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

  2. Вам понадобится состояний, если у вас n бит ОЗУ. Так что для вашего современного компьютера на 8 ГБ это . Это число настолько велико, что вольфрам альфа даже не знает, как его интерпретировать. Когда я делаю он говорит, что у него десятичных цифр. Это явно слишком много для хранения на обычном компьютере.2 32000000000 2 10 9 3000000002n2320000000002109300000000

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

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

ОБНОВЛЕНИЕ: Просто для решения пары вопросов, поднятых в комментариях.

@Tyler Fleming Cloutier: «бессмысленная» проблема возникает в доказательстве того, что проблема остановки неразрешима, но в основе неразрешимости действительно лежит бесконечное пространство поиска. Вы ищете объект с заданным свойством, и если он не существует, нет способа узнать, когда вы закончите.

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

Подробнее об этом смотрите Арифметическая Иерархия . Все что выше неразрешимо, хотя уровень 1 полуразрешим.Σ00=Π00

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

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

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

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

jmite
источник
4
@Mehrdad Для любого разумного определения «максимально быстрого машинного кода для данной программы» вопрос имеет смысл, и ответ таков: «Не может быть такого компилятора».
Дэвид Ричерби
13
Он также работает для поиска как можно более короткого машинного кода для вывода, кода с наименьшим количеством обращений к памяти и т. Д. И т. Д. Для общих программ поиск любого оптимального преобразования неразрешим. Это в основном теорема Райс.
Jmite
4
В качестве следствия к тому, что мы все еще ищем магический алгоритм Гильберта, без тесно связанной концепции эквивалентности Тьюринга, мы все равно будем спорить о том, допускают ли gotos или самоизменяющийся код более мощные вычисления, ища вычислительно более мощные формы аппаратного обеспечения. и аргументы в пользу лучшего языка программирования были бы гораздо более субъективными, чем сейчас.
sdenham
3
Это даже появляется в местах, которые вы не ожидаете. Хотите написать компилятор C ++, который отклоняет все недопустимые программы при компиляции всех допустимых? Сначала решите проблему остановки - метапрограммирование шаблона C ++ завершено по Тьюрингу, поэтому для решения вопроса о том, являются ли ваши шаблоны действительными или нет в общем случае, необходимо ее решить.
Отметить
7
@Merhrdad: Ваш пример «симуляции всей компьютерной программы» является отличным примером того, почему проблема остановки так важна. Для некоторых программ имитация программы не так проста, как кажется (например, посмотрите на страницу Википедии о остановке). Если проблема может быть обманчива в этой форме, вы можете себе представить, как трудно объяснить кому-то более скрытую форму (например, проблему с антивирусом)
Cort Ammon
49

В практическом плане это важно, потому что это позволяет вам сказать своим невежественным руководителям «то, что вы спрашиваете, математически невозможно».

Проблема остановки и различные NP-полные задачи (например, задача коммивояжера) прийти вверх много в форме «Почему вы не можете просто сделать программу , которая делает X?», И вы должны быть в состоянии дать объяснение почему это невозможно или неосуществимо в оставшееся время жизни вселенной.

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

o11c
источник
16
Ну, @bishop, кроме Flickr, сделал практически невозможное .
Франциско Презенсия
8
можно спроектировать язык, который не является полным по Тьюрингу : пример полезного не полного по Тьюрингу языка: SQL (фактически урезанный SQL). Полнота Тьюринга автоматически добавит к языку отсутствие завершения, чего вы, вероятно, не хотите при выполнении запроса к базе данных. (Хотя, боюсь, все современные реализации SQL в любом случае предлагают полноту
тьюринга
8
@FranciscoPresencia: они использовали исследовательскую группу, поэтому общая точка зрения остается в силе.
RemcoGerlich
4
@MooingDuck: Flickr не выбирает между парками и птицами, он (пытается) подтвердить одно или оба. ИЛИ не XOR.
Рикстер
45

Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

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

Проблема остановки для данного компьютера конечного размера не может быть решена на этом компьютере конечного размера. Это может быть решено только на большом компьютере. (Это верно для любого метода, не только для того, который вы предлагаете. Я не собираюсь приводить формальное доказательство, но вот суть. Если компьютер C может запускать N разных программ, из которых хотя бы один P не завершает работу затем компьютер V, который может проверить, должны ли эти N программы останавливаться, также может запускать различные программы верификатора N. Если C и V - это один и тот же компьютер, то P не является одной из N различных программ, которые запускает V, поэтому На компьютере должно быть запущено не менее N + 1 разных программ, что противоречит предположению, что C запускает N разных программ.)

Кроме того, вы не можете просто использовать алгоритм для обнаружения цикла в связанном списке. Вы должны знать, когда остановиться. Вы можете остановиться, выполнив столько шагов, сколько имеется состояний на компьютере. Если программа использует до бит памяти, то она может иметь различных состояний. Это очень быстро становится невозможным. Например, типичный компьютер выполняет порядка миллиарда команд в секунду; один миллиард секунд - немногим более 30 лет. Таким образом, если вы управляете компьютером в течение 8 лет, вы можете проверить, останавливается ли одна программа с 250 миллионами миллиардов потенциальных состояний. Но это только состояний, то есть вы можете протестировать только программу, которая работает в 7 байтах памяти.2 М 2 56M2M256

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

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

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

Существует более общий результат, называемый теоремой Райса, который утверждает, что любое нетривиальное свойствопрограмм неразрешима - любое свойство, которое зависит только от поведения программы, а не от того, каким образом она написана (например, «исходный код состоит из менее чем 42 символов?», ясно разрешимо, тогда как «есть ли Программа, исходный код которой содержит менее 42 символов и которая возвращает один и тот же результат для всех входных данных? »- это не так, и« эта программа вообще ничего не выводит? »). Остановка - это только один пример. Это важно, потому что это часто встречается на практике (обычно, мы хотим знать, будет ли программа возвращать результат в разумные сроки, учитывая ограниченные ресурсы компьютера, на котором она работает, но так как это практически не отвечает, мы готовы согласиться на более простой вопрос о том, будет ли программа в конечном итоге завершена при наличии достаточного времени и памяти).

жилль
источник
2
Я бы подумал, что вопрос «есть ли программа, которая выдаст тот же вывод, что и данная отдельная программа (без ввода, кроме самой программы), но за меньшее время, включая время загрузки программы ?» будет решаемо, хотя и трудно, поскольку максимальная продолжительность программ-кандидатов будет ограничена, как и время тестирования каждой из них.
суперкат
@supercat Да, это свойство разрешимо. Это не разрешимо для общего случая программы, которая принимает данные.
Жиль
1
У меня сложилось впечатление, что проблема остановки обычно предполагает, что все входные данные, которые программа получит в ходе своего выполнения, связаны с программой. Если бы у кого-то была машина, которая могла бы волшебным образом решить проблему остановки для любой программы, использующей какую-либо конкретную последовательность ввода, может ли такая машина определить, остановится ли программа для всех входов ограниченной длины?
суперкат
3
@supercat Нет, оракул с остановками на все входы будет на один шаг выше, чем оракул с остановками на вводе. Это сделало бы хороший вопрос для этого сайта ... на самом деле он у нас есть . Кстати, моя ментальная модель по умолчанию - рекурсивные функции, где «ввод» означает «аргумент», а запуск программы означает применение ее к аргументу; Вы правы, что мое утверждение неверно в контексте, касающемся машин Тьюринга, я его обновлю.
Жиль
28

Мне кажется, что проблема остановки является не чем иным, как так называемым «парадоксом», самореферентным (по крайней мере, циклическим) противоречием так же, как парадокс лжеца. Единственный вывод, который она делает, заключается в том, что функция остановки восприимчива к таким некорректным вопросам.

Нет, это не то , что проблема остановки о. Парадоксы, такие как парадокс лжеца, не являются правдой или ложью, они просто не имеют смысла. С другой стороны, детерминистический алгоритм либо остановится для данного ввода, либо будет работать вечно. Функция halts(program, input)имеет совершенно определенное, детерминированное значение для каждой программы, для каждого входа. Мы просто не можем решить это для любой программы. Или, точнее: мы не можем написать программу, которая может решить ее для каждой пары программа / вход.

Аналогичным (возможно, менее абстрактным) примером является функция «занятый бобер» , интуитивно определяемая как Самая длинная последовательность из 1-й машины Тьюринга с состояниями, начиная с пустой ленты, может записать до ее завершения. Для любого существует только конечное число машин Тьюринга, и каждая из них либо завершается в какой-то момент (затем вы можете сосчитать количество единиц), либо она работает вечно (тогда занятому бобру это не безразлично - оно смотрит только на программы, которые завершаются). Итак, функция занятого бобра имеет детерминированное значение для каждого . (Мы даже знаем это за несколько небольшихn n n n Σ ( n )Σ(n):=nnnn, потому что мы можем посмотреть на каждую программу и найти доказательства того, почему они никогда не остановятся.) Но не может быть программы, которая вычисляет .Σ(n)

nikie
источник
2
Стоит отметить, что в обычной форме парадокс лжеца явно ссылается на себя, но та же проблема может возникнуть, даже если это не так. Является ли ответ на утверждение, сформированный путем взятия текста: «Является ли ответ на утверждение, сформированный путем взятия текста и вставки после первой запятой копии, заключенной в кавычки, нет?» и вставляя после первой запятой копию, заключенную в одинарные кавычки, нет? Такое утверждение не является явно самоссылочным, но относится к правдивости утверждения, которое является идентичным для каждого символа.
суперкат
2
@supercat: да, я не думаю, что видел ангар на английском раньше ...
SamB
@SamB: я видел несколько, но решил попробовать свои силы в оригинальной формулировке, которая, хотя и более многословна, чем некоторые, читает (возможно) более естественно.
суперкат
24

Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Статья в Википедии правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

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

И во-вторых, даже теоретически имеет смысл рассматривать современный компьютер как бесконечный конечный автомат. У машины Тьюринга нет бесконечной ленты, у нее есть лента, которая всегда может быть удлинена, когда у машины заканчивается память. И разве это не то, что мы можем сделать с реальными компьютерами? (И если адресное пространство ЦП заканчивается, мы можем использовать облако и т. Д.)

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

Существует разница между проблемой остановки и доказательством ее неразрешимости. Проблема остановки - это просто спецификация для программы : в качестве входных данных программа получает исходный код программы и входных данных , и программа должна возвращать значение true, если останавливается на входе и false в противном случае. Это очень четкая спецификация; в этом нет ничего парадоксального: каждая пара исходного кода и ввода имеет один четко определенный правильный ответ.P x H P xHPxHPx

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

Hoopje
источник
1
+1 за объяснение связи между реальными компьютерами, конечными автоматами и машинами Тьюринга, что является важной частью постановки вопроса.
Дэвид Ричерби
1
Вы пробудили мой интерес. В чем разница между кажущимся и реальным противоречием?
Brent
Иначе говоря, программирование не предполагает ограниченных ресурсов. Большинство алгоритмов, которые мы разрабатываем, или программ, которые мы пишем, не написаны так, чтобы использовать ограниченный или даже фиксированный объем вычислительных ресурсов, если мы специально не разработаем их так, чтобы способ (например, это часто требуется при программировании для встроенных систем).
reinierpost
3
@Brent. Многие парадоксы вовсе не противоречат друг другу, а только на первый взгляд. Когда мы смотрим ближе, оказывается, что в рассуждении есть ошибка, или какое-то слово, значение которого немного изменилось, если использовать его в другом контексте, или что-то подобное. Однако иногда парадокс выявляет настоящее противоречие.
Hoopje
Я изучал эту проблему, начиная с моего ОП. Означает ли теорема Гёделя о неполноте, что всегда можно придумать какой-то парадокс, независимо от используемой системы логики?
Брент
17

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

Самостоятельная ссылка не парадоксальна!

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

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


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

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

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

Кава
источник
14

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

Еще один интересный аспект заключается в том, что в теории чисел (диофантовых) возникли очень старые проблемы, возникшие у греков и не доказанные тысячелетиями. есть связанный результат, что общие вопросы о диофантовых уравнениях неразрешимы и называются десятой проблемой / теоремой Гильберта . Гильберт жил на рубеже 20-го века и предложил в качестве исследовательской программы, что математика может найти систематические подходы к математическим задачам. этот вызов / план был серьезно поражен открытием неразрешимости, которое произошло несколько десятилетий спустя. неразрешимость продолжает оставаться очень продвинутой областью исследований, и граница между неразрешимыми и разрешимыми проблемами, вероятно, всегда будет подвергаться дальнейшему изучению и анализу.

ВЗН
источник
14

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

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

Иными словами, мы не только не можем решить Halt, мы не можем обнаружить, что программа - это та программа, которую мы не можем определить, если она останавливается, за исключением грубой меры типа «если для ее выполнения требуется более 1 минуты, притвориться это не останавливает ".

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

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

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

Вы хотите знать, принимает ли машина Тьюринга хотя бы целые числа? Неразрешимые.

Вы хотите знать, принимает ли машина Тьюринга арифметические последовательности? Неразрешимые.

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


1 К property ofэтому не относится механизм того, как это принято - только то, что принято. «Он принимает за 100 или менее шагов» - это свойство, которое он принимает, а не того, что принято.

Yakk
источник
Возможно, вы захотите объяснить, что такое «свойство», поскольку наивное толкование, которое вы можете сделать, скорее всего, будет неправильным.
Рик Декер
@ Рук, я думаю, сноска закрывает это сейчас?
Якк
7

Вы правы в том, что проблема остановки, как это обычно вводят и заявляют, является простой ошибкой. Это не доказывает, что не может быть трехзначной функции остановки ('halts', 'loops', 'not know'), которая на практике всегда возвращает 'halts' или 'loops' и возвращает только 'don' например, для специально сконструированных угловых шкафов.

Две причины, по которым проблема остановки является существенной:

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

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

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

анонимное
источник
5

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

f(0)=1f(0)=2hh(M)MHhh

Теодор Норвелл
источник
3
Я не следую Функция остановки является совершенно четко определенным и действительным предикатом - для любой конкретной машины Тьюринга и любого заданного ввода машина останавливается или зацикливается. (Вам не хватает надлежащего упоминания; какой папара вы суммируете?)
Рафаэль
@ Рафаэль То, что функция четко определена, обычно воспринимается как факт. Точка зрения Хенера другая и объясняется в его работах. Я отредактирую свой ответ, чтобы предоставить названия бумаг.
Теодор Норвелл
Скажем так, что, как бы ни говорил Хенер [я не читал газеты], они оказались спорными, по крайней мере, в первом чтении / приближении: « cs.toronto.edu/~hehner/Shallitaffair.pdf и recursed.blogspot.com/ 2013/10 / eric-hehner-replies.html
Fizz,
И не ясно, учитывая природу и количество ссылок, которые есть в работах Хенера (по этому поводу), что любые дополнительные чтения (его работ по этому вопросу) стоят хлопот.
Fizz
Его доказательства кажутся очень убедительными и указывают на то, что это просто перефразировка глупых вещей, которые вы можете сделать в философии, например попытка проанализировать следующее самоссылочное утверждение на предмет его правдивости: «Это предложение неверно». что, если истина означает, что это ложь, что означает, что это было на самом деле правда, нет, что делает его снова ложным ... так что это похоже на не столь важный философский вопрос морского взора. en.wikipedia.org/wiki/Liar_paradox парадокс остановки может быть случаем ученых, не говорящих с философами.
Джеймс Уэйкфилд
3

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

Это последняя лекция MIT 1986 «Структура и интерпретация» ; профессор спрашивает: "Есть ли вопросы?" и готовится закончить лекцию, когда один из студентов спрашивает: «Это последний вопрос?»

Задумайтесь об этом на мгновение. Как учитель может ответить на это? Если ученик решает противоречить учителю, он не может дать действительного ответа - это похоже на проблему остановки.

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

PS: Если вы не знаете, о каком курсе я говорю, посмотрите его, это круто.

SlySherZ
источник
Но если я выполню doesHalt(programCode, input);, программа не может знать, что doesHaltвозвращает функция. Невозможно прервать выполнение программы после того, как doesHaltфункция ее оценила.
Tvde1
0

Я легко могу написать программу, которая дает вход n, либо выводит наименьшее простое число p> n, такое что p + 2 также простое число, либо работает вечно, если такого p не существует. Если вы можете решить проблему, чтобы предсказать, будет ли моя программа останавливаться для каждого входа, вы только что решили гипотезу Твин Прайм.

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

gnasher729
источник
Я думаю, что вы смешиваете «неразрешимый по Тьюрингу» с совершенно другим понятием; на самом деле, вы можете случайно наткнуться на «ту же самую старую» ошибку. Смотрите также здесь и здесь .
Рафаэль