Nеорема о бесконечных обезьянах
Материал из Википедии — свободной энциклопедии


Текст теоремы о бесконечных обезьянах звучит (в одном из многих вариантов) так: «Если вы посадите бесконечное количество обезьян печатать на пишущих машинках, то одна из них обязательно напечатает какое-либо произведение Вильяма Шекспира». Существуют вариации теоремы с ограниченным количеством обезьян и бесконечным временем, по сути, являющиеся той же самой теоремой, так как на выходе получается бесконечное количество обезьяно-часов.
Если перенести данные рассуждения в обозримый масштаб, то теорема будет гласить — если в течение продолжительного времени случайным образом[1] стучать по клавиатуре, то среди набираемого текста будут возникать осмысленные слова, словосочетания и даже предложения.
Эта теорема не объясняет ничего относительно интеллекта конкретной случайной обезьяны, которой посчастливится набить правильный текст. Нет никакой необходимости в обезьянах и пишущих машинках, эксперимент может быть реализован, например, подключением генератора случайных чисел к принтеру. Один из вариантов использования данной теоремы — демонстрация бытовой нелепости случайного возникновения жизни.
Теорема в полушутливой форме может быть перенесена на выбор метода грубой силы в производстве; тогда она будет звучать так: при достаточном количестве ресурсов любая техническая задача решаема. В данном случае игнорируется ограниченность ресурсов.
Логическая часть теоремы может быть перенесена на всю вселенную, тогда она будет звучать так: «В случае, если вселенная бесконечна в пространстве и/или во времени, то всё, что бы вы ни вообразили, обязательно реализуется где-то во вселенной». Доказывается она исходя из того, что вероятность возникновения любой вообразимой структуры крайне мала, но все же больше нуля, и при бесконечном количестве попыток после крайне большого, но ограниченного их числа окажется равной единице.
Теорема впервые была популяризована астрономом сэром Артуром Эддингтоном. Она стала частью идиоматических выражений благодаря научно-фантастическому рассказу «Несгибаемая логика» (Inflexible Logic) Рассела Мэлони (Russell Maloney), а также упоминалась в «Автостопом по галактике» Дугласа Адамса:

— Форд! — выговорил он, — там, снаружи, бесконечно много обезьян.
И они хотят обсудить с нами «Гамлета», который у них получился.
— Дуглас Адамс, «Автостопом по галактике»

Теорема эта, строго говоря, тривиальна и не имеет особого научного значения, её популярность в массах объясняется видимой парадоксальностью.

Доказательство
читать дальшеПо лемме Бореля — Кантелли, если два события статистически независимы, а результат одного события не влияет на результат другого, то вероятность обоих событий равняется произведению вероятностей всех участвующих событий. Например, если вероятность выпадения определённого числа в кости равняется 1/6, а шанс выигрыша в рулетке с двойным зеро 1/38, то вероятность выигрыша в двух играх одновременно равна 1/6 × 1/38 = 1/228.
Теперь, предположите, что пишущая машинка имеет 50 клавиш, а слово, которое должно быть напечатано — «банан». При печатании наугад вероятность того, что первым напечатанным символом является «б», равна 1/50; такова же вероятность того, что вторым напечатанным символом будет «а», и так далее. Эти события независимы; таким образом, вероятность того, что первые пять букв составят слово «банан», равна (1/50)5.
По той же самой причине вероятность того, что следующие 5 букв будут словом «банан», также (1/50)5, и так далее.
Далее, вероятность того, что блок из 5 букв не является словом «банан», равен 1 − (1/50)5. Поскольку каждый блок напечатан независимо, вероятность того, что ни один из первых n блоков по 5 букв не совпадает со словом «банан», равна
P = (1 − (1/50)5)n.
Если n растет, то P становится меньше.
Количество
n                                   
P
1 000 000                           99,99%
10 000 000 000                     53%
100 000 000 000                    0,17%

Та же самая формула применяется для любой другой строки символов конечной длины.
Это показывает, почему среди очень большого количества обезьян найдётся такая, которая будет точно воспроизводить данный текст (например, «Гамлета»). В этом случае P = (1 − (1/50)5)n, где P представляет вероятность, что ни одна из n обезьян не напечатала «банан» правильно с первой попытки. Если в эксперименте участвует сто миллиардов обезьян, вероятность падает до 0,17 %, и когда количество обезьян n стремится к бесконечности, значение P (вероятность того, что ни одна из n обезьян не смогла воспроизвести данный текст) стремится к нулю. Если заменить слово «банан» на текст «Гамлета», показатель степени увеличится с 5 до числа символов в этом тексте, но принципиально ничего не изменится, лишь понадобится большее n для сохранения того же P.
Это эквивалентно утверждению, что вероятность того, что бесконечное количество обезьян напечатают любой данный текст с первой попытки, равна 1. Другое эквивалентное утверждение: работающая бесконечно долго обезьяна-машинистка рано или поздно напечатает любой наперёд заданный текст конечной длины (например, текст этой статьи).




Демон Максвелла
Материал из Википедии — свободной энциклопедии


Демон Максвелла — мысленный эксперимент, главным персонажем которого является гипотетическое разумное существо ростом c молекулу. Выдумано Джеймсом Максвеллом с целью проиллюстрировать Второе начало термодинамики.

Второе начало термодинамики

Одним из следствий второго начала термодинамики является невозможность передачи тепла от тела с меньшей температурой телу с большей температурой без совершения работы.

Суть парадокса
читать дальше
Мысленный эксперимент состоит в следующем: предположим, сосуд с газом разделён непроницаемой перегородкой на две части: правую и левую. В перегородке отверстие с устройством (так называемый демон Максвелла), которое позволяет пролетать быстрым (горячим) молекулам газа только из левой части сосуда в правую, а медленным (холодным) молекулам — только из правой части сосуда в левую. Тогда, через большой промежуток времени, горячие молекулы окажутся в правом сосуде, а холодные — в левом.
Таким образом, получается, что демон Максвелла позволяет нагреть правую часть сосуда и охладить левую без дополнительного подвода энергии к системе. Энтропия для системы, состоящей из правой и левой части сосуда, в начальном состоянии больше, чем в конечном, что противоречит термодинамическому принципу неубывания энтропии в замкнутых системах (см. Второе начало термодинамики)
Парадокс разрешается, если рассмотреть замкнутую систему, включающую в себя демона Максвелла и сосуд. Для функционирования демона Максвелла необходима передача ему энергии от стороннего источника. За счёт этой энергии и производится разделение горячих и холодных молекул в сосуде, то есть переход в состояние с меньшей энтропией. Детальный разбор парадокса для механической реализации демона (храповик и собачка) приведён в Фейнмановских лекциях по физике, вып. 4, а также в популярных лекциях Фейнмана «Характер физических законов».[1]
Частным случаем вышеописанной ситуации является гигантская флюктуация - с не равной нулю вероятностью все горячие молекулы соберутся в правом сосуде, а все холодные в левом.


Кот Шрёдингера
Материал из Википедии — свободной энциклопедии

Кот Шрёдингера (кошка Шрёдингера) — герой кажущегося парадоксальным мысленного эксперимента Эрвина Шрёдингера, которым он хотел продемонстрировать неполноту квантовой механики при переходе от субатомных систем к макроскопическим.

Суть эксперимента

В закрытый ящик помещён кот. В ящике имеется механизм, содержащий радиоактивное ядро и ёмкость с ядовитым газом. Параметры эксперимента подобраны так, что вероятность того, что ядро распадётся за 1 час, составляет 50 %. Если ядро распадается, оно приводит механизм в действие, он открывает ёмкость с газом, и кот умирает. Согласно квантовой механике, если над ядром не производится наблюдения, то его состояние описывается суперпозицией (смешением) двух состояний — распавшегося ядра и нераспавшегося ядра, следовательно, кот, сидящий в ящике, и жив, и мёртв одновременно. Если же ящик открыть, то экспериментатор обязан увидеть только какое-нибудь одно конкретное состояние — «ядро распалось, кот мёртв» или «ядро не распалось, кот жив».
Вопрос стоит так: когда система перестаёт существовать как смешение двух состояний и выбирает одно конкретное? Цель эксперимента — показать, что квантовая механика неполна без некоторых правил, которые указывают, при каких условиях происходит коллапс волновой функции и кот либо становится мёртвым, либо остаётся живым, но перестаёт быть смешением того и другого.
Вопреки расхожим представлениямчитать дальше, сам Шрёдингер придумал этот опыт вовсе не потому, что он верил, будто «мёртвоживые» коты существуют; наоборот, он считал квантовую механику неполной и не до конца описывающей реальность в данном случае. Поскольку ясно, что кот обязательно должен быть либо живым, либо мёртвым (не существует состояния, промежуточного между жизнью и смертью), то это означает, что это верно и для атомного ядра. Оно обязано быть либо распавшимся, либо нераспавшимся.
Оригинальная статья вышла в немецком журнале Naturwissenschaften («Естественные науки») в 1935 году: E. Schrödinger: «Die gegenwärtige Situation in der Quantenmechanik» («Сегодняшнее положение дел в квантовой механике»), Naturwissenschaften, 48, 807, 49, 823, 50, 844 (November 1935). Целью статьи было обсуждение ЭПР парадокса, опубликованного Эйнштейном, Подольским и Розеном ранее в том же году. Кроме того, что Шрёдингер в этой статье познакомил нас с котом, он ещё ввёл термин «запутанность» (По-немецки: Verschränkung, по-английски: entanglement).




Задача двух генералов
Материал из Википедии — свободной энциклопедии

Задача двух генералов — в вычислительной технике мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. Эта задача является частным случаем задачи византийских генералов, и часто рассматривается в рамках курса компьютерных сетей (в частности протокола TCP), хотя применима и к другим средствам связи. В литературе также иногда упоминается, как задача двух армий.

Определение

Две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагери обеих армий располагаются на двух холмах, разделенных долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, несмотря на принятое решение штурмовать город, генералы не согласовали между собой время начала штурма (время Ч).
Для успешного штурма генералы должны атаковать город одновременно. Штурм, предпринятый только одной армией, приведет к катастрофическим последствиям для атакующих. Требуется найти алгоритм обмена сообщениями, который бы позволил каждому из генералов сказать:
«Да, мы оба атакуем в указанное время.»
Отметим, что достигнуть такого соглашения очень просто — достаточно одного сообщения с временем начала штурма и одного сообщения, подтверждающего получение первого. Сложность задачи заключается в невозможности разработать алгоритм гарантированного обмена этими сообщениями.

Иллюстрация проблемы

читать дальшеПредположим, первый генерал отправляет второму сообщение «Атакуем завтра в девять часов утра». Отправив посыльного, первый генерал не знает, добрался ли посыльный до второго генерала. Не зная, поддержит ли второй генерал его действия, первый может отложить штурм. Зная это, второй генерал может отправить подтверждающее сообщение «Я получил Ваше сообщение и атакую завтра в девять часов утра». Но это сообщение также может быть перехвачено противником. Зная, что первый генерал не начнет штурм без подтверждения, второй генерал также может отложить атаку. Первый генерал может отправить сообщение «Я получил Ваше подтверждение о времени начала штурма», но оно также может быть перехвачено. Быстро становится очевидным, что, сколько бы ни было циклов обмена сообщениями, нет способа гарантированно уведомить обоих генералов о том, что их сообщения получены. Таким образом, задача не имеет решения.