Может ли проблема остановки быть «решена» путем перехода к более высокоуровневому описанию вычислений?

21

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

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

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

Н2СО3
источник
1
Добро пожаловать на биржу компьютерных наук. Пожалуйста, прочитайте cs.stackexchange.com/tour.if, если вы еще этого не сделали. --- Что вы пробовали для более мощной модели, чем ТМ? Что вас блокирует?
Бабу
2
@babou Напротив, вам нужна менее мощная модель.
Юваль Фильмус
2
@YuvalFilmus Ну, ОП просит более сильную модель, а не более слабую. --- с извинениями перед H2CO3 ... Мой вопрос был на самом деле шуткой, поскольку это стандартный вопрос, когда люди задают свои домашние задания как вопрос. Это было, конечно, неуместно, так как никто не ожидает, что вы найдете такую ​​модель. Я надеюсь, что вы не будете принимать это слишком кислотно.
Бабу
1
Возможно, вы захотите прочитать о гиперкомпьютерах en.wikipedia.org/wiki/Hypercomputation .
Эрик Тауэрс

Ответы:

15

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

Нет такой ситуации с теорией вычислений и проблемой остановки. Здесь нет парадокса, нет противоречий. Просто так получилось, что нет машины Тьюринга, которая могла бы решить проблему остановки ТМ. Это просто теорема, а не парадокс.

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

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

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

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

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

Babou
источник
Предполагая, что ZFC непротиворечив, он все еще неполон, т.е. есть предложения, которые мы не можем ни доказать, ни опровергнуть из ZFC, и это тесно связано с неразрешаемостью проблемы остановки, если бы остановка была разрешимой, мы могли бы доказать или опровергнуть все предложения. Это математика, и это не противоречие, которое нужно решить, но также теорема (Гёдель)
Hernan_eche
@Hernan_eche Ну ... да и ... что ...? Если вы считаете, что непоследовательность не хуже неполноты, это ваше личное суждение. Я сомневаюсь, что большинство математиков согласятся. Вам может не понравиться ТМ, который не заканчивается. Но вы бы хотели, чтобы они лучше заканчивались всегда, говоря иногда «да», а иногда «нет» на одном и том же входе. Что бы вы ответили? И если вы думаете, недетерминизм ... подумайте дважды.
Бабу
Я прокомментирую просто, чтобы прояснить, что информатика и математика борются с одними и теми же проблемами, чтобы не дать читателям неверно истолковать ответ, как будто математика решила свои фундаментальные проблемы с ZFC, а проблема остановки была просто проблемой информатики, это не так, есть взаимно однозначное соответствие между неполнотой и проблемой остановки, это та же проблема. Я не думаю, что неполнота хуже или лучше непоследовательности, но я думаю, что неполнота станет непоследовательностью, если вы захотите построить системы более высокого порядка.
Hernan_eche
17

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

Однако у этого подхода есть две проблемы.

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

  2. Никто никогда не предлагал каким-либо образом физически реализовать такого оракула. Это все очень хорошо, как теоретическое устройство, но никто не знает, как его создать.

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

Дэвид Ричерби
источник
Я думаю, что его собственная проблема остановки разрешима любым семейством автоматов, если оно тривиально, то есть либо все они останавливаются, либо ни один из них не делает (что в этом случае может показаться странным).
Бабу
1
@babou: как насчет автоматов, где машина 0 зацикливается вечно, машина 1 выдает FALSE, если ее вход равен 0, иначе выдает TRUE и затем останавливается. Все остальные машины выдают FALSE и затем останавливаются. Это семейство автоматов, в котором программа 1 решает нетривиальную проблему остановки? Или это даже не семейство автоматов из-за отсутствия какого-либо свойства, например, какого-либо состава?
Стив Джессоп
@ SteveJessop Ну, вы (и Дэвис Ричерби), вероятно, правы в некотором смысле. Что меня беспокоит, так это то, что это надуманный пример. Вы создаете очень слабую семью, так что одна машина в семье оказывается решающим фактором для всей семьи. Но, как вы сами подозреваете (см. Ваше замечание о композиции), может быть какое-то базовое свойство замыкания, которое отсутствует, чтобы проблему можно было тривиализировать. У меня нет готового ответа, и я согласен, что мое замечание нуждается в большей квалификации относительно того, что представляет собой семейство автоматов, но ваш контрпример не оставляет меня в этом убежден.
Бабу
3

Предупреждение: философский / не строгий ответ

Это может стать немного «философским», но я думаю, что это соответствует духу вашего вопроса.

Неповторяющаяся машина

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

Удаление свойств

Это немного похоже на переход от теории множеств к теории категорий: вы теряете некоторые «парадоксы», теряя ограничения. Но с результатом гораздо сложнее справиться.

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

stefan.schwetschke
источник
1
Спасибо, эта штука "неповторяющаяся машина" звучит довольно интересно, на самом деле. Я не чувствую себя достаточно компетентным, чтобы с комфортом сказать какую-то мудрость о умных самоинспекционных программах (потому что мой инстинкт инстинкта заключается в том, что они все еще выразимы как машины Тьюринга), но я чувствую, что они вполне могут быть полезны для некоторого набора проблем.
H2CO3
1
Как бы привести пример неповторяемости? Как бы вы определили остановку в этом случае. Основная трудность заключается в том, что, когда вы пытаетесь определить странную вычислительную модель, обычно геданкеновую, вы должны определить смысл остановки и то, какой ввод должен анализировать решающий аппарат, и, возможно, некоторые другие нетривиальные вещи. Смотрите, например, случай недетерминизма . Не говоря уже о проблеме того, что можно считать вычислительной моделью (вероятно, не специальным набором машин).
Бабу
1
@ H2CO3 Неповторяемая машина - это всего лишь своего рода «эксперимент Геданкена», посвященный тому, каким свойством вы должны пожертвовать, чтобы выйти из «общей проблемы остановки» (создание противоречия, позволяя машине осматривать себя). Вы получите машину, которая иногда подходит, но вы не знаете когда. Это как программа, которая рассчитывает номера лотереи на следующую неделю. Я могу легко предоставить вам такую ​​программу. Самое сложное для вас - решить, какая из многих программ, которые я вам предоставлю, является верной ...
stefan.schwetschke
2

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

Принимая во внимание любую конкретную спецификацию «усовершенствованной машины Тьюринга», можно было бы указать «Супер-усовершенствованную машину Тьюринга», которая могла бы проверить программу для ETM и сообщить, остановится ли она, но SETM сможет анализировать программы только для ETM - он не сможет анализировать программы SETM. Нет способа определить машину, которая может анализировать программы для себя и определять, останавливаются ли они, потому что добавление новых функций создаст новые требования для самоанализатора, и нет способа заставить функции «догнать» требования ,

Supercat
источник
1

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

  • Машины с действительными числами (т.е. аналоговые компьютеры)
  • Машинам Тьюринга дается бесконечное время
  • Недетерминированная машина Тьюринга

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

Корт Аммон - Восстановить Монику
источник