Правило 110

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Анімація правил одновимірного клітинного автомата Правило 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.