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

30

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

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

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

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

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

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

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

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

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

PS

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

user118967
источник
3
Рассмотрим возможность того, что любое доказательство существования неисчислимых множеств должно быть несколько нелогичным, даже если мы привыкнем к тому, что они верны . Также рассмотрите возможность того, что этот вопрос (если перефразирован) принадлежит math.stackexchange.com .
Андре Соуза Лемос
4
Кантор нашел аргумент диагонализации, и теперь мы не можем его отучить: Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können .
Хендрик Ян
1
После дальнейших размышлений я должен спросить, почему вы думаете, что это так отличается от парадокса Рассела. Парадокс Рассела выглядит даже так же, если мы используем обозначение для обозначения (то есть думать о множествах как о функциях, значения которых равны или ). Тогда парадокс Рассела состоит в том, чтобы определить , а затем рассмотреть . X SS(X)XStruefalseD(M) = not M(M)D(D)
1
Диагонализация является стандартной техникой . Конечно, было время, когда это не было известно, но это было стандартным в течение длительного времени, поэтому ваш аргумент просто из-за вашего невежества (я не хочу быть грубым, это факт: вы не знали все остальные доказательства, которые используют такую ​​технику и, следовательно, находят ее странной в первый раз, когда вы ее видите. Когда вы увидите ее 50 раз, вы, вероятно, сможете понять, как ее можно применить в новой ситуации).
Бакуриу
1
Возможно, вы бы прочитали мой обмен комментариями с Люком Мэтисоном (после его ответа). Его ответ исторически объясняет, почему Тьюринг использовал самоприменение (одна вещь, о которой вы спрашиваете в своем вопросе). Кажется, именно так математики воспринимали проблемы в то время. Мой собственный ответ пытается дать очень простое доказательство того, что оно не используется (или, по крайней мере, показывает, что оно не является существенным), что является другой вещью, о которой вы просите, совсем другой. Возможно, я мог бы сделать это еще проще, чем в своем ответе. Почему учителя до сих пор используют доказательства Тьюринга - это социологическая и педагогическая (?!) Проблема. cc @HendrikJan
Бабу,

Ответы:

18

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

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

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

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

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

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

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

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

Илмари Каронен
источник
1
Вау, ты действительно ухватился за мой вопрос! Это именно та история, которую я искал! Всё ещё читаю, но похоже, что это будет принятый ответ. Благодарность!
user118967
18

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

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

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

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

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

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

Люк Мэтисон
источник
2
Да, похоже, весь смысл Тьюринга заключался в том, чтобы воссоздать цикличность (от которой происходит диагонализация) с помощью машин, чтобы ввести какое-то абстрактное представление о времени , с которым можно по-новому говорить о конечности.
Андре Соуза Лемос
Может быть, вы можете просветить меня, так как я не знаком с некоторыми из этих доказательств. Я могу понять, что эти доказательства могут быть обнаружены с помощью самореференции. Я даже могу поверить (хотя это может нуждаться в доказательстве), что всегда есть некоторая самостоятельная ссылка, которую можно найти в любой структуре, созданной для этой цели. Но я не вижу необходимости использовать это явно, чтобы провести доказательство к его заключению. Вы можете перефразировать аргумент Кантора таким образом, но это не обязательно. И я не понимаю, почему вы должны сделать это для решения проблемы остановки. Возможно, я пропустил шаг, но какой?
Бабу
Чтобы сделать мое предыдущее замечание более ясным, первоначальный вопрос звучит так : « Есть ли более интуитивное доказательство неразрешимости проблемы остановки ... ». Я опускаю конец, так как мне кажется, что ФП жалуется в основном на отсутствие интуиции. Я считаю, что действительно есть более интуитивное доказательство, не использующее самоссылку. Вы можете подумать, что использование этого доказательства неразумно с педагогической точки зрения (как не связанное с работой Рассела и Геделя), но если оно отвечает на заданный вопрос, какой смысл его отвергать. Вы, кажется, отрицаете вопрос, а не отвечаете на него.
Бабу
@babou Думаю, проблема в том, что мы отвечаем на разные вопросы. Я полагаю, что ОП не был хорошо сформулирован в этом отношении. Мне кажется, что повторяющийся вопрос в теле ОП звучит так: «Как кто-то когда-либо думал об аргументе диагонализации, чтобы доказать ...» (перефразируя, конечно), и что «конструкции кажутся извлеченными из волшебной шляпы» ,
Люк Мэтисон
@babou, также, чтобы уточнить немного, с надлежащей клавиатурой, я не думаю, что так или иначе обязательно педагогически полезно (это будет сильно зависеть от контекста). На самом деле, для большинства современных курсов CS лучше делать это без аргумента диагонализации, большинство студентов CS просто недостаточно математически склонны к тому, чтобы знать предпосылки, которые облегчили бы понимание, но я определенно отвечал на вопрос, который закончился первоначальный основной текст: ...
Люк Мэтисон
9

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

В двух словах

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Babou
источник
Очень хорошо, спасибо! Похоже, что каким-то образом вам удалось обойти самоприменимые конструкции, которые мне показались неприятными. Теперь я удивляюсь, почему люди считают их необходимыми.
user118967
@ user118967 Я пытался подчеркнуть, что использование диагонали не очень важно. Все, что вам нужно, - это определить характеристическую функцию остановки, которая отличается от всех перечисленных в таблице и вычислима из перечисленных, при условии, что у нас есть оракул остановки. Таких характерных функций остановки бесконечно много. Теперь это кажется не таким заметным в обычном доказательстве, и, возможно, некоторые конструкции этого доказательства кажутся произвольными просто потому, что они подобны выбору диагонали в приведенном выше доказательстве. Это просто, не важно.
Бабу
@ user118967 Я добавил и введение, которое суммирует анализ различных доказательств. Он дополняет сравнение между доказательствами (с самостоятельным применением и без него), приведенное в конце. Я не знаю, покончил ли я с диагонализацией, как меня просили :) (я думаю, было бы несправедливо так сказать), но я намекаю, как покончить с очевидной диагональю. И в доказательстве не используется самоприменение, которое кажется ненужным, но хитрым на вид, трюком, скрывающим то, что может показаться более важной проблемой - поведение остановки.
Бабу
@ user118967 Чтобы ответить на ваш первый комментарий и после того, как вы прочитали наиболее одобренный ответ, кажется, что основной мотивацией является связь с работами Рассела и Геделя. Теперь я понятия не имею, действительно ли это важно для этой цели, и вариант самоприменимых конструкций, безусловно, можно изучить для этой цели, но я не вижу смысла навязывать его всем. Кроме того, более прямое доказательство кажется более интуитивным и дает инструмент для дальнейшего анализа самоприменяющейся версии. Почему тогда?
Бабу
Да, я склонен согласиться с вами в этом.
user118967
8

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

Предположим, что проблема остановки была вычислима. Пусть наименьшее натуральное число, которое не может быть вычислено программой на C длины . То есть, если является набором натуральных чисел, вычисленных C-программами длины , то является наименьшим натуральным числом, отсутствующим в .n S ( n ) n B ( n ) S ( n )B(n)nS(n)nB(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)nO(logn)nO(logn)ClognNClogNNNB(N)B(N)

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

Юваль Фильмус
источник
Возможно, это в статье, которую я цитирую, или в классической монографии Колмогорова «Сложность» Ли и Витани.
Юваль Фильмус
Кстати, вы думаете, что этот метод обеспечивает атаку на проблему NP против CoNP?
Мухаммед Аль-Туркистани
Нет. Такие проблемы вне нас в данный момент.
Юваль Фильмус
n
nnn
6

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

Для любой машины Тьюринга 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)

по желанию.


источник
Первый абзац не соответствует приведенной вами теореме, которую я знаю под названием теоремы smn.
Рафаэль
@Raphael: в моем учебнике это называется теорема о рекурсии. :( Моя краткая попытка Google не смогла
Не стоит беспокоиться; может я вас не так понимаю, или есть разные названия для одной и той же вещи. Тем не менее, ваше предложение «машины Тьюринга могут использовать свое собственное описание» не подтверждается приведенной вами теоремой. На самом деле, я думаю, что это неправильно: если функция, которую вычисляет TM, зависит от ее индекса, как будет выглядеть все бесконечно много TM, которые вычисляют одну и ту же функцию?
Рафаэль
TliarTruenot liar()False
TRR(x)=T(R;x)TRR(x)=T(R;x)
5

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

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

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

ВЗН
источник
Кроме того, действительно существует очень «интуитивный» способ увидеть неразрешимость, но для его понимания требуется много высшей математики (т. е. интуиция неофита сильно отличается от интуиции эксперта). математики рассматривают проблему остановки и приводят идентичные доказательства через теорему Лаврэра о неподвижной точке, но это передовой факт, который не так доступен для студентов «пока». видите проблему остановки, невычислимые множества, общую математическую проблему? Теоретическая информатика, а также связанный пост для рефери
vzn
3

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

Коди
источник