Численная оценка теоремы о конечных обезьянах

Численная оценка теоремы о конечных обезьянах

перевод оригинальной статьи с мало значимыми сокращениями

бедная обезьяна, как ты потеешь!

«Увы, бедная обезьяна, как ты потеешь!» (Уильям Шекспир, Генрих IV, часть 2, акт 2, сцена 4).

С момента своего возникновения теорема о бесконечных обезьянах стала одним из самых известных мысленных экспериментов. В своей самой популярной форме теорема о бесконечных обезьянах гласит, что если бы у вас было бесконечное количество обезьян и/или бесконечно долгий период времени, то обезьяна, нажимающая клавиши на пишущей машинке в случайном порядке, в конечном итоге наверняка воспроизвела бы произведения Уильяма Шекспира.

Математически доказательство теоремы является простым следствием леммы Бореля–Кантелли. Проще говоря, когда событие происходит в заданном испытании с конечной ненулевой вероятностью, то вероятность того, что событие никогда не произойдет, стремится к нулю, поскольку число независимых испытаний стремится к бесконечности, каким бы невероятным ни было событие в отдельном испытании.

Стивен Вудкок (Stephen Woodcock)

Совсем недавно были попытки проверить теорему эмпирически, как экспериментально, так и в популярной культуре. Эти подходы включали как компьютерное моделирование концептуальной модели, так и исследования с живыми приматами и клавиатурами. Кроме того, в долгоиграющем телешоу «Симпсоны» промышленник Чарльз Монтгомери Бернс пытался сделать это с несколькими обезьянами, прикованными цепями к пишущим машинкам, но сдался, когда лучшим из них было почти диккенсовское «Это было лучшее из времен, это было самое размытое из времен».

Хотя теорема о бесконечных обезьянах хорошо изучена, теорема о конечных обезьянах менее понятна. Авторы рассматривают ситуацию, когда доступно только конечное число обезьян и конечный период времени. Затем вычисляют вероятности того, что определенные фразы будут напечатаны заданным числом обезьян за заданный период времени. Вначале нужно сформулировать предположение модели. Клавиатура содержит K различных клавиш. Каждая печатающая обезьяна (всего М) нажимает N клавиш (по одной за раз) так, что каждая клавиша выбирается с равной вероятностью при каждом нажатии, независимо от всех других выбранных клавиш. Существует целевая строка текста длиной L символов, которую мы хотим набрать. С N нажатиями клавиш, каждое из которых является одним из K различных символов, есть K^N различных упорядоченных последовательностей, которые можно набрать. Ищем, сколько из этих (равновеликих) последовательностей содержат L последовательных символов из целевой строки по крайней мере один раз.

Джей Фаллетта (Jay Falletta)

Что касается строки длиной L как одного «символа», нужно поместить этот один «символ» в одно место в строке из N - L+1 символов. Оставшиеся N - L символов могут быть любыми из K возможных. Поэтому есть (N - L + 1) х (K^(N - L)) случаев, чтобы это произошло. Далее следуют головокружительной смелости математические броски, сочетающиеся с опасными, неожиданными виражами. Ожидаемое количество нажатых клавиш до того, как будет сгенерирована строка, приблизительно равно (K^L) / M.

Чтобы оценить вероятности или ожидаемые временные шкалы, нужно сделать несколько дополнительных предположений. Клавиатура содержит K=30 различных клавиш, охватывающих все буквы английского языка, а также некоторые общие знаки препинания. Для расчетов временной шкалы предполагается, что обезьяна-машинистка нажимает 1 клавишу в секунду каждую секунду дня. Поскольку шимпанзе являются ближайшими родственниками человека среди обезьян, сосредоточимся на них как на изучаемом виде. Принимаем продолжительность рабочей жизни шимпанзе за 30 лет, а тепловую смерть Вселенной - за 10^100 лет после начала эксперимента. Предполагая, что текущая популяция, составляющая около 200 000 шимпанзе, останется постоянной до конца Вселенной, имеем максимум около 6,4 х (10^103) рабочих жизней шимпанзе. В среднем на слово приходится 5,7 символа, исходя из длины английского слова 4,7 плюс 1 пробел или знак препинания.

Далее оценивается ожидаемое количество нажатий клавиш, пока случайно печатающая обезьяна впервые не произведет заданную целевую строку, для нескольких различных строк в диапазонах сложности от одного слова «Бананы» до полного собрания сочинений Уильяма Шекспира. Вероятности численно оцениваются для 3 временных шкал: в пределах продолжительности жизни 1 шимпанзе, в пределах продолжительности жизни всех шимпанзе (не происходит размножения для продления популяции), в пределах тепловой смерти вселенной (популяция обезьян сохраняется до этого времени).

Уильям Шекспир

Результат - все, кроме самых тривиальных фраз, никогда не будут произведены в течение жизни нашей вселенной. Существует много порядков разницы между ожидаемым количеством нажатий клавиш, пока вселенная не придет в термодинамическое равновесие и воспроизведением текстов Уильям, нашего, Шекспира. Cуществует вероятность 5% для 1 шимпанзе напечатать слово «бананы» в течение жизни. Все произведения Барда (884 647 слов), даже если привлечь всех шимпанзе, никогда не будут напечатаны до конца вселенной.

Таким образом, авторы отвергают выводы из теоремы о бесконечных обезьянах как потенциально вводящие в заблуждение в нашей конечной вселенной. Эта оценка твердо помещает теорему о бесконечных обезьянах в один ряд с другими кажущимися парадоксами с противоречивыми результатами в конечных и бесконечных случаях - парадокс Санкт-Петербурга (расхождение между теоретически оптимальным поведением игрока и здравым смыслом), парадокс дихотомии Зенона и парадокс Росса–Литтлвуда, в которых выводы о бесконечных ресурсах прямо противоречат выводам, полученным при рассмотрении ограниченных ресурсов, какими бы значительными они ни были.

Это не первый раз, когда труд обезьян рассматривается как потенциальный источник понятного результата. В 1964 году писатель-фантаст и футурист Артур Кларк предвидел, что «с нашими нынешними знаниями в области психологии животных и генетики мы, безусловно, могли бы решить проблему слуг с помощью царства обезьян. Конечно, в конечном итоге наши супершимпанзе начнут формировать профсоюзы, и мы вернемся к тому, с чего начали». Несмотря на этот страх, насколько известно, ни один шимпанзе до сих пор не принимал участия в забастовке, независимо от оплаты или условий труда.

Учитывая правдоподобные оценки продолжительности жизни вселенной и количества возможных обезьян-машинисток, это все еще оставляет огромные порядки разницы между доступными ресурсами и теми, которые требуются для нетривиальной генерации текста. Таким образом, следует вывод - сам Шекспир непреднамеренно дал ответ на вопрос о том, может ли труд обезьяны быть осмысленной заменой человеческих усилий в качестве источника учености или творчества. «Нет» (Уильям Шекспир, Гамлет, Акт 3, Сцена 3, Строка 87).

Дополнительное подтверждение можно найти в работе "Быть или не быть, вот в чем вопрос: исследование псевдослучайной генерации текстов для написания Гамлета с точки зрения теоремы о бесконечной обезьяне", Эргон Куглер де Мораес Сильва (Ergon Cugler de Moraes Silva), Университет Сан-Паулу, Бразилия, arXiv:2402.16253 [math.NA], 26 февраля 2024.

Эргон Куглер де Мораес Сильва (Ergon Cugler de Moraes Silva)

В статье рассматриваются теоретические и вычислительные аспекты теоремы о бесконечной обезьяне, исследуя количество попыток и время, необходимое для того, чтобы набор псевдослучайных персонажей собрался и произнес знаковую фразу Гамлета, "Быть или не быть, вот в чем вопрос". Черпая вдохновение из оригинальной концепции Эмиля Бореля (1913), исследование углубляется в практические последствия псевдослучайности с использованием Python. Используя симуляции Python для генерации отрывков из Гамлета, исследование перемещается по историческим перспективам и соединяет ранние теоретические основы с современными вычислительными подходами. Набор тестов выявляет попытки и время, необходимые для генерации дополнительных частей целевой фразы. Используя эти результаты, вычисляются факторы роста, прогнозирующие предполагаемые попытки и время для каждой части текста. Результаты указывают на астрономическую сложность создания всей фразы.

Cоздание всей фразы потребовало бы приблизительно 2,68 х 10^69 попыток, что заняло бы колоссальный промежуток времени в 2,95 x 10^66 секунд, 8,18 x 10^62 часов или 9,32 x 10^55 лет. Чтобы представить эту временную шкалу в перспективе, важно подчеркнуть, что 9,32 x 10^55 лет примерно в 6,75 x 10^45 раз больше предполагаемого возраста Вселенной, который составляет 1,38 x 10^10 лет.

По сути, запись фразы «Быть или не быть, вот в чем вопрос» посредством случайной генерации символов потребовала бы астрономической продолжительности, превышающей возраст вселенной в ошеломляющее число раз. Последующие цифры иллюстрируют, как геометрическая прогрессия почти линеаризует предыдущие значения, возрастая экспоненциально по мере увеличения числа значений, которые должны быть сгенерированы при псевдорандомизации символов. Это подчеркивает глубокую сложность поставленной задачи, проливая свет на ограничения и необычайные временные масштабы, связанные с такими теоретическими начинаниями. Только бесконечность могла бы написать Гамлета случайным образом.

Стивен Вудкок (Stephen Woodcock), Джей Фаллетта (Jay Falletta), Технологический университет Сиднея, Австралия, "Численная оценка теоремы о конечных обезьянах", журнал Института Франклина, 9, декабрь 2024.

08.11.2024