В отличном ответе член сообщества дал следующий набросок доказательства того, что проблема остановки неразрешима:
Доказательство того, что проблема остановки неразрешима. Если бы существовала вычислимая процедура для надежного определения того, останавливается ли данная программа/ввод, то спроектируйте новую программу q, которая на входе p сначала спрашивает, останавливается ли p на входе p, а затем сама выполняет противоположное поведение. Отсюда следует, что q останавливается на входе q тогда и только тогда, когда это не так, противоречие.
Перейдя по полезной ссылке Махмуда ниже, я нашел замечательную статью того же пользователя по этой теме. Кроме того, запись в Википедии по этой проблеме помогла мне разобраться в этом. (Я также наткнулся на это забавное стихотворение об этой проблеме.) Думаю, я понимаю, каким образом это дает нам «неразрешимые проблемы» для любой машины Тьюринга и как слабая форма теоремы Гёделя о неполноте может быть получена из доказательства того, что проблема неразрешима.
Какие другие, возможно, более общие следствия неразрешимости проблемы остановки могут быть? (В частности, чем они отличаются от теорем Гёделя о неполноте?)
Что касается вашего комментария:
«... один из способов выразить обеспокоенность [в отношении проблемы остановки] - это просто раскрыть, какие могут быть последствия ...»
Можно сказать, что проблема остановки указывает на то, что распаковка следствий логических предложений в принципе проста только в том случае, если вам достаточно повезло, что само предложение имеет простую структуру. В любой логической схеме, которая достаточно сложна, чтобы быть интересной, с конструктивистской точки зрения может даже не существовать факта логических следствий .
Проблема остановки указывает на то, что умных рассуждений, использующих понимание общей картины и понимание структуры логической ситуации, иногда бывает недостаточно. Существует бесконечная иерархия логических проблем, имеющих все более и более тонкую структуру, уходящая к горизонту проблем, о которых едва ли можно сказать, что они вообще имеют структуру; и поэтому для решения этих проблем не существует методов, экономящих время - чтобы найти ответы, нет другого выхода, кроме вычислений грубой силы.
Если вы считаете, что мир достаточно хорошо моделируется логикой, и у вас возникает искушение сказать, что мир «кажется логичным», из этого следует, что, вероятно, существует бесконечная иерархия физических явлений возрастающей сложности до такой степени, что будут непостижимые явления, о которых мы едва ли можем составить какие-либо разумные представления; где, в конце концов, остается только наблюдать, как они разворачиваются со временем.
Одним из следствий неразрешимости проблемы остановки может быть то, что она предполагает ограничения нашей способности знать некоторые концептуальные истины априори. Посмотрите эту статью Мартинеса, чтобы узнать, как это может выглядеть.
Я обнаруживаю небольшое замешательство в отношении того, в чем именно заключается проблема с остановкой.
Неправильно говорить, что проблема остановки неразрешима, как в «доказательстве того, что проблема остановки неразрешима». Проблема остановки была решена доказательством Тьюринга, что такого алгоритма не может существовать. Используя свои собственные обозначения, Тьюринг показал, что независимо от того, какое «p» вы выберете, всегда будет «q», для которого «p» не может решить, остановится ли «q». Неразрешимым является статус конкретного случая "q", а не сама проблема остановки.
Это мой первый день на PSE, и я надеюсь, что это не прозвучало язвительно. Это не должно было быть.
С точки зрения общего философского значения результата Тьюринга, на одном уровне кажется, что некоторые вещи (в арифметике) истинны просто потому, что они истинны, а не без «логической» причины. На другом уровне результат Тьюринга, кажется, поддерживает мнение о том, что истина может быть относительной, а не абсолютной.
То, что вы, вероятно, имели в виду, — это Святой Грааль всей математики и философии, TOE или Теория всего , предложенная Максом Тегмарком. Грегори Чайтин, который в своем видео на YouTube резюмирует, что структурой математики является случайность, также заключает в своей статье «Лейбниц, случайность и вероятность остановки », что математическое сообщество может двигаться в «квазиэмпирическом» направлении. По его словам:
Во всяком случае, мне так все кажется. Возможно, к тому времени, когда мы достигнем столетия со дня смерти Тьюринга, эта квазиэмпирическая точка зрения продвинется вперед, или, возможно, вместо этого эти чуждые идеи будут полностью отвергнуты иммунной системой математического сообщества. На данный момент они, безусловно, отвергнуты. Но прошедшие пятьдесят лет преподнесли нам много сюрпризов, и я ожидаю, что следующие пятьдесят лет тоже принесут немало сюрпризов.
Конечно, если не будет TOE и математика станет искусством науки «квазиэмпиризма», то известные открытые проблемы, такие как гипотеза Римана или Гольдбах, могут оказаться недоказуемыми. Чайтин заключает здесь :
Возможно, вместо того, чтобы пытаться доказать такие результаты, как знаменитая гипотеза Римана, математикам следует признать, что они могут быть недоказуемы, и просто принять их как аксиому.
Согласно Википедии, Роджер Пенроуз использовал проблему остановки, чтобы доказать, что человеческий разум нельзя смоделировать с помощью алгоритма (я еще не нашел исходного аргумента).
Роджер Пенроуз «возражает против точки зрения, что рациональные процессы разума полностью алгоритмичны и, таким образом, могут быть продублированы достаточно сложным компьютером. Это контрастирует со сторонниками сильного искусственного интеллекта, которые утверждают, что мысль может быть смоделирована алгоритмически. Он основывает это на утверждает, что сознание выходит за рамки формальной логики, потому что такие вещи, как неразрешимость проблемы остановки и теорема Гёделя о неполноте, не позволяют основанной на алгоритмах системе логики воспроизводить такие черты человеческого интеллекта, как математическое понимание».
Снайпер Клоун
Джозеф Вайсман
нвр
Скотт Роу