French
DeutschПравило 90 — Вікіпедія
У математичній галузі клітинних автоматів Правило 90 — елементарний клітинний автомат, заснований на операції виключне або (XOR). Складається з одновимірного масиву клітин, кожна з яких може містити значення 0 або 1. На кожному кроці часу всі значення одночасно замінюються результатом операції XOR двох їхніх сусідніх значень.[1] Martin, Odlyzko та Wolfram, (1984) називають його «найпростішим нетривіальним клітинним автоматом»,[2] 2002 року його широко описав Стівен Вольфрам у книзі «Новий вид науки».[3]
Якщо почати з однієї живої клітини, Правило 90 має часово-просторову діаграму у формі трикутника Серпінського. Поведінку будь-якої іншої конфігурації можна пояснити як суперпозицію копій цієї структури, отриманих за допомогою операції виключне або. Будь-яка конфігурація зі скінченною кількістю ненульових клітин стає реплікатором, який зрештою заповнює масив своїми копіями. Коли правило 90 запускається з випадкової початкової конфігурації, на кожному кроці часу його конфігурація залишається випадковою. Його часово-просторова діаграма утворює багато трикутних «вікон» різного розміру, структур, які утворюються, коли рядок послідовних клітин стають одночасно нульовими, а потім у цей рядок з обох кінців поступово переміщуються клітини зі значенням 1.
Деякі з найперших досліджень Правила 90 проведено у зв'язку з нерозв'язаною проблемою теорії чисел, гіпотезою Ґілбрета[en] про різницю послідовних простих чисел. Цей клітинний автомат пов'язаний із теорією чисел також через послідовність Ґулда. Ця послідовність підраховує кількість ненульових клітин на кожному часовому кроці після запуску Правила 90 з однієї живої клітини. Ці значення є степенями двійки з показниками, що дорівнюють кількості ненульових цифр у двійковому поданні номера кроку. Також відомо про застосування Правило 90 в дизайні гобеленів.
Кожна конфігурація Правила 90 має рівно чотири попередники, тобто, інші конфігурації, які на наступному кроці утворюють цю конфігурацію. Тому, на відміну від багатьох інших клітинних автоматів, таких як Життя Конвея, Правило 90 не має едемського саду, конфігурації без попередників. Це приклад клітинного автомата, який є сюр'єктивним (кожна конфігурація має попередника), але не ін'єктивним (існують набори з більш ніж однієї конфігурації з тим самим наступником). Із теореми про едемський сад випливає, що Правило 90 є локально ін'єктивним (усі конфігурації з однаковим наступником відрізняються в нескінченній кількості клітин).
Правило 90 — елементарний клітинний автомат. Це означає, що він складається з одновимірного масиву клітин, кожна з яких містить одне двійкове значення, 0 або 1. Сукупність значень усіх клітин називають конфігурацією. Автомат отримує початкову конфігурацію, а потім послідовно переходить до інших конфігурацій. На кожному кроці всі клітини оновлюються одночасно. Заздалегідь визначене правило визначає нове значення кожної клітини як функцію її попереднього значення та значень двох сусідніх клітин. Усі клітини підкоряються одному правилу, яке можна подати у вигляді формули або у вигляді таблиці правил, яка визначає нове значення для кожної можливої комбінації сусідніх значень.[1]
У випадку Правила 90 кожне нове значення клітинки є виключним або двох сусідніх значень. Тобто, наступний стан цього автомата формується за такою таблицею правил:[1]
| поточний зразок | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| новий стан центральної клітини | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Назва Правила 90 походить від двійково-десяткової нотації[en] Стівена Вольфрама для одновимірних правил клітинного автомата. Щоб обчислити позначення для правила, об'єднайте нові стани в таблиці правил в одне двійкове число та перетворіть число на десяткове: 010110102 = 9010.[1] Правило 90 також називають автоматом Серпінського через характерну форму трикутника Серпінського, яку воно створює,[4] та клітинним автоматом Мартіна — Одлізко — Вольфрама за прізвищами ранніх дослідників Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram (1984) цього автомата.[5]
Конфігурацію в Правилі 90 можна розділити на дві підмножини клітин, які не взаємодіють одна з одною. Одна з цих підмножин складається з клітин у парних позиціях на парних кроках часу та клітин у непарних позиціях на непарних кроках часу. Інша підмножина складається з клітин у парних позиціях на непарних кроках часу та клітин у непарних позиціях на парних кроках часу. Кожну з цих підмножин можна розглядати як клітинний автомат лише з його половиною клітин.[6] Правила для автоматів у кожній із цих підмножин еквівалентні (за винятком зсуву на половину клітини за часовий крок) іншому елементарному клітинному автомату, Правилу 102, в якому новий стан кожної клітини дорівнює виключному або значень її старого стану та її правого сусіда. Тобто поведінка Правила 90 по суті така ж, як і поведінка двох перемежованих копій Правила 102.[7]
Правило 90 і Правило 102 називають адитивними клітинними автоматами. Це означає, що якщо два початкові стани поєднати обчисленням виключного або кожного з їхніх станів, то їхні наступні конфігурації будуть об'єднані так само. Загалом, можна розділити будь-яку конфігурацію Правила 90 на дві підмножини з неперетинними ненульовими комірками, розвинути дві підмножини окремо та обчислити кожну послідовну конфігурацію початкового автомата як виключне або конфігурацій на тих самих часових кроках двох підмножин.[2]
Автомат Правило 90 (в його еквівалентній формі на одній із двох незалежних підмножин клітинок, що чергуються) досліджували на початку 1970-х років у спробі отримати додаткове розуміння гіпотези Ґілбрета[en] про відмінності послідовних простих чисел. У трикутнику чисел, утворених із простих чисел багаторазовим застосуванням оператора правої різниці, здається, що більшість значень дорівнює 0 або 2. Зокрема, гіпотеза Ґілбрета стверджує, що всі крайні ліві значення в кожному рядку цього трикутника дорівнюють 0 або 2. Якщо неперервна підпослідовність значень в одному рядку трикутника дорівнюють 0 або 2, тоді правило 90 можна використовувати для визначення відповідної підпослідовності в наступному рядку. Miller, (1970) пояснив правило метафорою росту дерев у лісі, назвавши свою статтю на тему «Періодичні ліси низькорослих дерев». У цій метафорі дерево починає рости в кожній позиції початкової конфігурації, значення якої дорівнює 1, і цей ліс дерев потім одночасно росте на нову висоту над землею на кожному кроці часу. Кожна ненульова клітина на кожному часовому кроці представляє позицію, яку займає зростаюча гілка дерева. На кожному наступному кроці часу гілка може перерости в одну з двох клітинок над нею ліворуч і праворуч лише тоді, коли немає іншої гілки, що конкурує за ту саму клітину. Ліс дерев, що росте відповідно до цих правил, має таку саму поведінку, що й Правило 90.[8]
З будь-якої початкової конфігурації Правила 90 можна сформувати математичний ліс, орієнтований ациклічний граф, у якому кожна вершина має щонайбільше одне вихідне ребро, дерева якого такі ж, як дерева в метафорі Міллера. Ліс має вершину для кожної пари (x,i) так що клітина x є відмінною від нуля в момент часу i. Вершини в момент часу 0 не мають вихідних ребер; кожна утворює в лісі корінь дерева. Для кожної вершини (x,i) з i відмінним від нуля її вихідне ребро переходить до (x ± 1, i − 1), унікального ненульового сусіда x на часовому кроці i − 1. Міллер помітив, що в цих лісах утворюються трикутні «галявини», області часово-просторової діаграми без ненульових клітин, обмежених плоским нижнім краєм і діагональними сторонами. Таке очищення утворюється, коли на певному часовому кроці послідовність суміжних клітинок стає нульовою, а потім (у метафорі дерева) гілки ростуть усередину, зрештою знову покриваючи клітини послідовності.[8]
За випадкових початкових умов межі між деревами, утвореними в такий спосіб, самі зміщуються за, здавалося б, випадковим шаблоном, і дерева часто вимирають взагалі. Але за допомогою теорії регістрів зсуву Міллер та інші змогли знайти початкові умови, за яких усі дерева залишаються живими назавжди, модель росту періодично повторюється, і всі галявини можуть гарантовано залишатися обмеженими за розміром.[8][9] Міллер використовував ці повторювані візерунки для гобеленів. Деякі з гобеленів Міллера зображують фізичні дерева; інші візуалізують автомат Правило 90, використовуючи абстрактні візерунки трикутників.[8]
На часо-просторовій діаграмі Правила 90 в i-му рядку записано конфігурацію автомата на i-му кроці. Коли початковий стан має одну ненульову комірку, ця діаграма виглядає як трикутник Серпінського, фрактал, утворений об'єднанням трикутників у більші трикутники. Правила 18, 22, 26, 82, 146, 154, 210 і 218 також створюють трикутники Серпінського з однієї комірки, однак не всі вони створюються цілком однаково. Один зі способів пояснення цієї структури використовує той факт, що в Правилі 90 кожна комірка є виключним або двох своїх сусідів. Оскільки це еквівалентно додаванню за модулем 2, це генерує версію трикутника Паскаля за модулем 2. Діаграма містить 1 там, де в трикутнику Паскаля непарне число, і 0 там, де в трикутнику Паскаля парне число. Це дискретний варіант трикутника Серпінського.[1][10]
Кількість живих клітин у кожному рядку цього візерунка дорівнює степеню двох. В i-му рядку вона дорівнює 2k, де k — кількість ненульових цифр у двійковому поданні числа i. Послідовність цих кількостей живих клітин,
- 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, … послідовність A001316 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
відома як послідовність Ґулда. Єдиною живою клітиною початкової конфігурації є пилкоподібний малюнок[en]. Це означає, що в деякі проміжки часу кількість живих клітин зростає як завгодно, тоді як в інші вона нескінченно часто спадає лише до двох живих клітин. Швидкість зростання цього шаблону має характерну зростальну пилоподібну форму хвилі, за якою можна розпізнавати фізичні процеси, які поводяться подібно до Правила 90.[4]
Трикутник Серпінського також зустрічається в тонший спосіб у еволюції будь-якої конфігурації Правила 90. На будь-якому кроці i в еволюції Правила стан будь-якої комірки можна обчислити як виключне або підмножини клітин початкової конфігурації. Ця підмножина має таку ж форму, що i-й рядок трикутника Серпінського.[11]
У трикутнику Серпінського для будь-якого цілого числа i рядки, номери яких кратні 2i, мають ненульові клітини, розташовані на відстані принаймні 2i. Отже, через адитивну властивість Правила 90, якщо початкова конфігурація складається зі скінченної комбінації ненульових клітин P із шириною, меншою за 2i, то на кроках, кратних 2i, конфігурація складатиметься з копій P, розташованих на відстані принаймні 2i одиниць від початку до початку. Ця відстань достатньо широка, щоб копії не заважали одна одній. Кількість копій дорівнює кількості ненульових клітин у відповідному рядку трикутника Серпінського. Отже, в цьому правилі кожен шаблон є реплікатором: він генерує кілька своїх копій, які поширюються по всій конфігурації, зрештою заповнюючи весь масив. Інші правила, зокрема універсальний конструктор фон Неймана[en], клітинний автомат Кодда[en] та цикли Ленґтона[en], також мають реплікатори, які працюють, переносячи та копіюючи послідовність інструкцій для самопобудови. Навпаки, реплікація в Правилі 90 є тривіальною й автоматичною.[12]
У Правилі 90 на нескінченній одновимірній ґратці кожна конфігурація має рівно чотири конфігурації-попередниці. Це пояснюється тим, що в попереднику будь-які дві послідовні клітини можуть мати будь-яку комбінацію станів, але після вибору станів цих двох клітин існує лише один узгоджений вибір для станів решти клітин. Тому в Правилі 90 немає Едемського саду, конфігурації без попередниць. Конфігурація за Правилом 90, що складається з однієї ненульової клітини (з усіма іншими нулями), не має попередниць, які мали б скінченну кількість ненульових клітин. Однак ця конфігурація не є Едемським садом, оскільки вона має попередниць із нескінченною кількістю ненульових значень.[13]
Той факт, що кожна конфігурація має попередницю, можна підсумувати словами, що Правило 90 є сюр'єктивним. Функція, яка відображає кожну конфігурацію в її наступницю, математично є сюр'єктивною функцією. Також Правило 90 не є ін'єктивним. В ін'єктивному правилі кожні дві різні конфігурації мають різних наступників, але Правило 90 має пари конфігурацій з однаковими наступниками. Отже, Правило 90 — приклад клітинного автомата, який є сюр'єктивним, але не ін'єктивним. Теорема Едемського саду Мура та Майгілла передбачає, що кожен ін'єктивний клітинний автомат має бути сюр'єктивним, але цей приклад показує, що зворотне хибне.[13][14]
Оскільки кожна конфігурація має лише обмежену кількість попередниць, еволюція Правила 90 зберігає ентропію будь-якої конфігурації. Зокрема, якщо нескінченна початкова конфігурація вибирається незалежно випадковим заданням стану кожної клітини, при цьому кожен із двох станів має рівну ймовірність вибору, то кожну наступну конфігурацію описує такий самий розподіл імовірностей.[2]
Багато інших клітинних автоматів та інших обчислювальних систем здатні імітувати поведінку Правила 90. Наприклад, конфігурацію Правила 90 можна перетворити в конфігурацію елементарного клітинного автомата Правило 22. Для перетворення кожну клітину Правила 90 замінюють трьома послідовними клітинами Правила 22. Усі ці клітини дорівнюють нулю, якщо клітина Правила 90 сама дорівнює нулю. Ненульова клітинка правила 90 перетворюється на одиницю, після якої йдуть два нулі. За такого перетворення кожні шість кроків автомата Правило 22 імітують один крок автомата Правило 90. Подібні прямі симуляції Правила 90 також можливі в елементарних клітинних автоматах Правило 45 і Правило 126, для певних систем перезапису рядків[en] і систем міток[en], а також у деяких двовимірних клітинних автоматах, зокрема у Wireworld. Правило 90 також може моделювати себе. Якщо кожну клітину конфігурації Правила 90 замінити парою послідовних клітин, перша з яких містить початкове значення клітини, а друга — нуль, то ця подвоєна конфігурація поводитиметься так само, як початкова конфігурація, на половині швидкості.[15]
Відомо, що різні інші клітинні автомати підтримують реплікатори, шаблони, які копіюють себе, і більшість із них мають таку саму поведінку, як у моделі росту дерева для Правила 90. Нова копія розміщується з обох боків шаблону реплікатора, доки там є вільне місце. Однак якщо два реплікатори намагаються скопіювати себе в однакові позиції, то простір залишається порожнім. У будь-якому випадку самі реплікатори зникають, залишаючи свої копії для продовження реплікації. Типовим прикладом такої поведінки є реплікатор у двовимірному автоматі HighLife. Його правило багато в чому схоже на «Життя» Конвея, але такого малого реплікатора в «Житті» не існує. Коли автомат підтримує реплікатори з однаковою схемою росту, можна використати одновимірні масиви реплікаторів для моделювання Правила 90.[16] Правило 90 (на скінченних рядах клітин) також можна змоделювати блоковими осциляторами двовимірного життяподібного клітинного автомата[en] B36/S125, також званого «2x2», і поведінку Правила 90 можна використати для характеристики можливих періодів цих осциляторів.[17]
- ↑ а б в г д Wolfram, Stephen (1983), Statistical mechanics of cellular automata, Reviews of Modern Physics, 55 (3): 601—644, Bibcode:1983RvMP...55..601W, doi:10.1103/RevModPhys.55.601, архів оригіналу за 21 вересня 2013, процитовано 7 лютого 2011.
- ↑ а б в Martin, Olivier; Odlyzko, Andrew M.; Wolfram, Stephen (1984), Algebraic properties of cellular automata, Communications in Mathematical Physics, 93 (2): 219—258, Bibcode:1984CMaPh..93..219M, doi:10.1007/BF01223745, архів оригіналу за 10 вересня 2012, процитовано 7 лютого 2011.
- ↑ Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media. The book's index lists over 50 distinct subtopics for Rule 90.
- ↑ а б Claussen, Jens Christian; Nagler, Jan; Schuster, Heinz Georg (2004), Sierpinski signal generates 1/f α spectra, Physical Review E, 70 (3): 032101, arXiv:cond-mat/0308277, Bibcode:2004PhRvE..70c2101C, doi:10.1103/PhysRevE.70.032101, PMID 15524560.
- ↑ Misiurewicz, Michał; Stevens, John G.; Thomas, Diana M. (2006), Iterations of linear maps over finite fields, Linear Algebra and Its Applications, 413 (1): 218—234, doi:10.1016/j.laa.2005.09.002.
- ↑ McIntosh, Harold V. (1993), Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992) (PDF), Instituto de Ciencias, Universidad Autónoma de Puebla.
- ↑ Kawaharada, Akane (2014), Ulam's cellular automaton and Rule 150, Hokkaido Mathematical Journal, 43 (3): 361—383, doi:10.14492/hokmj/1416837570, MR 3282639: «Except for trivial CAs the other four linear elementary CAs, Rule 60, Rule 90, Rule 102 and Rule 150, are either essentially equivalent to Rule 90 or Rule 150.»
- ↑ а б в г Miller, J. C. P. (1970), Periodic forests of stunted trees, Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences, 266 (1172): 63—111, Bibcode:1970RSPTA.266...63M, doi:10.1098/rsta.1970.0003, JSTOR 73779.
- ↑ ApSimon, H. G. (1970), Periodic forests whose largest clearings are of size 3, Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences, 266 (1172): 113—121, Bibcode:1970RSPTA.266..113A, doi:10.1098/rsta.1970.0004, JSTOR 73780; ApSimon, H. G. (1970), Periodic forests whose largest clearings are of size n ≥ 4, Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences, 266 (1538): 399—404, Bibcode:1970RSPSA.319..399A, doi:10.1098/rspa.1970.0185, JSTOR 73780. A similar analysis of periodic configurations in Rule 90 also appears in Wolfram, (2002), p. 954.
- ↑ Wolfram, (2002), pp. 25–26, 270—271, 870.
- ↑ Kar, B. K.; Gupta, A.; Chaudhuri, P. Pal (1993), On explicit expressions in additive cellular automata theory, Information Sciences, 72 (1–2): 83—103, doi:10.1016/0020-0255(93)90030-P.
- ↑ Waksman, Abraham (1969), A model of replication, Journal of the ACM, 16 (1): 178—188, doi:10.1145/321495.321509; Amoroso, Serafino; Cooper, Gerald (1971), Tessellation structures for reproduction of arbitrary patterns, Journal of Computer and System Sciences, 5 (5): 455—464, doi:10.1016/S0022-0000(71)80009-0. Wolfram, (1983) (Fig.33 and surrounding text) also mentions the same property, and as well as citing Waksman, Amoroso, and Cooper he credits its observation to unpublished work by Edward Fredkin in 1981.
- ↑ а б Skyum, Sven (1975), Confusion in the Garden of Eden, Proceedings of the American Mathematical Society, 50 (1): 332—336, doi:10.1090/S0002-9939-1975-0386350-1
- ↑ Sutner, Klaus (1991), De Bruijn Graphs and Linear Cellular Automata (PDF), Complex Systems, 5: 19—30. Wolfram, (2002), pp. 959—960. Martin, Odlyzko та Wolfram, (1984) provide a similar analysis of the predecessors of the same rule for finite sets of cells with periodic boundary conditions.
- ↑ Wolfram, (2002), pp. 269—270, 666—667, 701—702, 1117.
- ↑ Griffeath, David (1996), Recipe for the week of July 1–7: Replicating Skeeters, The Primordial Soup Kitchen.
- ↑ Johnston, Nathaniel (2010), The B36/S125 "2x2" Life-like cellular automaton, у Adamatzky, Andrew (ред.), Game of Life Cellular Automata, Springer-Verlag, с. 99—114, arXiv:1203.1644, Bibcode:2010golc.book...99J, doi:10.1007/978-1-84996-217-9_7.
- Weisstein, Eric W. Правило 90(англ.) на сайті Wolfram MathWorld.
- Правило 90 в атласі клітинних автоматів Вольфрама (англ.)