А.Я. Бекшаев Физические основы ЭВМ Лекции для студентов 4-го курса физического факультета ОНУ, Специализация "Компьютерная физика" 2007 – 2009

Информация как физическая реальность Термодинамика вычислений Информация: знание некоторых характеристик физической системы. Физическая система объективно характеризуется значениями координат, скоростей, масс, температур, электрических и магнитных полей, и т.д. всех ее составляющих. Но есть еще и внешний по отношению к системе наблюдатель (познающий субъект), который может иметь или не иметь знание об этих величинах. Оказывается, объективное описание системы недостаточно. Мы должны явно или неявно учитывать присутствие наблюдателя и его возможности. Принципиальное ограничение объема доступных знаний о системе определяет фундаментальные законы ее поведения. Статистическая термодинамика Теория когерентности в оптике Теория относительности Квантовая механика Определение Вселенной (ФЭ, 1988): окружающая часть материального мира, доступная наблюдению.

Информация кодируется состояниями некоторых "стандартных" физических систем, "приспособленных" для этой цели (носителей): чернила на бумаге; электромагнитное, звуковое и т.д. поле; костяшки на счетах; положение стрелки; проницаемость мембран в нейронах; электрический потенциал; намагниченность; пропускание (отражение) света; и т.д. Если информация кодируется непрерывным процессом (величина – носитель может принимать непрерывный ряд значений), то представление называется аналоговым Если носитель принимает дискретный ряд значений, то представление называется дискретным, или цифровым Представление информации – кодирование Содержание информации не должно зависеть от специфики носителя.

Каждый носитель является физическим объектом и подчиняется общим законам физики. Эти законы определяют реальное поведение и возможности любых информационных устройств: от человеческого мозга… до искусственного мозга, в т.ч. компьютеров Двойственнная "физичность" информации: она отражает свойства физической системы (объекта) + сама выражается через состояние физической системы (носителя) Обработка информации подчиняется общим законам, вытекающим из самой природы носителей как физических систем Информация, как совокупность знаний о физическом объекте и как состояние некоторой физической системы, является элементом физической реальности. Физические свойства каждого конкретного носителя накладывают свои дополнительные требования, которые определяют особенности работы конкретных систем

МЕРА ИНФОРМАЦИИ Элементарный выбор: из двух равновероятных возможностей (дихотомия). Нет информации: незнание Набор возможностей, между которыми можно выбирать. Неопределенность Есть информация: знание Выбор из набора возможностей совершен. Определенность Знание, полученное в результате элементарного выбора – одна двоичная единица информации (binary unit = bit) В общем случае: определить какую-либо величину значит указать способ ее измерения. Количество информации можно определить, указав способ устранения начальной неопределенности. Его всегда можно свести к последовательности элементарных выборов между двумя возможностями. Последовательность вопросов, на которые можно ответить "да" или "нет" Наименьшее количество таких вопросов – мера извлекаемой информации Извлечение информации: выбор из набора возможностей. Простейшая информационная ячейка: бинарный элемент

Пример Нужная ячейка находится за два шага В случае N = 2 n ячеек потребуется n = log 2 N шагов Если N 2 n, 2 n–1 < N < 2 n число шагов может быть то n – 1, то n; в среднем log 2 N Если две возможности не равновероятны, то иногда можно угадать результат и без всякого измерения, просто указывая на более вероятную ячейку. Среднее число шагов < 1 Левая ячейка с вероятностью p 1, правая p 2 = 1 – p 1 :n = –(p 1 log 2 p 1 + p 2 log 2 p 2 ) Общий случай: количество информации по Шеннону При p i = 1/N

Любая информация может быть представлена в виде совокупности состояний бинарных элементов: иначе говоря, нулей и единиц Физическая реализация бинарных элементов: любая система с двумя устойчивыми состояниями Пример: числовая информацияa a a … + a n–1 2 n–-1 = {a n–1 a n–2 … a 1 a 0 } n разрядов 5 = = {101} Потенциальная энергия Модель: потенциальные барьеры = стенки Рассмотрим на примерах общие закономерности процессов обработки информации Основные операции: запись (копирование) и стирание молекула

Копирование (запись) Копируемая ячейка (оригинал) Заготовка для копии (пустая ячейка) Частица движется бесконечно медленно (обратимо) Начинает испытывать силу (например, дипольную) Состояние ячейки скопировано Закрепление: восстанавливаются перегородки Все поля консервативны: суммарная работа всех сил равна нулю Копирование информации всегда возможно; оно может происходить без диссипации энергии и без возрастания энтропии Трение пропорционально скорости и может быть произвольно слабым Копирование = измерение. Измерение также всегда возможно и может происходить бездиссипативно (обратимо) Важное условие : заготовка для копии пустая (не требуется стирать ранее записанную информацию).

Копирование (запись)

Стирание Битовая ячейка в одном из двух состояний 10 Удаляется перегородка, вставляется поршень Поршень сдвигается так, что независимо от начального состояния молекула оказывается в левой половине ( 0 ) Перегородка восстанавливается Узнать, где была молекула раньше, невозможно Информация потеряна! В процессе стирания поршень совершает работу; в изотермическом процессе E = kT ln(V 1 /V 2 ) = kT ln2 Соответствующее количество теплоты передается окружению Энтропия окружающей среды возрастает на S = E/T = k ln2 Энтропия однобитовой ячейки уменьшается на ту же величину S = E/T = k ln2

Принцип Ландауэра Замечание 1 (теоретическое). Принцип Ландауэра связывает информацию с физическими концепциями энергии и энтропии. Замечание 2 (практическое). Хотя в реальности затраты энергии на элементарные операции намного больше ландауэровского предела ( –21 Дж = эВ при 300 К), принцип подсказывает возможные пути и пределы минимизации энергопотребления компьютеров Замечание 3. Принцип есть следствие логической необратимости стирания. Аналогичные выводы справедливы и в отношении других логически необратимых операций, например, И, ИЛИ: диссипация энергии составляет kT ln2 на каждый потерянный бит Стирание одного бита информации сопровождается затратой по крайней мере kT ln2 = 0.693kT энергии и увеличением энтропии окружающей среды на k ln2 = –23 Дж/К. Эти количества не могут быть уменьшены, какие бы способы кодирования и стирания информации ни применялись ВходВыход На входе: 4 равновероятных возможности I in = 2 бита На выходе: 0 с вероятностью ¾ и 1 с вероятностью ¼ I out = – (¾)log 2 (¾) – (¼)log 2 (¼) = = – (¾)log (¾) log (¼)log 2 4 = – (¾)log E = kT ln2 (I in – I out ) = kT ln2(¾)log 2 3 = kT Потерянная информация (I in – I out ) = (¾)log 2 3 = бит

Принцип Ландауэра и демон Максвелла Ящик с "одномолекулярным" газом Демон (Д) – интеллектуальное устройство, способное измерять, хранить и использовать информацию Сначала положение молекулы неизвестно. В зависимости от результата измерения, Д размещает в ящике поршень с грузом таким образом, чтобы удары молекулы его поднимали "Газ" расширяется и совершает работу. После того, как поршень сдвинулся и груз был поднят, его удаляют. Система вернулась к исходному состоянию… и совершена работа за счет теплового резервуара при постоянной температуре Нарушено второе начало термодинамики? Упущено: Д, точнее, его память. В памяти осталась информация о состоянии ячейки, которой в начале цикла не было. Вернуть к исходному состоянию – стереть информацию:затратить энергию kT ln2 Д ставит перегородку, делящую ящик пополам, и определяет, в какой половине находится молекула При постоянной температуре A = kT ln(V 2 /V 1 ) = kT ln2 М

Информация оказалась включенной в общее описание состояния системы наравне с ее физическими параметрами: это тоже физическая характеристика, а не просто математическая концепция Одна и та же система имеет различные физические свойства в зависимости от имеющейся информации (в одном случае она способна совершить работу, в другом – нет) Устройства хранения информации ("память демона") – физические объекты и должны рассматриваться в одном контексте с "явными" объектами системы Введенная мера информации оказывается согласованной с общефизическими понятиями энергии и энтропии Обращение принципа Ландауэра: любая неслучайная комбинация битов может быть использована для производства работы за счет рандомизации (адиабатическое размагничивание, … ) Демон Максвелла, гипотетическое "всемогущее" устройство, способное различать и сортировать молекулы газа, было придумано на заре статистической физики для демонстрации пределов применимости второго начала. Оказывается, включение его "памяти" в состав системы "спасает" второе начало термодинамики от нарушения даже в случае "интеллектуального" вмешательства в систему

Информационная энтропия Возможен и другой подход: не включать память "демона" явно в состав сиcтемы, но учесть "знание" о системе в описании ее состояния. Произведенная механическая работа A = kT ln2= Q = T S Полученное от резервуара количество теплоты Изменение обычной термодинамической энтропии ячейки Работа, затраченная на стирание информации A e = – kT ln2 Полная совершенная в процессе работа A + A e = T S – kT ln2= T S g S g = S – k ln2 = 0 Можно сохранить обычное выражение второго закона термодинамики (T S 0 в замкнутом цикле), если ввести эффективную энтропию системы S g = S – k ln2 = (S + S i ) S – обычная термодинамическая энтропия, зависящая только от ее состояния S i зависит от того, что знает о системе наблюдатель: информационная энтропия S i = – k ln2 (на один бит) В общем случае, если есть I бит информации: S i = – I k ln2 Наличие информации о системе может быть учтено, если "подправить" значение ее энтропии.

В определении энтропии как суммы термодинамической и информационной еще раз подчеркивается физическое значение информации. Оказывается, если мы имеем два физически тождественных состояния системы, но в одном случае мы ничего не знаем о ее состоянии, а во втором имеем какую- то информацию, то эти состояния различаются фундаментально. В одном случае мы можем получить работу, в другом – нет! Информация материальна : всегда связана с физическими объектами (носителями) Материя информационна : знания о системе придают ей дополнительные свойства. Через информационную энтропию информация напрямую включается в формулировку второго начала термодинамики. По некоторым предположениям, объективные характеристики физического мира неразрывно связаны с существованием наблюдателя ( антропный принцип )

Информационная энтропия S i = – I kln2 отличается от количества информации I только множителем – kln2 Фактически это одна и та же величина, но измеренная в других единицах. По Больцману S = – k p i lnp i = kln2 (– p i log 2 p i ) = kln2 I T количество "отсутствующей" информации о термодинамическом состоянии (то, что можно было бы извлечь, если знать состояние точно) Отличие в знаке. Информация о системе уменьшает ее энтропию. Обычная энтропия есть мера нашего незнания точного микросостояния системы Система может совершать работу, если ее энтропия не максимальна. Информация меньше энтропия больше возможности совершать работу Взаимосвязь энтропии и информации За каждый бит можно получить до kTln2 полезной работы

Обратимые вычисления В любом реальном случае диссипация энергии значительно превышает предел Ландауэра. Однако при дальнейшем уменьшении размеров и энергопотребления теоретически неизбежная диссипация начинает влиять все сильнее. Выход: логически обратимый компьютер? Вариант: запоминать все промежуточные результаты в специальном ЗУ. Неудобно, требуется много лишней памяти, проблема не решается, а только откладывается. Важность физической необратимости: она позволяет нивелировать небольшие ошибки (если |1 - это 5 В, то 4.5 или 5.6 В тоже |1 ). Тем не менее, полезно иметь возможность снизить диссипацию до произвольно малого уровня и не зависеть от термодинамических ограничений. Логически обратимые операции важны и для квантового компьютера, потому что в квантовой механике возможны только обратимые операции. Это привело к поиску логически обратимых алгоритмов. Квантовый, баллистический, брауновский компьютер Обычные алгоритмы широко используют необратимые операции (например, И, ИЛИ, стирание…). С каждой такой операцией связана диссипация энергии. Можно ли создать компьютер без необратимых операций? Нужно ли это делать?

Обратимые вентили Вентили – это устройства, которые выполняют заданные операции над логическими (бинарными) данными Другое название – логические элементы: И, ИЛИ, НЕ, … Из обычных операций обратимы только отрицание (НЕ) и исключительное ИЛИ (XOR). Но они не образуют полного набора. Надо ввести еще хотя бы один стандартный элемент, например Toffoli gate (вентиль Тоффоли, 1980). INPUT OUTPUT битовый вход и выход, если 2 первых бита оба равны 1, то третий бит инвертируется. выход = вход (тождество) 3-й бит инвертируется Эта 2-битовая операция «встроена» в 3-битовую. Можно считать, что «лишние» входы и выходы обеспечивают логическую обратимость. Когда третий вход = 0, между двумя первыми входами и третьим выходом реализуется И Число входов = числу выходов

Этот вентиль может быть моделирован биллиардными шарами (баллистический компьютер). Входные шары влетают одновременно слева, сталкиваются с «зеркалами» и друг с другом. Механическая обратимость движения шаров соответствует логической обратимости. Входные данные являются частью выходных, два различающихся бита кодируют операцию. Динамическая нестабильность: малейшие возмущения "уводят" компьютер от заданной программы (система шаров становится хаотической). Хаотизация : основной недостаток классических обратимых компьютеров. Можно восстанавливать "правильные" сигналы, но это сопряжено с диссипацией. Иначе – хаотизация. Можно ли ее использовать? x x, f(x) x f(x)f(x)

В нормальных условиях редупликация ДНК идет со скоростью около 30 нуклеотидов в секунду, на каждый шаг тратится ~20kT, вероятность ошибки < В условиях близких к равновесию (11 шагов вперед и 10 назад диссипация kT ln(11/10) ~ 0.1kT на нуклеотид). Брауновский компьютер Тепловой шум влияет настолько сильно, что все движения похожи на случайные блуждания. Траектории удерживаются в желаемых пределах потенциальными барьерами, дрейф в требуемом направлении обеспечивается «движущей силой» (в термодинамическом смысле). Мера движущей силы – высвобождаемая энергия, т.е. диссипация: Вероятность шага вперед Вероятность шага назад Примеры в биохимии (обратимые реакции). Барьеры в несколько kT преодолеваются в ходе проб и ошибок, барьеры ~100kT (covalent bond) предотвращают нежелательные реакции.

Если у текущего состояния есть m «предшественников», вероятность обратного шага возрастает в m раз: Вероятность шага вперед Вероятность шага назад Для того, чтобы процесс продвигался, необходимо > kTlnm. Чаще всего m = 2. Это еще одно обоснование принципа Ландауэра: Может ли брауновский компьютер выполнять необратимые операции? Диссипация энергии при логически необратимых операциях гарантирует, что процесс вычислений идет в нужном направлении Необратимость возникает при ветвящихся процессах: В точках ветвления движущая сила должна быть достаточно большой