Я понимаю доказательство неразрешимости проблемы остановки (приведенное, например, в учебнике Пападимитриу), основанное на диагонализации.

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

В книге доказательство выглядит следующим образом : «предположим , что решает проблемы остановки на входе , т, решает ли машина Тьюринга привалов для ввода Построить машину Тьюринга. , который принимает машину Тьюринга в качестве входных данных , запускает и инвертирует вывод. " Затем он показывает, что не может дать удовлетворительный результат. М ; x M x D M M H ( M ; M ) D ( D $M_H$$M;x$$M$$x$$D$$M$$M_H(M;M)$$D(D)$

Я хотел бы иметь интуицию для, по-видимому, произвольной конструкции , в частности, идеи кормления для себя, а затем для себя. Что побудило людей определить эти конструкции и шаги в первую очередь?M $D$$M$$D$

Есть ли у кого-нибудь объяснение того, как кто-то рассуждал бы о своем пути к аргументу диагонализации (или какому-либо другому доказательству), если бы он не знал этот тип аргумента для начала?

Приложение дано в первом раунде ответов:

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

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

То , что я до сих пор не вижу, что бы мотивировать кого - то , чтобы определить на основе «s„самоприменения“ , а затем снова применить к себе. Похоже, что это меньше связано с диагонализацией (в том смысле, что аргумент Кантора не имел ничего подобного), хотя он, очевидно, хорошо работает с диагонализацией, когда вы их определяете.M M ; М $D(M)$$M$$M;M$$D$

PS

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

В своем редактировании вы пишете:

То , что я до сих пор не вижу, что бы мотивировать кого - то , чтобы определить на основе «s„самоприменения“ , а затем снова применить к себе. Похоже, что это меньше связано с диагонализацией (в том смысле, что аргумент Кантора не имел ничего подобного), хотя он, очевидно, хорошо работает с диагонализацией, когда вы их определяете.M M ; М $D(M)$$M$$M;M$$D$

Распространенное «популярное» обобщение доказательства Тьюринга выглядит примерно так:

«Если бы мы имели машины , которые могли бы решить , будет ли другая машина привалах Тьюринга или нет, мы могли бы использовать это , чтобы построить другую машину , что, учитывая машина Тьюринга , остановятся , если и только если действительно не остановить. Но тогда мы могли бы передать качестве входных данных самому себе и таким образом получить парадокс: эта машина остановится, если и только если она не остановится! " D M M $M_H$$D$$M$$M$$D$

Теперь легко увидеть, что приведенное выше обобщение затушевывает важную деталь - остановка машины Тьюринга также зависит от ее входных данных, которые мы не указали! Но эту проблему можно решить достаточно легко: нам просто нужно, чтобы выбрал какой-то подходящий ввод для каждой машины ввода , прежде чем передать их оба в .Д х М М М $M$$D$$x_M$$M$$M_H$

Каков подходящий выбор для , учитывая, что в конечном итоге мы хотим получить противоречие? Что ж, естественный выбор предлагается непосредственно из приведенного выше «ручного» доказательства, где мы в конечном итоге получаем противоречие, запустив машину на себе.$x_M$$D$

Таким образом, чтобы поведение действительно было парадоксальным в этом случае, то есть когда оно вызывается как , нам нужно, чтобы остановка зависела от поведения при вызове как , Таким образом, мы получим противоречие , мы хотим, установив .D ( D ) D ( M ) M M ( M ) M = $D$$D(D)$$D(M)$$M$ $M(M)$$M = D$

Имейте в виду, это не единственный выбор; мы могли бы также получить такое же противоречие, скажем, построив машину , что останавливается тогда и только тогда, когда (а не ) не останавливается. Но, хотя ясно, что машина может легко продублировать свой ввод перед передачей его в , не совсем очевидно, как сконструировать машину которая бы со своим собственным кодом в качестве ввода. Таким образом, использование этого вместо излишне усложнит доказательство и сделает его менее интуитивным.D ′ ( M ) M ( D ′ ) M ( M ) D M H D ′ M H D ′$D'$$D'(M)$$M(D')$$M(M)$$D$$M_H$$D'$$M_H$$D'$$D$

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

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

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

Кантор даже не использовал диагонализацию в своем первом доказательстве неисчислимости реалов, если мы возьмем даты публикации как приближение того, когда он думал об идее (не всегда надежной вещи), ему потребовалось около 17 лет от того, что он уже знал что действительность неисчислима к выработке аргумента диагонализации.

Что касается «самоприменения» в упомянутом вами доказательстве, это также является неотъемлемой частью парадокса Рассела (который полностью зависит от самоссылки), и первая теорема Гёделя о неполноте подобна мощной версии парадокса Рассела , Доказательство неразрешимости проблемы останова настолько сильно основано на работе Гёделя, что трудно представить, что она может быть достигнута без нее, поэтому идея «самоприменения» уже является частью базовых знаний, которые вам необходимы, чтобы получить решение проблемы останова. , Точно так же работа Геделя является переработкой парадокса Рассела, так что вы не доберетесь туда без другого (обратите внимание, что Рассел был не первым, кто наблюдал подобный парадокс, поэтому прототипы аргумента диагонализации были в формальной логике, так как о 600BCE). Работу Тьюринга и Гёделя (о которых мы здесь говорим) можно рассматривать как все более мощную демонстрацию проблем с самообращением и того, как он встраивается в математику. Итак, еще раз, очень трудно предположить, что эти идеи на уровне Тьюринга имели дело с нимиаприори , они были кульминацией работы тысячелетий в части философии, математики и логики.

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

Самостоятельное применение не является обязательным компонентом доказательства

В двух словах

Если существует машина Тьюринга которая решает проблему остановки, то из этой машины мы можем построить другую машину Тьюринга с характеристикой остановки (характеристикой остановки), которая не может быть характеристикой остановки любой машины Тьюринга.$H$$L$

Парадокс, построенный на самоприкладной функции ( в этом ответе названной - извините за несоответствия обозначений), не является обязательным компонентом доказательства, а устройством, пригодным для построения с одним конкретным противоречием, скрывающим то, что кажется «реальным». Цель "строительства. Наверное, поэтому это не интуитивно понятно.$D$$L$

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

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

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

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

Детальный анализ доказательств

Я не собираюсь быть историческим (но спасибо тем, кто мне нравится), но я только пытаюсь работать с интуитивной стороной.

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

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

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

Случай подмножеств (Кантор)$\mathbb N$

Доказательство Кантора предполагает (это только гипотеза), что существует перечисление подмножеств целых чисел, так что все такие подмножества могут быть описаны его характеристической функцией которая равна если и является в противном случае.C j ( i ) 1 i ∈ S j$S_j$$C_j(i)$$1$$i\in S_j$$0$

Это можно рассматривать как таблицу , такую ​​что$T$$T[i,j]=C_j(i)$

Затем, учитывая диагональ, мы строим характеристическую функцию , что , т. Е. Она идентична диагонали таблицы с каждым битом, переключенным на другое значение.$D$$D(i)=\overline{T[i,i]}$

В диагонали нет ничего особенного, кроме того, что это простой способ получить характеристическую функцию которая отличается от всех других, и это все, что нам нужно.$D$

Следовательно, подмножество, характеризуемое не может быть в перечислении. Так как это было бы верно для любого перечисления, не может быть перечислением , которая перечисляет все подмножества .$D$$\mathbb N$

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

Случай проблемы остановки (Тьюринга)

Мы предполагаем, что у нас есть перечень машин Тьюринга (которые, как мы знаем, возможны). Поведение остановки машины Тьюринга может быть описано ее характеристической функцией остановки которая равна если останавливается на входе и равна противном случае.$M_j$$H_j(i)$$1$$M_j$$i$$0$

Это можно рассматривать как таблицу , такую ​​что$T$$T[i,j]=H_j(i)$

Затем, рассматривая диагональ, мы строим характеристическую функцию остановки, такую, что , то есть она идентична диагонали таблицы с каждым битом, переключенным на другое значение.$D$$D(i)=\overline{T[i,i]}$

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

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

Пока нет оракула и гипотеза вычислимости : мы ничего не знаем о вычислимости и функций .$T$$H_j$

Теперь предположим, что у нас есть машина Тьюринга которая может решить проблему остановки, так что всегда останавливается с в результате.$H$$H(i,j)$$H_j(i)$

Мы хотим доказать , что при , мы можем построить машину , которая имеет характерный останавливая функцию . Машина почти идентична , так что имитирует , за исключением того, что всякий раз, когда собирается завершиться со значением , входит в бесконечный цикл и не прекращается.$H$$L$$D$$L$$H$$L(i)$$H(i,i)$$H(i,i)$$1$$L(i)$

Совершенно очевидно, что мы можем построить такую ​​машину если существует. Следовательно, эта машина должна быть в нашем начальном перечислении всех машин (что, как мы знаем, возможно). Но этого не может быть, так как его поведение остановки соответствует ни одной из перечисленных машин. Машина не может существовать, что означает, что не может существовать.$L$$H$$D$$L$$H$

_{Я нарочно подражал первому доказательству и углубился в крошечные детали}

Я чувствую, что таким образом все происходит естественным образом, особенно если рассматривать доказательство Кантора как достаточно интуитивное.

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

Примечание: чтобы определить функцию , мы могли бы заменить перевернутую диагональ любой другой характеристической функцией остановки, отличной от всех перечисленных в , которая является вычислимой (например, из перечисленных в , при условии, что оракул остановки доступен , Тогда машина должна быть построена соответствующим образом, чтобы иметь качестве характеристической функции остановки, а будет использовать машину , но не подражать так непосредственно . Выбор диагонали делает это намного проще.$D$$T$$T$$L$$D$$L(i)$$H$$H(i,i)$

Сравнение с "другим" доказательством

Определенная здесь функция по-видимому, является аналогом функции в доказательстве, описанном в вопросе.$L$$D$

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

Идея «обычного» доказательства, кажется, пытается убить то, что я вижу как мертвую рыбу. Это говорит: давайте предположим, что - одна из машин, которые были перечислены (то есть, все они). Тогда он имеет индекс в этом перечислении: . Тогда, если останавливается, мы имеем , так что будет зацикливаться по построению. И наоборот, если не останавливается, то так что остановится по построению. Таким образом, у нас есть противоречие. Но противоречие вытекает из того, как характерная функция остановки$L$$j_L$$L=M_{j_L}$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=1$$L(j_L)$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=0$L $L(j_L)$$L$был построен, и кажется гораздо проще просто сказать, что не может быть машиной Тьюринга, потому что она сконструирована так, чтобы иметь характеристическую функцию остановки, которая не является функцией машины Тьюринга.$L$

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

Существует также доказательство этого факта, в котором используется другой парадокс, парадокс Берри, который я слышал от Ран Раза.

Предположим, что проблема остановки была вычислима. Пусть наименьшее натуральное число, которое не может быть вычислено программой на C длины . То есть, если является набором натуральных чисел, вычисленных C-программами длины , то является наименьшим натуральным числом, отсутствующим в .n S ( n ) n B ( n ) S ( n $B(n)$$n$$S(n)$$n$$B(n)$$S(n)$

Рассмотрим следующую программу:

1. Пройдите все программы на C длиной не более .$n$

2. Для каждой такой программы проверьте, останавливается ли она; если это произойдет, добавьте его в список .$L$

3. Выход первого натуральное число , не в .$L$

Это программа для вычисления . Насколько велика эта программа? Кодировка принимает символов, а остальная часть программы не зависит от , поэтому общая длина составляет , скажем, самое большее . Выберите так , что . Тогда наша программа, длина которой не больше , вычисляет , что противоречит определению .n O ( log n ) n O ( log n ) C log n N C log N ≤ N N B ( N ) B ( N $B(n)$$n$$O(\log n)$$n$$O(\log n)$$C\log n$$N$$C\log N \leq N$$N$$B(N)$$B(N)$

Эта же идея может быть использована для доказательства теорем Гёделя о неполноте, как показали Кричман и Раз .

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

Для любой машины Тьюринга Tесть машина Тьюринга, Rкоторая вычисляет R(x) = T(R;x).

Если бы у нас была машина Тьюринга, которая могла бы решить проблему остановки, то, используя идею, описанную выше, мы могли бы легко построить множество «лжец» машин Тьюринга: например, в нотации, подобной Python,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

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

R(x) = T(R; x)

Сначала определите

S(M; x) = T(M(M; -); x)

где под тем M(M; -), что я на самом деле имею в виду, мы вычисляем (используя описание M) и подключаем описание машины Тьюринга, которое при вводе yоценивает M(M; y).

Теперь мы наблюдаем, что если мы подключимся Sк самому себе

S(S; x) = T(S(S; -); x)

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

R = S(S; -)

тогда мы имеем

R(x) = T(R; x)

по желанию.

доказательство Тьюринга весьма сходно с доказательством Кантора, что мощность действительных чисел («неисчислимых») больше, чем мощность рациональных чисел («исчисляемых»), поскольку они не могут быть приведены в соответствие 1-1, но это не отмечено / подчеркнуто в очень много ссылок (кто-нибудь знает какие-нибудь?). (iirc) Профессор CS однажды показал это несколько лет назад в классе (не уверен, где он сам это получил). в доказательстве Кантора можно представить сетку с горизонтальным измерением n- ^й цифрой числа и вертикальным измерением n- ^го числа множества.

Конструкция доказательства остановки по Тьюрингу очень похожа, за исключением того, что содержимое таблицы равно Halt / Nonhalt для 1/0, а горизонтальная ось - это n- ^й вход, а вертикальная ось - это n- ^я компьютерная программа. другими словами, комбинация компьютерных программ и входных данных может быть исчисляемой, но бесконечная таблица / массив неисчислима на основе конструкции универсального симулятора машины, которая может «перевернуть» остановку в случай остановки, предполагая, что машина детектора остановки существует (следовательно, reductio ad absurdam ) ,

некоторые доказательства того, что Тьюринг имел в виду конструкцию Кантора отчасти, состоят в том, что его та же самая статья с остановочным доказательством говорит о вычислимых числах как (вдоль линий) действительных чисел с вычислимыми цифрами.

На данный момент стоит отметить работу Эмиля Поста, которому (справедливо) приписывают то, что он был со-первооткрывателем основных результатов вычислимости, хотя, к сожалению, был опубликован слишком поздно, чтобы считаться со-первооткрывателем решения проблемы Entscheidungs. , Он, конечно, участвовал в разработке так называемого тезиса Черча-Тьюринга .

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

Проблема Entscheidungs ​​рассматривает возможность использования такого средства вычисления, чтобы сказать, определить теорему любого предложения, выражаемого в системе Principia Mathematica . Но ПМ была системой, явно разработанной для того, чтобы иметь возможность представлять все математические рассуждения и, соответственно, (по крайней мере, в то время, когда логика все еще была в моде) все человеческие рассуждения!

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

Таким образом, на данный момент ясно, что самообращение, или способность систем описывать себя, было довольно естественным предметом в начале 1930-х годов. Фактически, Дэвид Гилберт надеялся «начать» математические рассуждения сам, предоставив формальное описание всей человеческой математики, которая затем может быть математически доказана как сама по себе!

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

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

программа pвозвращает результат trueпри вводеn

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

эта программа всегда врет.

может быть выражено

Программа pвсегда возвращает противоположность тому, что скажут, как утверждают pPrincipia Mathematica.

Сложность в построении программы p. Но на данный момент вполне естественно рассмотреть более общее предложение

Программа pвсегда возвращает противоположное тому, что скажет премьер q.

для некоторых произвольно q. Но это легко построить p(q)для любого данного q! Просто вычислите, что PM предсказывает, что он выведет, и верните противоположный ответ. Мы не можем просто заменить qна pв данный момент , хотя, так как pпринимает в qкачестве входных данных, и qнет (она не принимает никакого ввода). Давайте изменим наше предложение так, чтобы p оно принимало ввод:

Программа pвозвращает противоположное тому, что говорит PM q(r).

Arg! Но теперь pтребуется 2 части ввода: qи r, тогда как qтолько 1. Но подождите: мы pвсе rравно хотим в обоих местах, так что это не новая часть информации, а снова та же самая часть данных, а именно q! Это критическое наблюдение.

Итак, мы наконец получили

Программа pвозвращает противоположное тому, что говорит PM q(q).

Давайте забудем об этом глупом «премьер-министре», и мы получим

Программа p(q)возвращает противоположное тому, q(q)что вернется.

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