Немного арифметики

[macroevolution]

 Какой длины должен быть текст, состоящий из букв русского алфавита, чтобы возможных текстов такой длины было больше, чем элементарных частиц во вселенной?
(под "текстом" имеется в виду любая произвольная последовательность букв).

Букв 33; элементарных частиц во вселенной, если не ошибаюсь, где-то около 10^80. 

33 в степени 53 уже превышает это число.
Таким образом, достаточно всего лишь 53 букв: это меньше, чем стандартная строка в вордовском документе.

Написали неполную строчку текста - и уже каким-то непонятным образом соприкоснулись с вселенскими масштабами.
Строчка - вселенная, страничка - уже мультиверс.
Я вот накатал двухтомник на полтора миллиона знаков. Сколько двухтомников такого размера существует в Вавилонской библиотеке Борхеса?  Примерно 10 в степени 2250000 (число из двух с четвертью миллионов цифр). Вселенная отдыхает :)

 

Comments

[liartar.livejournal.com]

:)

[dims12.livejournal.com]

Существуют такие частицы (бозоны), количество которых может быть неопределённым. Не большим, не маленьким, а неопределённым.

[leolion-1.livejournal.com]

Тексты такой длины осмысленно соприкасаются с вселенскими масштабами разве что у Кнышева с Губерманом. Но любителям Твиттера Вы сейчас определенно потрафили:)

Поздравляю с окончанием работ, всю библиотеку Борхеса мы, конечно, не осилим, но на Ваш двухтомник нас (заинтересованной общественности) должно хватить:)

[error-lapsus.livejournal.com]

Сейчас придёт какой-нибудь креационист и скажет: "Вот!". А далее - энное количество слов, по осмысленности приближающееся к случайному набору букв...

[macroevolution.livejournal.com]

На этот случай есть замечательный фрагмент из "Слепого часовщика" Докинза.

Я не знаю, кто сказал первым, что при наличии достаточного времени, обезьяна, беспорядочно стучащая по клавишам пишушей машинки, смогла бы когда-нибудь напечатать все произведения Шекспира. Ключевая фраза здесь, конечно "при наличии достаточного времени". Давайте несколько сузим задачу, стоящую перед нашей обезьяной. Предположим, что ей нужно воспроизвести не все произведения Шекспира, а только короткое предложение "Methinks it is like a weasel" ("Сдаётся мне, что оно похоже на горностая"), и облегчим её работу, предоставив ей пишущую машинку с клавиатурой, состоящей только из 26 букв (заглавных), и клавиши пробела. Сколько времени ей потребуется, чтобы написать это небольшое предложение?
Предложение состоит из 28 символов, так что давайте предположим, что обезьяна будет производить серию попыток, состоящих из 28 ударов по клавиатуре. Если она напечатает фразу правильно, то это будет окончанием эксперимента. Если нет, то мы предоставляем ей другую 28-символьную "попытку". У меня нет знакомых обезьян, но к счастью, моя 11-месячная дочь - опытный генератор случайных символов, она лишь продемонстрировала слишком большое нетерпение, чтобы продвигаться в работе обезьяны-машинистки поэтапно. Вот что она напечатала на компьютере:

UMMK JK CDZZ F ZD DSDSKSM
S SS FMCV PU I DDRGLKDXRRDO
RDTE QDWFDVIOY UDSKZWDCCVYT
H CHVY NMGNBAYTDFCCVD D
RCDFYYYRM N DFSKD LD K WDWK
JJKAUIZMZI UXDKIDISFUMDKUDXI

Поскольку у дочери есть другие важные дела, то роль такой машинистки я поручил компьютерной программе, имитирующей беспорядочно печатающего младенца или обезьяну:

WDLDMNLTDTJBKWIRZREZLMQCO P
Y YVMQKZPGJXWVHGLAWFVCHQYOPY
MWR SWTNUXMLCDLEUBXTQHNZVJQF
FU OVAODVYKDGXDEKYVMOGGS VT
HZQZDSFZIHIVPHZPETPWVOVPMZGF
GEWRGZRPBCTPGQMCKHFDBGW ZCCF

И так далее в том же духе. Несложно подсчитать, как долго нам придётся ждать, пока генератор случайных символов (младенец или обезьяна) напечатают "METHINKS IT IS LIKE A WEASEL". Оценим общее количества возможных фраз заданной длины, которые обезьяна, младенец или генератор случайных символов могли бы напечатать. Вычисления будут теми же самыми, какие мы делали для гемоглобина, и приведут к аналогично большому результат. На первой позиции этой строки возможно 27 возможных символов (включая символ пробела). Шанс, что обезьяна, напечатает букву "M" прямо следует из количества символов - 1 из 27. Шанс, что вторая буква будет "E" аналогичен шансу, что первая буква будет "M", а шанс, что первые две буквы будут "ME" равен их произведению 1/27 × 1/27, что даст 1/729. Шанс на то, что первое слово будет "METHINKS" - это шанс на появление каждой буквы на своём месте - 1/27 для каждой, итого (1/27) × (1/27) × (1/27) × (1/27) ..., и так далее 8 раз, то есть (1/27) в степени 8. Шанс на получение всей этой фразы из 28 символов, есть (1/27) в степени 28, то есть (1/27) умножимое само на себя 28 раз. Это очень маленький шанс, примерно 1 из 10000 миллионов миллионов миллионов миллионов миллионов миллионов. Искомую фразу, таким образом, придётся ждать, мягко говоря, долго, не говоря уж о всех произведениях Шекспира.

[macroevolution.livejournal.com]

ПРОДОЛЖЕНИЕ
Так долго получается в случае одноразового отбора случайной вариации. Теперь рассмотрим нарастающий отбор - насколько он будет эффективнее? Очень и очень намного! Гораздо эффективнее, чем мы возможно себе представляем в первый момент, хотя это почти очевидно, если мы подумаем над этим чуть более. Мы снова используем нашу компьютерную обезьяну, но внесём критическое изменение в программу. Она, как и раньше, снова начинает, выбирая случайную последовательность из 28 букв:

WDLMNLT DTJBKWIRZREZLMQCO P

Однако теперь она "размножает" эту случайную фразу. Она реплицирует её неоднократно, но с некоторой вероятностью случайной ошибки - "мутации" при копировании. Компьютер исследует мутировавшую бессмысленную фразу, "потомка" первоначальной, и выбирает ту, которая более всего (хотя бы чуть-чуть) походит на нашу искомую фразу, "METHINKS IT IS LIKE A WEASEL". В данном случае, в следующем поколении победила такая фраза:

WDLTMNLT DTJBSWIRZREZLMQCO P

Улучшение неочевидное! Но процедура повторилась, и снова мутировавший "потомок" "вывелся" от последней фразы, и отобран новый "победитель". И так поколение за поколением. После 10 поколений, фраза, выбранная на роль "производителя" была такой:

MDLDMNLS ITJISWHRZREZ MECS P

А вот что было после 20 поколений:

MELDINLS IT ISWPRKE Z WECSEL

А вот здесь глаз уже не может не заметить некоторого подобия искомой фразе. В 30-м поколении в подобии можно уже не сомневаться:

METHINGS IT ISWLIKE B WECSEL

На 40-м поколении - мы в одной букве от цели:

METHINKS IT IS LIKE I WEASEL

И вот цель наконец достигнута в 43-м поколении.
Второй прогон компьютер начал с фразы:

Y YVMQKZPFJXWVHGLAWFVCHQXYOPY

Результаты прогона были таковы (снова приводится только каждое десятое поколение):

Y YVMQKSPFTXWSHLIKEFV HQYSPY
YETHINKSPITXISHLIKEFA WQYSEY
METHINKS IT ISSLIKE A WEFSEY
METHINKS IT ISBLIKE A WEASES
METHINKS IT ISJLIKE A WEASEO
METHINKS IT IS LIKE A WEASEP

И конечная цель достигнута в поколении 64. Третий прогон компьютер начал с фразы:

GEWRGZRPBCTPGQMCKHFDBGW ZCCF

И достиг "METHINKS IT IS LIKE A WEASEL" в 41-м поколении селективного "размножения".
Точное время, затраченное компьютером на достижение цели, значения не имеет. Но если вы настаиваете, то он закончил весь первый прогон за время, пока я завтракал - то есть, примерно полчаса. (Энтузиасты-компьютерщики могут счесть, что это неправдоподобно долго. Но дело в том, что программа была написана на БЕЙСИКЕ - это язык программирования для младенцев. Когда я переписал её на Паскаль, то она стала выполняться за 11 секунд). Компьютеры в этих делах несколько быстрее обезьян, но разница действительно не имеет значения. Значение имеет разница между временем нарастающей селекции, и временем, потребным тому же самому компьютеру, работающему с той же скоростью, на достижение целевой фразы, если мы заставим его использовать другую процедуру - процедуру одноразового отбора: это примерно миллион миллионов миллионов миллионов миллионов лет. Это в миллион миллионов миллионов раз больше времени существования Вселенной. Фактически разумнее говорить, что в сравнении с временем, потребным, неважно кому - хоть обезьяне, хоть компьютерному генератору случайных символов, для генерации нашей целевой фразы, возраст вселенной - столь ничтожная величина, что на практике утонет в погрешностях данного рода вычислений. В то же время, компьютерному генератору случайных символов, но работающему по алгоритму нарастающего выбора, для выполнения той же самой задачи потребуется совершенно обозримое время - от 11 секунд до длительности спокойного завтрака.

[macroevolution.livejournal.com]

ОКОНЧАНИЕ
Различие между нарастающим отбором (при котором каждое улучшение, пусть небольшое, используется как фундамент для будущей постройки), и одноразовым выбором (при котором каждая новая "попытка" делается "с нуля"), просто неимоверно огромно. Если бы эволюционный прогресс полагался на одноразовый отбор, то он никогда и нигде не имел бы места. Однако, если где-нибудь и как-нибудь слепые силы природы создадут условия для нарастающего отбора, то необыкновенные и удивительные последствия не заставят себя ждать. Собственно говоря, именно это и произошло на нашей планете, и мы с вами - одно из новейших, и может быть - самое необыкновенное и удивительное из этих последствий. Просто поразительно, как можно всё ещё полагать вычисления, вроде наших вычислений "числа гемоглобина" аргументами против теории Дарвина. Люди, так полагающие, часто эксперты в своей сфере - астрономии или где-то ещё, похоже, вполне искренне полагают, что дарвинизм объясняет организацию живой материи в терминах "спонтанности" - одного только "одноразового отбора". Вера в то, что дарвиновская эволюция "спонтанна", не просто ложна. Это точная антитеза правды. Случай - второстепенный компонент в дарвиновском рецепте, главнейший же - нарастающий отбор, который принципиально неслучаен.

[error-lapsus.livejournal.com]

Чем меня ещё со школы поражала комбинаторика - так это огромным количеством вариантов почти чего угодно :)

[error-lapsus.livejournal.com]

Про нарастающий отбор очень интересно. Особенно про разницу в порядках со случайным перебором. Видимо, та же причина, по которой шахматные партии не длятся миллиарды лет, а кончаются в несколько десятков, а то и в несколько ходов.

[artemn.livejournal.com]

Данный отрывок из Докинза предполагает, что у эволюции есть "цель". Что, очевидно, не так...

[oldodik.livejournal.com]

Это глюк. "Цель" вводится искусственно, чтобы нам было понятнее, как работает эта система. А смысл эксперимента в том, чтоб показать, каким образом такой перебор может выдать результаты, кажущиеся нам осмысленными. Как-то так.

Можно было поставить отбор не на цитату из отца нашего Вильяма, а на округлость букв, и через какое-то время текст состоял бы из одних ООО.

[artemn.livejournal.com]

При чем здесь глюк? Зачем мне вводить искусственную цель, чтобы объяснить механизм эволюции, который никакой цели не имеет? Этот отрывок -- трюк, наподобие тех, которые в извытке водятся в математических шарадах, когда получается, что 2x2=5. Он ничего не объясняет, и скорее всего просто вреден для объяснения тех эволюционных процессов, которые привод к осмысленным (адаптированным) результатам.

[oldodik.livejournal.com]

Лично мне он оказался полезен

[kroshka-cat.livejournal.com]

хорошо, уберите цель, и что изменится? да ничего по сути не изменится, поскольку самоорганизация в автоколебательных неживых системах - факт давным давно известный.
Рассуждения о случайности можно провести не только на базе текста.. возьмите банальную ячейку Бенара - сколько времени, сколько вариантов перебора понадобится, чтобы молекулы воды в ковшике случайным образом начали двигаться строго определенным согласованным образом, образуя ячейку Бенара?
А между тем наличие внешнего источника энергии и силы тяжести - делает процесс абсолютно закономерным, и ячейки Бенара в таких условиях появляются ВСЕГДА.
Вопрос - имеется ли цель у вашей газовой плиты, генерирующей тепло, или у планеты, являющейся источником силы тяжести - так вот, имеется у них ли цель получить на выходе ячейку Бенара? Очевидно нет. А ячейка, тем не менее, появляется. каждый раз, как вы греете воду.

Цель

[oraculofthebbox.livejournal.com]

Есть просто процедура отбора.
В данном случае процедура такова, что отдает преимущество фразам похожим на "METHINKS IT IS LIKE A WEASEL". Обычное Дарвиновское "выживание наиболее приспособленных".

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

[artemn.livejournal.com]

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

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

Все, что я написал, сводится к несложному вроде бы утверждению: нельзя доказывать верный довод с помощью неверных аргументов.

Re: Цель

[artemn.livejournal.com]

Данная процедура отбора (описанная в приведенном отрывке) имеет к реальности отношение меньшее, чем обезьянка за печатной машинкой.

Мы хотим получить "осмысленную" (приспособленную) фразу, но при этом почему-то предполагаем, что фразы, для простоты,

MAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

или

AEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

более осмысленны (приспособленны),

чем

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

очевидно, что это не так. Поэтому пример Докинза не верен.

[kroshka-cat.livejournal.com]

где аргументы неверные? где вы вообще цель углядели? в том, что компутерная программа написана специально для отбора определенных последовательностей букв? И что? У вас есть другое предложение, как учитывать давление окружающей среды? Да, модель очень грубая и примитивная, но сути дела это не меняет.
И потом, данный пример - с текстом, изложен как аргумент в споре, где противоположная сторона совершенно свободно оперирует понятием цели.
Все, что показано в этом примере - так это то, что под действием внешних сил случайные процессы заменяются на закономерные. у сил может и не быть никаких целей. Они просто есть и действуют.

Re: Цель

[kroshka-cat.livejournal.com]

а почему вдруг вообще что-то одно более приспособлено, чем другое? какая разница - программист придумал какое то правило отбора, имитируя давление внешней среды, или на реальный организм действует сама внешняя среда?

По вашим словам, в науке вообще нет места никаким моделям, ибо ни одна из них не имеет отношения к реальности.

[artemn.livejournal.com]

>где аргументы неверные?

в приведенном отрывке из Докинза.

>где вы вообще цель углядели?

Там же, где ее увидели, например, и два других моих оппонента в данной ветке. Совершенно очевидно, что ситуация, предложенная Докинзом, включает не только механизмы изменений, но и цель.

>в том, что компутерная программа написана специально для отбора определенных последовательностей букв? И что?

Вообще-то человек в интернете, задающий вопрос "ну и что", считается слившим дискуссию. Это я не то, чтобы в плане начать ругань, а в общеобразовательном...

>У вас есть другое предложение, как учитывать давление окружающей среды?

Еще Дарвин хорошо все объяснил. Ну и много всяких других людей.

>Да, модель очень грубая и примитивная, но сути дела это не меняет.

Смотря, что считать сутью.

Re: Цель

[artemn.livejournal.com]

>а почему вдруг вообще что-то одно более приспособлено, чем другое?

ну потому, что естественный отбор в противном случае не работает.

>какая разница - программист придумал какое то правило отбора, имитируя давление внешней среды, или на реальный организм действует сама внешняя среда?

То есть Вам для процесса эволюции без разницы, есть там просто механизм, или это творец сидит? нда :)

>По вашим словам, в науке вообще нет места никаким моделям, ибо ни одна из них не имеет отношения к реальности.

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

Re: Цель

[oraculofthebbox.livejournal.com]

Докинз в примере определил "приспособленность" как похожесть на фразу "METHINKS IT IS LIKE A WEASEL". Под похожестью он понимает максимальное количество совпадающих букв.

Вы можете определить приспособленность как вам угодно, лишь бы ваше определение допускало переход от фразы А к фразе Б путем малых изменений с ростом приспособленности на каждом шаге.

Чтобы смысл фразы вас не отвлекал, можете фразу Б взять такой же бессмысленной как и A. Например "ADDFFF Apsfdaspf afaf fasffs".

Суть примера не втом что программа получает осмысленную фразу, а в том что нарастающий отбор действует гораздо быстрее одноразового. И это пример прекрасно иллюстрирует.

Re: Цель

[artemn.livejournal.com]

Полностью согласен. Это ровно о том, о чем я говорю. В данном примере приспособленность=1/расстояние по хэммингу. Таким образом изначально и задается цель эволюции, как бы Вы это не называли. Процесс с известным заранее результатом.

Почему же, однако, Докинз, в качестве цели выбрал именно оссмысленную фразу? потому что ему надо показать, как из бессмысленной последовательности символов у него получается осмысленный текст. Но тогда и приспособленность должна задаваться по-другому, а именно это должна быть выраженная в некоторых единицах "осмысленность" фразы. Например, фраза

METHINKS IT IS LAKT A WEASEL

очевидно более осмысленна, чем фраза

AAAAAAA AAA AAAA AAAAAAAAAA

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

В этом случае, кстати, когда приспособленность=осмысленность, совсем не обязательно получить именно фразу

METHINKS IT IS LIKE A WEASEL

можно было бы получить, скажем, фразу

My lord, the queen would speak with you

что и объясняет, как работает процесс эволюции, в результате которого мы получаем нечто приспособленное (осмысленное), но сказать заранее не можем, что же именно мы получим.

Re: Цель

[wim-winter.livejournal.com]

Приведенная модель корректна.
Так как моделируется не эволюция (как процесс, не имеющий окончания, и, соответственно, цели), а ее механизм (на примере другого процесса, который цель имеет).

[wim-winter.livejournal.com]

Ну, строго говоря пример не арифметический, а скорее комбинаторный.