Pull to refresh

Предел Бреммермана — невычислимые задачи

Reading time3 min
Views4K


Шутки шутками, но что, если задуматься об объеме такого «жесткого» диска?
В 1964 году Ханс Бреммерман опубликовал статью «Optimization through evolution and recombination», главный вывод который заключается в следующем:

Не существует системы обработки данных, искусственной или естественной, которая бы могла бы обрабатывать более чем 2×10^47 бит в секунду на грамм своей массы.

Масса Земли оценивается примерно в 6×10^27 г, а возраст 10^10 лет, год состоит из приблизительно 3.14×10^7 секунд. Наша воображаемая компьютерная система смогла бы обработать 2,56×10^93 бит, округляя до порядка 10^93 бит.

Задачи, требующие обработки более чем 10^93 бит информации называются трансвычислительными задачами. К сожалению, комбинаторика говорит нам, что что такой предел может быть достигнут для задач даже относительно небольшого размера. Например, в распознавании образов: пусть есть массив q*q, каждый элемент которого может быть раскрашен одним из k цветов, тогда всего вариантов раскраски может быть k^(q*q). Если массив 18×18, то задача трансверсальна при двух цветах, для массива 10×10 становится трансверсальной при 9 цветах. Понятно, что рассмотреть все варианты образов сетчатки глаза, имеющий порядка миллиона светочувствительных колбочек, невозможно. Еще один пример такой задачи — тестирование микросхемы, у которой 308 входов и всего 1 выход.

Наиболее естественный способ решения трансверсальных задач — переформулировка, ослабление условий, вероятностный характер решения. Хочется верить, что все-таки появятся алгоритмы искусственного интеллекта, в частности для решения задачи распознавания образов, которые смогут позволить автоматически решать трансверсальные задачи, подобному тому, как это может делать мозг человека.


Доказательство предела Бреммермана:


Для обработки информация должна быть закодирована. Предположим, что она закодирована в виде энергетических уровней в интервале [0, E]. Пусть энергетические уровни измеряются с точностью до dE. Таким образом на всем интервале будет N = E/dE подинтервалов, каждый из которых может быть занят или нет (1 или 0).
Максимальное число битов будет равно log2 (N+1)

Для того, чтобы представить больший объем информации, необходимо сокращать dE. По принципу неопределенности Гейзенберга энергия может быть измерена с точностью до dE, если выполняется dE*dt >= h, где dt — длительность времени измерения, h = 6.625×10^-27 эрг/с (постоянная Планка)

Получаем, N<= Edt/h
Если представить имеющуюся энергию E соответствующим количеством массы согласно формуле Эйнштейна E = mc^2
N = mc^2*dt/h

Подставив с и h, имеем N = 1.35×10^47*m*dt

Для массы 1 г (m = 1) и времени 1с (dt = 1) получаем указанное значение
N = 2×10^47 бит


P.S. По книге Дж. Клир «Системология.Автоматизация решения системных задач»

______________________
Текст подготовлен в Хабра Редакторе от © SoftCoder.ru
Tags:
Hubs:
Total votes 43: ↑41 and ↓2+39
Comments25

Articles