Информация и Life
May. 29th, 2012 12:45 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vlkamovКонвей придумал "игру" Life лет полста тому назад. С тех пор "Жизнь", пардон, живет все более полнокровной жизнью. С одной стороны это практически Hello, world клеточных автоматов. С другой стороны, в "Жизни" реализуются все более сложные алгоритмы, вплоть до того, что построена машина Тьюринга (МТ), которая эквивалентна прочим вычислительным устройствам. То есть при желании в "Жизни" можно даже сэмулировать обычный писюк, хошь 32-битный, хошь 64-битный.
И тогда меня поразила мысль, которая в общем-то справедлива, хотя и не так очевидна в приложении к тем же писюкам. А именно:
Life - генератор информации. То есть выдает информации больше, чем было заложено изначально. И если сложность устройства PC сильно маскирует этот факт, то описание правил Life на машинных и человечьих языках обычно не длиннее 1 килобайта. И есть начальные состояния, которые тоже весьма просты, но порождают чудовищно сложные картины, описание которых, как его ни пакуй, на порядки длиннее изначальных компонент.
Задумался. До сих пор мне был известен только один источник инфорамции - шум. Но в "Жизни", в отличие от жизни, шума нет. Откуда тогда информация ? Должен быть не меньший по интенсивности поток [псевдо]хаоса из которого вырезаются все эти поражающие воображение сцены. Собственно такты - регулярный поток, генератора случайных чисел нет. Но сочетание регулярных по отдельности счетчика времени, координат, алгоритма и начальной расстановки может производить искомый хаос, если у какой-то пары есть иррегулярное сочетание. И "жизнь" становится прекрасна и удивительна.
Проиллюстрирую возникновение иррегулярности на более слабом примере. Возьмем пару сцепленных шестеренок. Если первая содержит шесть зубьев (примем что возможны 6 различных положений), а вторая 12, то всего в этой системе возможны 12 различных сочетаний. Но если на второй шестеренке 13 зубьев, то получается уже 6*13=78 сочетаний. То есть не меняя конструкции принципиально, а только лишь слегка - параметры, мы умножаем количествосущностей состояний. Еще интереснее этот эффект вглядит в парах 6x6 и 6x7. Легким движением руки из тривиальных 6 получается хорошо различимые 42 состояния.
Аналогичным образом устроен не угловой, а линейный механизм - штангенциркуль. Нониус содержит на 1 деление меньше (см. корень слова), поэтому из 100 делений миллиметровой шкалы и 9 делений нониуса получается 900 различных отсчетов. Кстати, в угломерах тоже есть нониусы.
Мое личное открытие генерации хаоса состоялось при знакомстве с динамикой популяций. Про Life я уже знал и даже попрактиковался в ее программировании, но там было всеукрадено изучено до нас, т.ч. ощущения новизны не было. Уравнения Вольтерра-Лотка - обыкновенные дифференциальные и даже имеют аналитическое решение, в простейшем случае (лисы-зайцы) периодическое. Графики лучше смотреть здесь:
http://www.exponenta.ru/educat/class/courses/ode/theme17/theory.asp
Внесение разного рода поправок ("логистических" и др.) несколько усложняет картину, но не сильно. Количество лис и зайцев выражены действительными числами для удобства решения дифференциальных уравнений. В жизни же лисы и зайцы существенно дискретны, не продифференцируешь. По этой причине на уравнения я сразу поклал и начал с моделирования немногочисленных популяций: лис порядка 10, зайцев - соответственно. Полез такой хаос, что никакому Вольтерра в страшном сне не снилось ! И если число сочетаний, как и в паре шестеренок, сверху ограничено Лmax x Зmax, то последовательность интервалов между пиками уже содержит настоящую хаотическую компоненту. Учет даже самых простейших жизненных реалий обычно усиливает хаос, заодно увеличивая амплитуды колебаний.
Впрочем есть и весьма абстрактные генераторы хаоса. Кроме алгоритмов вычисления псевдослучайных чисел, хотелось бы обратить внимание на число "пи". Казалось бы, его определение можно уложить в сотню-другую байтов. Однако, когда даже эта весьма лапидарная формулировка входит в "зацепление" с определением рациональных чисел, возникает хаос в чистом виде. И правильность вычислений знаков числа "пи" проверяют по тому, а достаточно ли случайны* цифры в этом ряду.
В жизни поток хаоса может обеспечить даже одна лишь квантовая неопределенность, но и в строго детерминированных системах, как видим тоже есть место свободе.
(*) Конечно же не буквально случайны, а распределены по тому же закону, что и случайные цифры.
И тогда меня поразила мысль, которая в общем-то справедлива, хотя и не так очевидна в приложении к тем же писюкам. А именно:
Life - генератор информации. То есть выдает информации больше, чем было заложено изначально. И если сложность устройства PC сильно маскирует этот факт, то описание правил Life на машинных и человечьих языках обычно не длиннее 1 килобайта. И есть начальные состояния, которые тоже весьма просты, но порождают чудовищно сложные картины, описание которых, как его ни пакуй, на порядки длиннее изначальных компонент.
Задумался. До сих пор мне был известен только один источник инфорамции - шум. Но в "Жизни", в отличие от жизни, шума нет. Откуда тогда информация ? Должен быть не меньший по интенсивности поток [псевдо]хаоса из которого вырезаются все эти поражающие воображение сцены. Собственно такты - регулярный поток, генератора случайных чисел нет. Но сочетание регулярных по отдельности счетчика времени, координат, алгоритма и начальной расстановки может производить искомый хаос, если у какой-то пары есть иррегулярное сочетание. И "жизнь" становится прекрасна и удивительна.
Проиллюстрирую возникновение иррегулярности на более слабом примере. Возьмем пару сцепленных шестеренок. Если первая содержит шесть зубьев (примем что возможны 6 различных положений), а вторая 12, то всего в этой системе возможны 12 различных сочетаний. Но если на второй шестеренке 13 зубьев, то получается уже 6*13=78 сочетаний. То есть не меняя конструкции принципиально, а только лишь слегка - параметры, мы умножаем количество
Аналогичным образом устроен не угловой, а линейный механизм - штангенциркуль. Нониус содержит на 1 деление меньше (см. корень слова), поэтому из 100 делений миллиметровой шкалы и 9 делений нониуса получается 900 различных отсчетов. Кстати, в угломерах тоже есть нониусы.Мое личное открытие генерации хаоса состоялось при знакомстве с динамикой популяций. Про Life я уже знал и даже попрактиковался в ее программировании, но там было все
http://www.exponenta.ru/educat/class/courses/ode/theme17/theory.asp
Внесение разного рода поправок ("логистических" и др.) несколько усложняет картину, но не сильно. Количество лис и зайцев выражены действительными числами для удобства решения дифференциальных уравнений. В жизни же лисы и зайцы существенно дискретны, не продифференцируешь. По этой причине на уравнения я сразу поклал и начал с моделирования немногочисленных популяций: лис порядка 10, зайцев - соответственно. Полез такой хаос, что никакому Вольтерра в страшном сне не снилось ! И если число сочетаний, как и в паре шестеренок, сверху ограничено Лmax x Зmax, то последовательность интервалов между пиками уже содержит настоящую хаотическую компоненту. Учет даже самых простейших жизненных реалий обычно усиливает хаос, заодно увеличивая амплитуды колебаний.
Впрочем есть и весьма абстрактные генераторы хаоса. Кроме алгоритмов вычисления псевдослучайных чисел, хотелось бы обратить внимание на число "пи". Казалось бы, его определение можно уложить в сотню-другую байтов. Однако, когда даже эта весьма лапидарная формулировка входит в "зацепление" с определением рациональных чисел, возникает хаос в чистом виде. И правильность вычислений знаков числа "пи" проверяют по тому, а достаточно ли случайны* цифры в этом ряду.
В жизни поток хаоса может обеспечить даже одна лишь квантовая неопределенность, но и в строго детерминированных системах, как видим тоже есть место свободе.
(*) Конечно же не буквально случайны, а распределены по тому же закону, что и случайные цифры.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-05-29 07:14 am (UTC)=======
Что касается генератора информации, то к сожалению найти автомат, который в результате своей эволюции даст нужную последовательность, например, текст "Войны и мира" "выросшего из зёрнышка" начального кода, очень трудно. А был бы отличный компрессор данных.
====
Ну, и про хаос. "Хаос - вид порядка". Всё упорядочения равноправны, включая натуральный ряд. Все зарегистрированные последовательности теряют свойство случайности и приобретают закономерность следования определяемые свойствами носителя и процедурой регистрации. Так что, с этим у Вас я не согласен - никакого места свободе в детерминированных системах нет. Невычислимость или непредсказуемость, это другой вопрос. Степени свободы в механической системе дают количество их комбинаций и вариабельность внутри этого кобинаторного множества но не более. А вот по неголономным связям - свобода полная. Но там и детерминизму кирдык.
no subject
Date: 2012-05-29 08:19 am (UTC)Собсно поведение электронов в процессоре определяется квантовой механикой и геометрией областей с разным типом проводимости. Шутка.
Не отрицая эквивалентности вашего подхода предпочту более привычный. Потому что привычный.
> методы, которые можно реализовать на автомате являются лишь подмножеством всех, значительно больших
> по количеству "операций", которые можно осуществить в рамках автомата, но которые или вообще не
> формализуются или их формализация бессмысленна
Трудно быть богом. Для человеческой же деятельности достаточно автоматов.
> найти автомат, который в результате своей эволюции даст нужную последовательность, например,
> текст "Войны и мира" "выросшего из зёрнышка" начального кода, очень трудно
Уже найден - вычисление числа "пи".
> я не согласен - никакого места свободе в детерминированных системах нет. Невычислимость или непредсказуемость, это другой вопрос.
Они практически эквивалентны. Независимо от чьего-либо согласия.
Пафос моей заметки в том, что в практических задачах сырьем для получения информации может быть автомат, вычисляющий число "пи", "Жизнь" и т.п. Теоретическая предопределенность этих последовательностей практического значения не имеет, как и исчисление чертей на кончике иглы.
no subject
Date: 2012-05-29 09:43 am (UTC)<<Не отрицая эквивалентности вашего подхода предпочту более привычный. Потому что привычный.>>
Да, я знаю... Но, тем не менее считаю разговор полезным. Для меня, так точно.
<<Трудно быть богом. Для человеческой же деятельности достаточно автоматов.>>
угу. Но речь-то я вёл не об этом! А о том, что операций много больше, чем требуется для реализации какой-то алгебры. Из этого следует и вычислительная неприводимость. Автомат работает, а вычислить коротким способом результат, невозможно. При этом получается, что автомат имеет больше возможностей, чем любая формальная алгебра. И утверждение о том, что аналитике подвластно всё на свете в корне неверно! Эти методы равноправны с другими.
<<Уже найден - вычисление числа "пи".>> Не, я не о том, что в числе пи "есть всё на свете", а конкретно о свёртке результирующей последовательности, текста "Войны и мир" в начальный короткий код, от которого в рамках клеточного автомата можно сгененировать эту последовательность.
<<Они практически эквивалентны. Независимо от чьего-либо согласия.>> Чёрта лысого они эквивалентны!
Невычислимость определяется, как невозможность получить значение на I-том шаге автомата, минуя все I-1 шагов.
Но автомат можно смоделировать более быстродействующим. И всё же предсказать значение I-того шага за счёт моделирования одной физической системы с помощью другой. Именно на это указывал Вольфрам ещё в 1983-м.
Аналитика не везде справляется, о чём я не устаю повторять. А физическая модель как раз может справиться. Но это опять же относится только к детерминированной системе (голономной в механическом смысле). На неголономной рулетке (шарик), красное/чёрное точно предсказать нельзя.
<<Теоретическая предопределенность этих последовательностей практического значения не имеет>>
Как раз это я и оспариваю! Если конвейер это аналог клеточного автомата, а это как раз так, то вся фишка в эволюционном отборе воспроизводимой последовательнсти задания правил. Вплоть до результата - хоть велосипеда, хоть организма :)
no subject
Date: 2012-05-29 08:14 am (UTC)Life - НЕ генератор информации. В любой момент система находится в одном из доступных ей 2^N состояний, где N - число клеток поля. Для описания состояния (любого) требуется N разрядное двоичное слово. Даже абсолютно пустое поле требует те же N бит для своего определения (000....00).
>> ...больше, чем было заложено изначально
Изначально вы закладываете ровно столько же информации. Тот факт, что какие-то клетки вы не заполнили в действительности означает что вы заполнили их нулями.
no subject
Date: 2012-05-29 09:20 am (UTC)no subject
Date: 2012-05-29 09:44 am (UTC)