Предел Бремермана

Для решения системной задачи данные о системе объекта необходимо физически закодировать. Общим способом кодирования данных является их представление в виде энергетических уровней величиной ΔЕ энергии решения системной задачи данные о системе объекта Е, которой мы располагаем. Число энергетических уровней согласно принципу в этом случае будет равно N = E/ΔE. Максимальное число физически разрешимых уровней для заданного количества энергии определяется неопределенности Гейзенберга. Согласно этого принципа величина уровня должна удовлетворять условию ΔE•Δt ≥ h, где Δt — длительность интервала наблюдения h = 6•6,25•10^-27 эрг/c — постоянная Планка. Из этого следует:

N ≥ E•Δt/h

Тогда с учетом формулы Энштейна Е = mc₂ (где с = 3•10¹⁰ см/c — скорость света, m — количество массы), получим:

N = mc₂•Δt/h

Отсюда следует, что измеритель массой 1 г за время 1 сек может обработать не более N = 1,36•10⁴⁷ бит данных.

Представим гипотетический измеритель массой равной массе Земли m = 6•1027 г. Этот измеритель за время равное времени существования Земли q 10 лет смог бы обработать порядка 10⁹³ бит данных. Это число обычно называют пределом Бреммермана.

Вычислительная сложность задачи

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

Разбор этих вопросов выходит за пределы нашего предмета и рассматривается в общей теории алгоритмов.