Імовірність Дошка Гальтона
Дошка Гальтона — біноміальний розподіл і ЦГТ
Киньте кульки крізь n рядів шпильок (p на кожне відхилення) і спостерігайте, як B(n,p) збігається до нормальної кривої. Відстеження PMF та σ у реальному часі.
Чому виникає дзвоноподібна крива
Шлях кожної кульки через дошку Гальтона — це послідовність n незалежних випробувань Бернуллі. Комірка, в яку вона потрапляє, дорівнює кількості відхилень праворуч k, яка підпорядковується біноміальному розподілу:
Центральна гранична теорема стверджує, що для великих n сума незалежних однаково розподілених випадкових величин наближається до нормального розподілу незалежно від форми розподілу окремої величини. Для дошки Гальтона:
При n = 4 гістограма виглядає дискретною й нерівною. Уже при n = 12 контур напрочуд добре повторює знайому дзвоноподібну криву. Симуляція показує одночасно точну біноміальну PMF (пунктирна помаранчева) та плавне нормальне наближення (бірюзова), дозволяючи спостерігати збіжність під час переміщення повзунка.
Гальтон спершу використовував це, щоб довести, що спадкові ознаки регресують до середнього значення популяції (звідси «регресія до середнього»), але математична структура лежить в основі статистики, фінансів, обробки сигналів та квантової механіки.
Спробувати дошку Гальтона →Хімія Реакція Білоусова-Жаботинського
Реакція Білоусова-Жаботинського — хімічні спіральні хвилі
3-станний клітинний автомат збудливого середовища: спокій→збудження→рефрактерність→спокій, що породжує самоорганізовані спіральні хвилі. Клацніть, щоб посіяти іскри.
Хімія, що мислить сама за себе
Коли Борис Білоусов 1951 року змішав малонову кислоту, бромат і каталізатор на основі церію, він очікував рівноважної кінцевої точки. Натомість суміш почала коливатися: колір коливався між жовтим і безбарвним, повторюючись протягом кількох хвилин. Його результат спершу відхилили як неможливий — здавалося, термодинаміка забороняє стійкі коливання. Жаботинський пізніше, 1961 року, показав, що реакція може коливатися не лише в перемішуваній колбі, а й у тонкому неперемішуваному шарі спонтанно утворює концентричні кільця та спіральні хвилі.
Механізм збудливого середовища
Далеко від рівноваги деякі реакційно-дифузійні системи поводяться як збудливі середовища: невелике збурення може поширюватися як самопідтримувана хвиля. Ключові складові:
- Збудження — область спокою запалюється достатньою кількістю збуджених сусідів
- Поширення — збуджений стан розповсюджується назовні
- Рефрактерність — область рефрактерності, що залишається позаду, запобігає зворотному поширенню, змушуючи хвилі рухатися в одному напрямку
- Відновлення — після рефрактерного періоду клітини можуть бути повторно збуджені
Модель Грінберга-Гастінгса відтворює цю поведінку трьома станами й простими правилами підрахунку. Асиметричне початкове зерно порушує обертальну симетрію й створює пари спіралей. Спіралі обертаються з періодом, що визначається рефрактерним часом і порогом збудження.
Той самий механізм — збудливе середовище, рефрактерний хвіст, спіральний повторний вхід — лежить в основі серцевих аритмій, фронтів лісових пожеж і кіркової поширюваної депресії в мозку.
Спробувати реакцію БЖ →Алгоритми Машина Тюрінга
Машина Тюрінга — покроковий симулятор стрічки
Анімована стрічка, підсвічена таблиця переходів, п'ять вбудованих програм: двійковий інкремент, унарне додавання, паліндром, копіювання, зайнятий бобер.
Найпростіший можливий універсальний комп'ютер
Машина Алана Тюрінга 1936 року складається лише з чотирьох речей: нескінченної стрічки символів, головки читання/запису, скінченної множини станів і функції переходу. Проте ця мінімальна модель обчислювально еквівалентна кожному сучасному комп'ютеру, коли-небудь збудованому — теза Черча-Тюрінга стверджує, що будь-яку ефективно обчислювану функцію можна обчислити на такій машині.
Чому важлива проблема зупинки
Тюрінг довів глибокий негативний результат: не існує алгоритму, який міг би визначити для довільної машини Тюрінга та вхідних даних, чи зупиниться машина зрештою, чи працюватиме вічно. Ця проблема зупинки нерозв'язна — не просто складна, а доказово неможлива. Доведення використовує аргумент діагоналізації: припустимо, що вирішувач H(M, w) існує; побудуємо машину D, яка запускає H на собі й робить протилежне. D призводить до суперечності.
Цей результат поширюється на реальне програмне забезпечення: загалом неможливо довести, що програма вільна від нескінченних циклів, що вона ніколи не зависне, або що дві програми обчислюють одну й ту саму функцію. Саме тому формальна верифікація програм залишається межею досліджень.
Проблема зайнятого бобра
Скільки одиниць може записати n-станна машина Тюрінга на порожній стрічці, перш ніж зупиниться? Функція зайнятого бобра Σ(n) зростає швидше за будь-яку обчислювану функцію — вона необчислювана. 3-станний чемпіон записує 6 одиниць за 14 кроків. Σ(5) = 4098 (доведено 2024 року), Σ(6) невідоме. Спробуйте 3-станного зайнятого бобра в симуляторі; спостерігайте, як він пише в, здавалося б, випадкових напрямках, перш ніж зупинитися щільно упакованим блоком одиниць.
Спробувати машину Тюрінга →Три дисципліни, одна тема: емерджентна складність
Усі три симуляції хвилі 58 об'єднує спільна нитка: прості локальні правила породжують складну глобальну поведінку.
- Дошка Гальтона: кожна взаємодія зі шпилькою — це одне підкидання монети; сукупні комірки породжують несподівано гладку криву — нормальний розподіл.
- Реакція БЖ: кожна клітина перевіряє вісім сусідів проти порогу; сукупна поведінка — глобальні обертові спіралі, що можуть зберігатися тисячі поколінь.
- Машина Тюрінга: кожен крок зчитує один символ і застосовує одне правило; сукупне обчислення може обчислити будь-яку математичну функцію.
Цей зв'язок — локальні правила, глобальна емерджентність — лежить в основі науки про складність і з'являється по всій бібліотеці mysimulator.uk, від клітинних автоматів і нейронних мереж до динаміки зграй і симуляцій ринків.