Пределы вычислений: физические и теоретические ограничения
Limits of computation
Пределы вычислений: физические ограничения на объём данных и вычислений, связанные с массой, энергией и энтропией. Границы Бekenштейна и термодинамики.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Обзор пределов вычислимости
Overview of the limits of computation
Пределы вычислимости определяются рядом различных факторов. В частности, существуют физические и практические ограничения на объем вычислений или объём хранения данных, который может быть осуществлён при заданном количестве массы, объёма или энергии.
The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be performed with a given amount of mass, volume, or energy.
Плотность обработки и памяти
Граница Бекенштейна ограничивает количество информации, которое можно хранить в сферическом объеме энтропией чёрной дыры с той же площадью поверхности. Термодинамика ограничивает объём хранения данных системы, исходя из её энергии, числа частиц и модальных степеней свободы частиц. На практике это более жёсткое ограничение, чем граница Бекенштейна.
The Bekenstein bound limits the amount of information that can be stored within a spherical volume to the entropy of a black hole with the same surface area. Thermodynamics limit the data storage of a system based on its energy, number of particles and particle modes. In practice, it is a stronger bound than the Bekenstein bound.
Скорость обработки
Лимит Бремермана — это максимальная скорость вычислений самодостаточной системы в материальной Вселенной, обусловленная соотношением между массой-энергией и ограничениями, связанными с принципом неопределённости квантовой механики.
Bremermann's limit is the maximum computational speed of a self contained system in the material universe, and is based on mass–energy versus quantum uncertainty constraints.
Задержки в связи
Теорема Марголуса — Левитина устанавливает предел максимальной вычислительной скорости на единицу энергии: 6 × 1033 операций в секунду на джоуль. Однако этот предел можно обойти, если имеется доступ к квантовой памяти. В этом случае можно разработать вычислительные алгоритмы, требующие сколь угодно малого количества энергии/времени на один элементарный шаг вычислений.
The Margolus–Levitin theorem sets a bound on the maximum computational speed per unit of energy: 6 × 1033 operations per second per joule. This bound, however, can be avoided if there is access to quantum memory. Computational algorithms can then be designed that require arbitrarily small amounts of energy/time per one elementary computation step.
Энергоснабжение
Принцип Ландауэра определяет нижний теоретический предел потребления энергии: kT (энергия), потребляемая при каждом необратимом изменении состояния, где k – постоянная Больцмана, а T – рабочая температура компьютера. Реверсивные вычисления не ограничены этим нижним пределом. Даже теоретически невозможно понизить T ниже 3 кельвинов, приблизительной температуры космического микроволнового фонового излучения, не затратив на охлаждение больше энергии, чем будет сэкономлено при вычислениях. Однако, в масштабе времени от 10⁹ до 10¹⁰ лет, космическое микроволновое фоновое излучение будет экспоненциально уменьшаться, что, по мнению некоторых, в конечном итоге позволит выполнять в 10³⁰ раз больше вычислений на единицу энергии. Важные аспекты этого утверждения подвергаются сомнению.
Landauer's principle defines a lower theoretical limit for energy consumption: [[kT (energy) consumed per irreversible state change, where k is the Boltzmann constant and T is the operating temperature of the computer. Reversible computing is not subject to this lower bound. T cannot, even in theory, be made lower than 3 kelvins, the approximate temperature of the cosmic microwave background radiation, without spending more energy on cooling than is saved in computation. However, on a timescale of 109 – 1010 years, the cosmic microwave background radiation will be decreasing exponentially, which has been argued to eventually enable 1030 as much computations per unit of energy. Important parts of this argument have been disputed.
Абстрактные границы в информатике
В области теоретической информатики часто исследуются вычислимость и сложность вычислительных задач. Теория вычислимости описывает степень, в которой задачи могут быть вычислены, в то время как теория сложности описывает асимптотическую меру потребления ресурсов. Таким образом, вычислительные задачи классифицируются по классам сложности. Арифметическая иерархия и полиномиальная иерархия классифицируют степень вычислимости и вычислимости задач за полиномиальное время соответственно. Например, уровень арифметической иерархии классифицирует вычислимые частичные функции. Более того, эта иерархия является строгой, и любой другой класс в арифметической иерархии содержит строго невычислимые функции.
In the field of theoretical computer science the computability and complexity of computational problems are often sought after. Computability theory describes the degree to which problems are computable, whereas complexity theory describes the asymptotic degree of resource consumption. Computational problems are therefore confined into complexity classes. The arithmetical hierarchy and polynomial hierarchy classify the degree to which problems are respectively computable and computable in polynomial time. For instance, the level of the arithmetical hierarchy classifies computable, partial functions. Moreover, this hierarchy is strict such that at any other class in the arithmetic hierarchy classifies strictly uncomputable functions.
Свободные и жесткие границы
Многие пределы, выведенные на основе физических констант и абстрактных моделей вычислений в информатике, являются нестрогими. Очень немногие известные пределы непосредственно сдерживают передовые технологии, но многие инженерные проблемы в настоящее время нельзя объяснить аналитическими формулами.
Many limits derived in terms of physical constants and abstract models of computation in computer science are loose. Very few known limits directly obstruct leading edge technologies, but many engineering obstacles currently cannot be explained by closed form limits.