Правило 110
Правило 110 — елементарний одновимірний клітинний автомат з поведінкою, яка перебуває на кордоні хаосу і стабільності. В цьому відношенні Правило 110 ідентично грі «Життя». Відомо, що Правило 110 є Тьюринг-повним, що означає, що будь-яка обчислювальна процедура може бути реалізована за допомогою цього клітинного автомата.
Історія
Меттью Кук представив свій доказ на конференції Інституту Санта-Фе у 1998 році, але Стівен Вольфрам заборонив включати цей доказ в паперову версію матеріалів конференції, бо не хотів, щоб воно було опубліковано до видання книги A New Kind of Science. У 2004 році доказ Кука було опубліковано в журналі Вольфрама «Комплексні системи» (випуск 15, том 1), через 10 років після того як Кук вперше представив його.
Визначення
В найпростіших клітинних автоматах одновимірний масив нулів і одиниць оновлюється відповідно до набору простих правил. Значення клітини на наступному кроці залежить від значень клітин-сусідів на поточному кроці і значення самої клітини. Для Правила 110 має місце наступний набір правил:
| Поточний стан | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Новий стан центральної клітини | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Найменування Правило 110 названо правилом тому, що бінарна послідовність 01101110 при перекладі в десяткову систему дасть число 110.