Я понимаю, что полнота Тьюринга требует неограниченной памяти и неограниченного времени.
Однако в этом сервисе существует ограниченное количество атомов, что ограничивает память. Например, даже если иррационально, нет способа сохранить более определенного числа цифр, даже если все атомы во вселенной были использованы для этой цели.
Каковы же тогда пределы вычислимости реализованной машины Тьюринга (которая могла бы использовать все ресурсы вселенной, но не более), основанной на пределах вселенной? Каково максимальное количество цифр ? Есть ли какие-либо статьи на эту тему, которые могут быть интересны для чтения?
computability
upper-bounds
Хороший человек
источник
источник
Ответы:
У Сета Ллойда есть статья на эту тему. Вам нужна энергия для вычисления, но если вы поместите слишком много энергии в небольшую область, она образует черную дыру. Это замедляет время (делая время, необходимое для того, чтобы вычисления выполнялись относительно дольше), и любые вычисления, выполненные внутри черной дыры, теряются, поскольку результаты не могут быть извлечены из черной дыры и использованы. Сет вычисляет пределы возможного объема вычислений и показывает, что для некоторых показателей вычислений наиболее интенсивной вычислительной средой, возможной во вселенной, будет среда вокруг черной дыры.
источник