Как выполняется правило 110 Тьюринга?

Я прочитал страницу Википедии для правила 110 в клеточных автоматах, и я более или менее знаю, как они работают (набор правил решает, где рисовать следующие 1 или 0).

Я только что прочитал, что они завершены по Тьюрингу, но я даже не могу понять, как бы вы «запрограммировали» «правило 110»?

Универсальность - это несколько неформальное понятие. Это примерно означает, что для каждой вычислимой функции в модели есть «программа» так что «запуск» на любом входе всегда «останавливает» и «выводит» правильный ответ. (Обратите внимание, что машины Тьюринга здесь не появляются: они являются лишь одним примером универсальной вычислительной модели.)P P $f$$P$$P$$x$

Процитированные слова - это те слова, которые необходимо определить. Для машин Тьюринга:

• Программа определяется как список состояний, магнитофона алфавита, начального состояния, конечных состояний и переходов.
• Запуск машины Тьюринга на входе означает, что мы инициализируем ленту с кодировкой и запускаем машину на этой ленте в соответствии с обычными правилами.х х $T$ $x$$x$$T$
• Машина Тьюринга останавливается, если достигает конечного состояния. (Здесь есть несколько вариантов.)
• То, что выводит машина Тьюринга (если она останавливается), является содержимым ленты.

Правило 110, как вычислительная модель, должно быть определено формально таким же образом. Определение является разумным, если можно вычислить вычислительную модель вычислительной модели в следующем смысле: существует вычислимая функция такая, что для каждой программы и ввода (оба кодируются как натуральные числа) останавливается тогда и только тогда, когда останавливается на , и если останавливается, то его вывод идентичен выводу на .P x S ( P , x ) P x S ( p , x ) P $S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Если вас интересует конкретная настройка правила 110 в качестве вычислительной системы, я предлагаю вам взглянуть на статью Мэтью Кука, в которой доказывается универсальность правила 110 (точнее, вычислительной системы, построенной на основе правила 110).

Что касается других правил, таких как правило 30 и правило 90, мы не знаем, что они не являются универсальными. Вокруг них могут быть построены убедительные вычислительные системы, которые являются универсальными, но мы просто не знаем ни о каких.

Из доказательства Мэтью:

Используемый здесь подход заключается не в том, чтобы разработать новый клеточный автомат, а в том, чтобы выбрать самый простой, который естественным образом демонстрирует сложное поведение, и посмотреть, сможем ли мы найти в этом сложном поведении способ заставить его делать то, что мы хотим. Мы не будем непосредственно касаться таблицы поиска, приведенной выше, но вместо этого мы рассмотрим поведение, которое естественным образом проявляется в действии автомата во времени.

Сначала автор доказывает, что «система тегов», которая удаляет 2 символа на каждом шаге, является универсальной путем компиляции машинной программы Тьюринга с 2 состояниями. После этого он доказывает, что система планеров действительно может реализовать систему тегов. Это пошаговый процесс. Затем он изучает космическое время CA-110, чтобы найти планеры и правильно привязать их к системе планеров.

Теперь на ваш вопрос: как бы вы «запрограммировали» «правило 110»?

1. Найдите простейшую машину Тьюринга с двумя состояниями и найдите ленты с основными операциями ИЛИ, И, XOR, НЕ .

2. Скомпилируйте их в систему тегов.

3. Скомпилируйте реализацию системы тегов в реализацию планера.

4. Правильно адаптируйте его к планерам CA-110, и вы получите базовые операции в клеточных автоматах.

Шаги с 1 по 4 выполняются только один раз. Оттуда вычисление сводится к сумме чисел с использованием логических элементов.$1+1=2$

Примечание в сторону. Планеры - это особые конструкции. Операции будут рассматриваться как частицы, движущиеся и сталкивающиеся (планеры), генерирующие различный выходной сигнал в зависимости от того, как эти планеры начинаются или сталкиваются.