Rule 110
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (November 2012) |
The Rule 110 cellular automaton (often called simply Rule 110)[a] is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete.[2] This implies that, in principle, any calculation or computer program can be simulated using this automaton.
Definition
[edit]In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value, as well as on those of its two neighbors.
The Rule 110 automaton has the following set of rules:
| Current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| New state for center cell | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
The name "Rule 110" derives from the fact that this rule can be summarized in the binary sequence 01101110; interpreted as a binary number, this corresponds to the decimal value 110. This is the Wolfram code naming scheme.
History
[edit]In 2004, Matthew Cook published a proof that Rule 110 with a particular repeating background pattern is Turing complete, i.e., capable of universal computation, which Stephen Wolfram had conjectured in 1985.[2] Cook presented his proof at the Santa Fe Institute conference CA98 before publication of Wolfram's book A New Kind of Science. This resulted in a legal affair based on a non-disclosure agreement with Wolfram Research.[3] Wolfram Research blocked publication of Cook's proof for several years.[4]
Interesting properties
[edit]Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been directly proven, although proofs for several similar rules follow as simple corollaries (e.g. Rule 124, which is the horizontal reflection of Rule 110). Rule 110 is arguably the simplest known Turing complete system.[2][5]
Rule 110, like the Game of Life, exhibits what Wolfram calls "Class 4 behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in complex ways.[6]
Matthew Cook proved Rule 110 capable of supporting universal computation by successively emulating cyclic tag systems, then 2-tag system, and then Turing machines. The final stage has exponential time overhead because the Turing machine's tape is encoded with a unary numeral system. Neary and Woods (2006) presented a different construction that replaces 2-tag systems with clockwise Turing machines and has polynomial overhead.[7]
The proof of universality
[edit]Matthew Cook presented his proof of the universality of Rule 110 at a Santa Fe Institute conference, held before the publication of A New Kind of Science. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction.[8] The character of Cook's proof differs considerably from the discussion of Rule 110 in A New Kind of Science. Cook has since written a paper setting out his complete proof.[2]
Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system, which is known to be universal. He first isolated a number of spaceships, self-perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
Spaceships in Rule 110
[edit]The function of the universal machine in Rule 110 requires a finite number of localized patterns to be embedded within an infinitely repeating background pattern. The background pattern is fourteen cells wide and repeats itself exactly every seven iterations. The pattern is 00010011011111.
Three localized patterns are of particular importance in the Rule 110 universal machine. They are shown in the image below, surrounded by the repeating background pattern. The leftmost structure shifts to the right two cells and repeats every three generations. It comprises the sequence 0001110111 surrounded by the background pattern given above, as well as two different evolutions of this sequence.
In the figures, time elapses from top to bottom: the top line represents the initial state, and each following line the state at the next time.
The center structure shifts left eight cells and repeats every thirty generations. It comprises the sequence 1001111 surrounded by the background pattern given above, as well as twenty-nine different evolutions of this sequence.
The rightmost structure remains stationary and repeats every seven generations. It comprises the sequence 111 surrounded by the background pattern given above, as well as five different evolutions of this sequence.
Below is an image showing the first two structures passing through each other without interacting other than by translation (left), and interacting to form the third structure (right).
There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.
Построение циклической системы тегов
[ редактировать ]Механизм системы циклических тегов состоит из трех основных компонентов:
- Строка данных , которая является стационарной;
- Бесконечно повторяющаяся серия конечных производственных правил , которые начинаются справа и движутся влево;
- Бесконечно повторяющаяся серия тактовых импульсов , которые начинаются слева и движутся вправо.
Исходное расстояние между этими компонентами имеет первостепенное значение. Чтобы клеточный автомат реализовал систему циклических тегов, начальные условия автомата должны быть тщательно выбраны так, чтобы различные локализованные структуры, содержащиеся в них, взаимодействовали высокоупорядоченным образом.
Строка данных в системе циклических тегов представлена серией стационарных повторяющихся структур показанного выше типа. Различное количество горизонтального пространства между этими структурами позволяет отличить 1 символ от 0 символов. Эти символы представляют собой слово , с которым работает система циклических тегов, и первый такой символ уничтожается при рассмотрении каждого правила производства. Если этот ведущий символ равен 1, в конец строки добавляются новые символы; когда он равен 0, новые символы не добавляются. Механизм достижения этого описан ниже.
Справа входят ряд движущихся влево структур, показанных выше, разделенных разным количеством горизонтального пространства. Большое количество этих структур комбинируется с разными интервалами для обозначения 0 и 1 в правилах производства системы циклических тегов. Поскольку правила производства системы тегов известны во время создания программы и бесконечно повторяются, шаблоны 0 и 1 в начальном состоянии могут быть представлены бесконечно повторяющейся строкой. Каждое производственное правило отделено от следующего другой структурой, известной как разделитель правил (или разделитель блоков ), которая перемещается влево с той же скоростью, что и кодирование продуктивных правил.
Когда разделитель правил с перемещением влево встречает стационарный символ в строке данных системы циклических тегов, это приводит к уничтожению первого встреченного символа. Однако его последующее поведение варьируется в зависимости от того, был ли символ, закодированный строкой, 0 или 1. Если 0, разделитель правил меняется на новую структуру, которая блокирует входящее производственное правило. Эта новая структура уничтожается, когда она встречает следующий разделитель правил.
Если, с другой стороны, символом в строке была 1, разделитель правил изменится на новую структуру, которая допускает входящее производственное правило. Хотя новая структура снова уничтожается при встрече со следующим разделителем правил, она сначала позволяет ряду структур пройти влево. Затем эти структуры добавляются в конец строки данных системы циклических тегов. Это окончательное преобразование осуществляется с помощью серии бесконечно повторяющихся, движущихся вправо тактовых импульсов по схеме, движущейся вправо, показанной выше. Тактовые импульсы преобразуют входящие 1-символы, движущиеся влево, из производственного правила в стационарные 1-символы строки данных, а входящие 0-символы из производственного правила в стационарные 0-символы строки данных.
Циклическая система тегов работает
[ редактировать ]
На рисунке выше показана схема реконструкции циклической системы тегов в Правиле 110.
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ 110 — это число 110 , записанное в общепринятой десятичной системе счисления и, таким образом, произносится так, как обычно произносятся номинальные числа . Например, Стивен Вольфрам произносит название «правило один-десять». [1]
Ссылки
[ редактировать ]- ^ Стивен Вольфрам (2003). Новый вид науки — Стивен Вольфрам . Телевидение Калифорнийского университета (UCTV). Событие происходит в 9:51 . Проверено 19 июня 2023 г.
- ^ Перейти обратно: а б с д Кук (2004) .
- ^ Wolfram Research Inc. против Кука (2:00-cv-09357) (иногда упоминается как «Wolfram Research Inc. против Мэтью Кука. 8/31 CV00-9357 CBM»)
- ^ Джайлз (2002) .
- ^ Вольфрам (2002) , стр. 169, 675–691.
- ^ Вольфрам (2002) , с. 229
- ^ Нири и Вудс (2006) .
- ^ Мартинес, Хенаро Дж.; Сек Туох Мора, Хуан; Чапа, Серджио; Леметр, Кристиан (апрель 2019 г.). «Краткие заметки и исторические вычисления в Мексике за 50 лет» . Международный журнал параллельных, новых и распределенных систем . 35 (2): 185–192. arXiv : 1905.07527 . дои : 10.1080/17445760.2019.1608990 . S2CID 150262966 . Проверено 15 апреля 2020 г.
Цитируемые работы
[ редактировать ]- Кук, Мэтью (2004). «Универсальность в элементарных клеточных автоматах» (PDF) . Сложные системы . 15 :1–40.
- Джайлз, Джим (2002). «Что это за наука?» . Природа . 417 (6886): 216–218. Бибкод : 2002Natur.417..216G . дои : 10.1038/417216a . ПМИД 12015565 . S2CID 10636328 .
- Нири, Терлоу; Вудс, Дэмиен (2006). «П-полнота клеточного автомата Правило 110». В Бульези, Микеле; Пренил, Барт; Сассоне, Владимиро; Вегенер, Инго (ред.). Автоматы, языки и программирование: 33-й международный коллоквиум, ICALP 2006, Венеция, Италия, 10–14 июля 2006 г., Материалы, часть I. Конспекты лекций по информатике. Том. 4051. Спрингер. стр. 132–143. дои : 10.1007/11786986_13 .
- Вольфрам, Стивен (2002). Новый вид науки . Вольфрам Медиа. ISBN 1-57955-008-8 .
Дальнейшее чтение
[ редактировать ]- Кук, Мэтью (2008). «Конкретный взгляд на вычисления по правилу 110». В Нири, Т.; Вудс, Д.; Седа, АК; Мерфи, Н. (ред.). Сложность простых программ . Электронные труды по теоретической информатике. Том. 1. С. 31–55. arXiv : 0906.3248v1 . дои : 10.4204/EPTCS.1.4 . S2CID 10266058 .
- Мартинес, Хенаро Х.; Адамацкий А.; Чен, Фангюэ; Чуа, Леон (2012). «О солитонных столкновениях между локализациями в сложных элементарных клеточных автоматах: правила 54, 110 и далее». Сложные системы . 21 (2): 117–142. arXiv : 1301.6258 . дои : 10.25088/ComplexSystems.21.2.117 . S2CID 10165042 .
- Мартинес, Хенаро Х.; Адамацкий А.; Стивенс, Кристофер Р.; Хёфлих, Алехандро Ф. (2011). «Клеточно-автоматные суперколлайдеры» . Межд. Дж. Мод. Физ. С. 22 (4): 419–439. arXiv : 1105.4332 . Бибкод : 2011IJMPC..22..419M . дои : 10.1142/S0129183111016348 . S2CID 7508070 .
- Мартинес, Хенаро Х.; Макинтош, Гарольд В .; Мора, Хуан КСТ; Вергара, Серджио ВК (2003–2008). «Воспроизведение систем циклических тегов, разработанных Мэтью Куком с помощью правила 110, с использованием фаз fi_1» (PDF) . Журнал клеточных автоматов . 6 (2–3): 121–161.
- Мартинес, Хенаро Х.; Макинтош, Гарольд В .; Мора, Хуан КСТ; Вергара, Серджио ВК (2008). «Определение регулярного языка с помощью структур на основе планера, называемых фазами fi_1 в Правиле 110». Журнал клеточных автоматов . 3 (3): 231–270. arXiv : 0706.3348v1 . Бибкод : 2007arXiv0706.3348J .
- Мартинес, Хенаро Х.; Макинтош, Гарольд В .; Мора, Хуан КСТ; Вергара, Серджио ВК (2007). «Правило 110, основанное на столкновениях объектов и других конструкций» (PDF) . Журнал клеточных автоматов . 2 (3): 219–242.
- Мартинес, Хенаро Х.; Макинтош, Гарольд В .; Мора, Хуан КСТ (2006). «Планеры в Правиле 110» (PDF) . Межд. Дж. Нетрадиционных вычислений . 2 : 1–49.
- Мартинес, Хенаро Х.; Макинтош, Гарольд В .; Мора, Хуан КСТ (2003). «Производство планеров путем столкновений в Правиле 110» (PDF) . Достижения в области искусственной жизни . Конспекты лекций по информатике. Том. 2801. стр. 175–182. дои : 10.1007/978-3-540-39432-7_19 . ISBN 978-3-540-20057-4 .
- Мартинес, Хенаро Х.; Макинтош, Гарольд В. (2001). «АТЛАС: Столкновения планеров как фазы эфира в правиле 110» .
- Макинтош, Гарольд В. (1999). «Правило 110 в отношении наличия планеров» (PDF) .
- Макинтош, Гарольд В. (2002). «Правило 110 универсально!» (PDF) .
Внешние ссылки
[ редактировать ]