Девлог №78 – Хвиля 58: Дошка Гальтона, реакція Білоусова–Жаботинського & машина Тюрінга

Нові симуляції

🎯 Дошка Гальтона — біноміальний розподіл & центральна гранична теорема

Бобова машина

Бобова машина Френсіса Гальтона (1889) — фізична демонстрація центральної граничної теореми. Кульки падають з єдиного отвору зверху і зустрічають n рядів штифтів. На кожному штифті кулька відхиляється ліворуч з імовірністю p або праворуч з імовірністю q = 1 − p. Якщо порахувати кількість відхилень праворуч k, отриманий розподіл є біноміальним:

P(k) = C(n, k) · p^k · (1-p)^(n-k)     k = 0, 1, ..., n

Середнє дорівнює μ = n·p, а стандартне відхилення — σ = √(n·p·q). За центральною граничною теоремою, зі зростанням n цей біноміальний розподіл збігається до нормального розподілу N(np, npq) незалежно від значення p. Симулятор показує PMF біноміального розподілу пунктирною кривою та плавну нормальну апроксимацію бірюзовим кольором — обидві оновлюються наживо в міру падіння кульок.

Дизайн симуляції

Кульки анімовано рухаються крізь сітку штифтів. Кінцевий бін кожної кульки попередньо обчислюється при появі на основі послідовності Бернуллі, тому вона точно слідує біноміальному розподілу. Ліва панель показує анімований каскад; права панель відображає гістограму кількості кульок у бінах у реальному часі з теоретичним накладенням.

• Рядів n: 4–16 (до 17 бінів)
• Імовірність p: 0.1–0.9 (для асиметричних розподілів)
• Швидкість падіння: 1–20 кульок за кадр анімації
• Жива статистика: спостережуване середнє, спостережуване σ, теоретичне σ
• Миттєве скидання 100 кульок для швидкого заповнення гістограми

🌀 Реакція Білоусова–Жаботинського — клітинний автомат зі збудливим середовищем

Хімія за спіраллю

Реакція Білоусова–Жаботинського — осцилююча хімічна система, відкрита Борисом Білоусовим у 1951 році (і незалежно Анатолем Жаботинським у 1961 році). Суміш малонової кислоти, бромату натрію та каталізатора церію чи фероїну спонтанно циклічно переходить між окисленим і відновленим станами, породжуючи концентричні кольорові хвилі, видимі неозброєним оком. Орегонатор — стандартна кінетична модель, але простіший клітинний автомат відтворює основну поведінку.

Модель Гринберга–Гастінгса

Клітинний автомат зі збудливим середовищем із 3 станами (Гринберг і Гастінгс, 1978) використовує три стани клітин:

• Спокій (0) — клітина стає збудженою, якщо кількість збуджених найближчих сусідів в оточенні Мура з 8 клітин досягає або перевищує поріг T.
• Збудження (1) — на наступному кроці клітина переходить у стан рефрактерності. Це і є «фронт хвилі».
• Рефрактерність (2 … k) — клітина відлічує k кроків назад до стану спокою. Це створює «рефрактерний хвіст», що не дає хвилям розвертатися і змушує спіральні чи концентричні візерунки зберігатися.

Початкові асиметричні зерна породжують пари спіральних хвиль. Спонтанне запалення (з налаштовуваною швидкістю) з часом засіває нові центри хвиль. Весь рендеринг використовує масиви пікселів ImageData для продуктивності, підтримуючи сітки до 300×300 при 60 кадрах/с.

🖥️ Машина Тюрінга — обчислюваність, яку видно

Навіщо симулювати машину Тюрінга?

У статті Алана Тюрінга 1936 року «Про обчислювані числа» була представлена гіпотетична машина, що читає й записує символи на нескінченній стрічці, по одній клітині за раз, керуючись скінченним набором правил. Попри простоту, теза Черча–Тюрінга стверджує, що будь-яку ефективно обчислювану функцію можна обчислити такою машиною. Візуалізація виконання крок за кроком робить абстрактні поняття — приймальні/відхильні стани, зупинку та функцію переходу — конкретними й зрозумілими.

П'ять вбудованих програм

• Двійкове інкрементування — сканує до кінця, додає 1 з поширенням переносу. Вхід 1011 → 1100.
• Унарне додавання — замінює роздільник + на 1 і стирає завершальну 1. Вхід 111+11 → 11111.
• Перевірка паліндрома — позначає та зіставляє зовнішні символи, рухаючись усередину, для алфавіту {a, b}. Приймає abba, відхиляє abab.
• Копіювання рядка — копіює унарний рядок за роздільником: 111 → 1110111.
• Зайнятий бобер зі 3 станами — переможна 3-станова машина зайнятого бобра записує 6 одиниць за 14 кроків перед зупинкою. Старт на порожній стрічці.

Відображення стрічки

Полотно відображає плавне вікно клітин стрічки, центроване на голівці читання/запису. Активна клітина підсвічена фіолетовим сяйвом; порожні клітини показують символ □. Таблиця переходів прокручується, підсвічуючи правило, виконане на кожному кроці. Вказівник голівки стає зеленим при прийнятті, червоним — при відхиленні.

Що далі

Хвиля 59 продовжить розширювати покриття категорій, де є прогалини. Пріоритетні кандидати включають стохастичний резонанс (посилене шумом виявлення сигналу в порогових системах), пружні хвилі (поширення поздовжніх і поперечних хвиль з відбиттям та інтерференцією) та ріст клітин і морфогенез (патерни Тюрінга типу реакція-дифузія, що керують диференціацією клітин).