Существуют релятивистские пространства-времени (например, пространства-времени МГ; см. Хогарт, 1994), где мировая линия бесконечной длительности может содержаться в прошлом конечного наблюдателя. Это означает, что обычный наблюдатель может иметь доступ к бесконечному количеству вычислительных шагов.
Предполагая, что компьютер может функционировать идеально в течение бесконечного промежутка времени (и я знаю, что это большая проблема): можно построить компьютерный HM, который путешествует по этой бесконечной мировой линии, вычисляя проблему остановки для данного M. Если M останавливается , HM посылает сигнал конечному наблюдателю. Если после бесконечного числа шагов наблюдатель не получает сигнал, он знает, что M зацикливается, решая проблему остановки.
Пока это звучит нормально для меня. Мой вопрос: если то, что я сказал до сих пор, верно, как это меняет доказательство Тьюринга, что проблема остановки неразрешима? Почему его доказательство терпит неудачу в этих промежутках времени ?
Ответы:
Обратите внимание, что доказательство Тьюринга принадлежит математике, а не физике. В рамках модели машины Тьюринга, определенной Тьюрингом, неразрешимость проблемы остановки была доказана и является математическим фактом. Следовательно, доказательство Тьюринга не «провалится» в пространстве-времени, оно просто не докажет ничего о связи проблемы остановки и замедления времени.
Однако, вероятно, вы захотите узнать, может ли «машина Тьюринга с замедлением времени» решить проблему остановки.
Если вы хотите изучить влияние «замедления времени» на машине Тьюринга, вам придется указать формальную модель, с помощью которой мы можем формально понять, что означает, что машина Тьюринга использует замедление времени. К сожалению, этот формат не подходит для предоставления такой формальной модели (если кто-то еще не написал статью об этом), поскольку создание модели слишком широкое.
Тем не менее, не исключено, что некоторая формализация действительно способна решить проблему остановки. В этой статье Скотта Ааронсона, Мохаммада Баварского и Джулио Гельтрини рассматриваются вычислительные модели в предположении, что существуют так называемые замкнутые временные циклы, и делается вывод о том, что проблема остановки действительно вычислима внутри этой модели.
источник
Машина Тьюринга - это формальная математическая модель вычислений, она не отвечает никаким физическим ограничениям и не заботится о релятивистских эффектах. Это означает, что доказательство Тьюринга не является ошибочным, поскольку стандартное определение машины Тьюринга даже не содержит понятия «пространство-время».
Что вы можете попытаться сделать, так это определить другую модель вычислений, основанную на теории относительности. Опять же, это будет только формальный объект, и вопрос о том, может ли он решить проблему остановки, относится к области математики и зависит от вашего конкретного определения. Однако настоящий вопрос сейчас заключается в том, действительно ли эта новая модель правильно отражает релятивистские эффекты, то есть действительно ли она отражает нашу физику и может быть реализована в нашем мире?
Вы можете увидеть такую дискуссию о квантовых вычислениях. У нас есть формальное определение «квантовых машин Тьюринга», и их точная вычислительная мощность остается открытой проблемой в математике (хотя даже близко к проблеме остановки). Тем не менее, вы можете утверждать, что это определение на самом деле не отражает наше понимание квантовой физики, и необходимо лучшее. Есть аргументы , свидетельствующие о том, что такие машины невозможно построить, поэтому их точная мощность не влияет на (сильный) тезис Черча-Тьюринга.
Вернемся к вашему вопросу. Существует формальное представление о бесконечной машине Тьюринга , но для того, чтобы она имела какое-либо влияние на тезис Черча-Тьюринга, вам нужно, чтобы она существовала на практике. Возможно, вас заинтересует статья Скотта , в которой есть раздел о вычислениях с использованием релятивистских эффектов, хотя кажется, что наивные аргументы бесперспективны (в том смысле, что они непрактичны, поскольку затраты времени заменяются затратами на энергию).
источник
Доказательство Тьюринга показывает, что ни одна машина Тьюринга не может решить проблему остановки, независимо от того, сколько времени вы ей уделяете. Если ваш космический корабль использовал замедление времени, чтобы дать компьютеру миллиард лет на работу, он все равно не сможет сказать вам что-то более определенное, чем «Пока нет».
Очевидно, (спасибо, @DiscreteLizard!), Если у вас есть путешествие во времени, которое не может вызвать парадоксы, вы можете настроить цикл времени , который вызовет парадокс, если компьютер не сможет доказать, останавливается ли машина Тьюринга. Либо он получает ответ из будущего и передает его обратно себе, либо он работает вечно (и, ловко, возвращает квантовую суперпозицию, которая преобразуется в устойчивый цикл времени). Но, прежде чем пытаться это сделать, убедитесь, что безопасно вызывать парадокс путешествий во времени.
источник
Возражение состоит в том, что вы определили процесс, который может производить бесконечную энтропию в компактной области, и, похоже, это происходит в конечном отрезке прошлого наблюдателя. Это означает несколько вещей
Это интересный открытый вопрос, применимы ли и как эти ограничения к квантовым компьютерам. Вполне может быть, что сложность вычислений, выполняемых квантовым компьютером, ограничена площадью поверхности компьютера. Поэтому нам, возможно, придется удвоить площадь поверхности экстремального квантового компьютера, чтобы получить еще один полезный кубит вычислений. Это быстро приводит к непрактично большим компьютерам.
источник
Цитата из челки, хруста, хныканья и вопля:
источник