Машина Тьюринга + замедление времени = решить проблему остановки?

15

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

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

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

маргаритка
источник
Может быть актуально: researchgate.net/publication/… .
Мартин-Блас Перес Пинилья
1
Будет ли наблюдатель с бесконечной продолжительностью иметь доступ к бесконечной энергии для выполнения своих бесконечных вычислительных шагов? (альтернативно, можно ли сформулировать тестер проблемы остановки обратимым образом? Я бы так не думал)
user253751
Определенно отношение: chiark.greenend.org.uk/~sgtatham/infinity.html
Жюль
@immibis: Да, это так! Я изучал это в колледже.
Иисус Навин
Обратите внимание, что распространенным заблуждением является то, что машина Тьюринга, которая не останавливается, должна «зацикливаться». Это подразумевает некое повторяющееся состояние или повторение одного и того же. Фактически мы можем точно сказать, имеет ли машина такое поведение или останавливается, если он выполняет одно из двух. Беспокойные машины, которые нас запутывают, - это не петлевые, а хаотично вращающиеся, почти случайные модели, не поддающиеся чувству регулярности.
exfret

Ответы:

26

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

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

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

Тем не менее, не исключено, что некоторая формализация действительно способна решить проблему остановки. В этой статье Скотта Ааронсона, Мохаммада Баварского и Джулио Гельтрини рассматриваются вычислительные модели в предположении, что существуют так называемые замкнутые временные циклы, и делается вывод о том, что проблема остановки действительно вычислима внутри этой модели.

Дискретная ящерица
источник
4
Возможно, также полезным является то, что формализм «гипертурирующей машины» как машины Туронга, которая может выполнять бесконечное число шагов за конечное время, действительно является обычным формализмом. Вы можете найти много полезного материала там.
Cort Ammon - Восстановить Монику
10

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

Что вы можете попытаться сделать, так это определить другую модель вычислений, основанную на теории относительности. Опять же, это будет только формальный объект, и вопрос о том, может ли он решить проблему остановки, относится к области математики и зависит от вашего конкретного определения. Однако настоящий вопрос сейчас заключается в том, действительно ли эта новая модель правильно отражает релятивистские эффекты, то есть действительно ли она отражает нашу физику и может быть реализована в нашем мире?

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

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

Ariel
источник
1
Число рейнольдса «... чтобы это имело какое-либо влияние на тезис Черча-Тьюринга, нужно, чтобы оно существовало на практике». - разве машины Тьюринга не являются идеализированными машинами, которые не могут существовать на практике?
Маргаритка
1
На самом деле, это только отражает (или, по крайней мере, пытается) нашу интуицию относительно того, что такое «вычислительная машина». Вот почему тезис Черча-Тьюринга - это тезис, а не математическая теорема. Это только неофициально утверждает, что машины Тьюринга отражают истинную вычислительную мощь, которая существует в нашем мире.
Ариэль
Моя точка зрения такова: почему на практике должна существовать машина Тьюринга с бесконечным временем, чтобы она могла оказывать какое-либо влияние на СТТ, если на практике стандартных машин Тьюринга также не существует?
маргаритка
1
Одна из формулировок тезиса Черча-Тьюринга заключается в следующем: каждая возможная вычислительная модель, реализуемая в нашем мире, не превосходит мощность машины Тьюринга. Сам тезис определяется относительно некоторой наземной модели (а именно, машины Тьюринга).
Ариэль
Я задал дополнительный вопрос, потому что даже после просмотра опубликованных слайдов я не совсем понимаю утверждение, что практическая квантовая машина Тьюринга не может быть построена. (2-й раз, чтобы оставить этот комментарий, теперь указывает на QC.SE вместо CS.SE)
BurnsBA
7

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

Очевидно, (спасибо, @DiscreteLizard!), Если у вас есть путешествие во времени, которое не может вызвать парадоксы, вы можете настроить цикл времени , который вызовет парадокс, если компьютер не сможет доказать, останавливается ли машина Тьюринга. Либо он получает ответ из будущего и передает его обратно себе, либо он работает вечно (и, ловко, возвращает квантовую суперпозицию, которая преобразуется в устойчивый цикл времени). Но, прежде чем пытаться это сделать, убедитесь, что безопасно вызывать парадокс путешествий во времени.

Davislor
источник
2
«Для содержательного ответа пока недостаточно данных».
Роберт Колумбия
Обратите внимание, что главная причина, по которой я упомянул машины Тьюринга в замкнутых временных циклах, заключается в том, что существует некоторая «физическая модификация» модели машины Тьюринга, так что проблема остановки вычисляется этой машиной. Кажется, что другие знают о замедлении времени больше, чем я, но этот пример заставляет меня хотя бы колебаться делать такие заявления, если не дано формализация замедления времени.
Дискретная ящерица
@Discretelizard Это был большой вклад в обсуждение. Я не уверен, что полностью понимаю намерения ОП, но релятивистское замедление времени - реальная концепция в современной физике, и я ответил, что он использовал стандартное определение термина.
Дэвислор
@Davislor Конечно, замедление времени хорошо определено в физике . Машина Тьюринга - это математический объект. Насколько я знаю, лучшее, что мы можем сделать, чтобы объединить их, - это создать «физическую аналогию» машины Тьюринга и формально показать, как она взаимодействует с замедлением времени. Это (пример) того, что я имею в виду под «формализацией». Я не думаю, что существует уникальный способ формализовать это и что результаты могут отличаться, поэтому я не решаюсь говорить что-либо убедительное об этом.
Дискретная ящерица
Тем не менее, вполне возможно, что ответ «нет» для любой разумной формализации, но такое утверждение , по крайней мере, не в моей компетенции.
Дискретная ящерица
5

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

  • Вычислительная энтропия в компактной области превышает Бекенштейнасвязана с энтропией (эта граница пропорциональна площади поверхности региона), поэтому она коллапсирует в черную дыру (мгновенно), и никакой сигнал не может достичь вас изнутри. (Метрика Керра описывает пространство-время МЗ. Наблюдается, что бесконечный процесс завершается только по мере того, как наблюдатель переходит во внутренний горизонт событий. Несмотря на текущую неопределенность относительно физики такого перехода, ни один удаленный наблюдатель никогда не имеет доступа к результату вычисления - результат имеет только наблюдатель, исчезнувший в черной дыре. Это не описание полезного вычислительного процесса. Перефразируя: «У нас есть оракул, который дает правильный ответ на любой вопрос, который вы задаете в постоянном времени в такой ситуации. таким образом, что ответ существует только в тот момент, когда он уничтожается путем промывки черной дыры. ")
  • Машина Тьюринга уничтожает информацию каждый раз, когда она перезаписывает символ на ленте, поэтому по принципу Ландауэра должно наблюдаться конечное вычисление бесконечной мировой линии, сжатой в конечный отрезок в прошлом световом конусе наблюдения, чтобы требовать бесконечной мощности и излучения бесконечное тепло в течение бесконечно малого времени, в течение которого оно работает. То есть, поскольку останов достигается за конечное время, он достигается мгновенно с точки зрения внешнего наблюдателя, поэтому вся мощность потребляется мгновенно, а все тепло выделяется мгновенно. Альтернативно, если вычисление не останавливается, компактная область постоянно потребляет бесконечную мощность и излучает бесконечное тепло. Чистый результат: опять черная дыра.
  • Альтернативно, принцип Ландауэра не распространяется на обратимым вычислениям и там есть ( универсальные ) обратимые машины Тьюринга . Тем не менее, такая машина Тьюринга требует способности представлять все пространство потенциальных вычислительных состояний, которое экспоненциально по размеру количества используемой ленты, поэтому быстро сталкивается с границей Бекенштейна. В итоге мы можем избежать проблемы с нагревом, только ограничившись лентами ограниченной длины. Эквивалентно, мы имеем верхнюю границу полезной длины ленты, контролируемой областью поверхности, которая имеет бесконечную мировую линию. Если вы не учитываете это и ваши вычисления используют слишком много ленты, вы снова получаете черную дыру.

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

Эрик Тауэрс
источник
1

Цитата из челки, хруста, хныканья и вопля:

Лампы Томсона, супер πмашины и платонистские компьютеры - игрушки философов; они способны выжить только в тепличной атмосфере философских журналов. В конце концов, пространства М-Н и суперзадачи, которые они выполняют, могут также оказаться развлекательными вымыслами для общих релятивистов, которым нечего делать. Но для того, чтобы прийти к этой последней позиции, необходимо сначала решить некоторые из самых глубоких фундаментальных проблем классической общей теории относительности, включая природу особенностей и судьбу космической цензуры. Именно эта связь с реальными проблемами в физике делает их достойными обсуждения.
Есть также связи с философией математики и теорией вычислимости. Некоторые философы сомневаются в том, что из-за финитских сомнений целесообразно присвоить значение истинности формуле арифметики вида(Икс1)(Икс2)...(ИксN)F(ИксL,Икс2,...,ИксN), Мне кажется непривлекательным ставить истинность математических утверждений в зависимость от непредвиденных обстоятельств структуры пространства-времени. Рассмотренные выше виды схем могут быть использованы для определения истинности значений арифметики с преднормальной формой, которая является чисто экзистенциальной или чисто универсальной. (Последняя теорема Ферма, например, имеет чисто универсальный вид.) Для такого утвержденияγ1 настроен на работу для проверки (бесконечно бесконечного) списка N- наборы чисел в поисках фальсификатора или верификатора в зависимости от того, является ли проверяемое утверждение универсальным или экзистенциальным, и γ1извлекает из этих трудов знание истинного значения утверждения. Но как только смешанные квантификаторы задействованы, метод не работает. Однако Хогарт (1994) показал, как в принципе можно использовать более сложные схемы в общих релятивистских пространствах-временах для проверки истинности любого арифметического утверждения произвольной количественной сложности. В таком пространстве и времени трудно понять, как сохранить позицию, при которой у нас нет четкого представления об истине в арифметике.
Мартин-Блас Перес Пинилья
источник