Каковы пределы вычислений в этой вселенной?

17

Я понимаю, что полнота Тьюринга требует неограниченной памяти и неограниченного времени.

Однако в этом сервисе существует ограниченное количество атомов, что ограничивает память. Например, даже если иррационально, нет способа сохранить более определенного числа цифр, даже если все атомы во вселенной были использованы для этой цели.π

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

Хороший человек
источник
7
На это есть забавное эссе Скотта Ааронсона: scottaaronson.com/writings/finite.html
Артем Казнатчеев
2
Вас может заинтересовать обсуждение этого вопроса . Ярослоав Булатов разместил ссылку на научно-популярную версию газеты Ллойда «Питер Шор», на которую ссылается ниже, но, к сожалению, ссылка сейчас, похоже, не работает. Я читал эту статью в то время, но не сохранил ее и не помню точное название.
Аарон Стерлинг

Ответы:

34

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

Питер Шор
источник
10
@AaronRoth Я застрял в черной дыре. Принят сейчас.
Хороший человек