Клеточные автоматы в гипотезе Коллатца

У меня есть клеточный автомат , который из любого начального целого числа (начальное состояние автомата) генерирует состояния последовательностей Коллатца. Окрестность автомата имеет форму L-тетромино (включая два временных состояния). (Спокойный) фон представлен как 0 (состояние ноль). Другой 1 -state (включено) формирует активную границу с левой стороны при генерации автомата. Граница представляет собой интересную часть, потому что именно здесь «точное» поколение либо увеличивается (нечетное), либо остается (нечетное), либо уменьшается (четное). Мой предыдущий пост по этому вопросу был закрыт из-за того, что мой вопрос неясен.

Я обнаружил, что если я смогу написать статью об этом (или попросить кого-нибудь помочь мне написать ее — помочь мне с терминологией и т. д.), мы могли бы представить ( 3 н + 1 ) проблема Коллатца с клеточным автоматом (или адаптивным клеточным автоматом), и кто-то может подойти к проблеме с этой точки зрения; как, например, Мэтью Кук доказал, что Правило 110 было полным по Тьюрингу (т.е. универсальным); и студент из Великобритании доказал, что 2 , 3 Машина Тьюринга была универсальной. У меня есть ощущение, что мы могли бы выяснить, верна ли эта гипотеза, ложна или недоказуема, решая некоторые свойства этого автомата.

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

Об автомате: я думаю, что конвергенцию трудно доказать в сотовом автомате, но это может быть возможно в зависимости от соседства, правил и, возможно, настройки CA. Я думаю, может быть, доказательство того, что пути, по которым идет окрестность (функция перехода), достигают некоторой границы (или нет), докажет, что гипотеза верна или нет. Мне трудно на самом деле описать, что я имею в виду по этому поводу. Пожалуйста, если кто-нибудь пробовал это раньше? Я хотел бы услышать больше об этом. Кто-нибудь, как знает об информации, или документ об этом конкретно я хотел бы знать.

Мой вопрос; существует ли уже гипотеза о Коллатце в форме клеточного автомата, и такая, что если что-то о ней может быть доказано как истинное или ложное, оно также докажет, истинна или ложна исходная гипотеза?

Спасибо

Пример пространственно-временной диаграммы клеточного автомата, показывающей только нечетные числа (без учета правила сдвига вправо):

введите описание изображения здесь

Возможно, вы уже пробовали поиск в Google и нашли, например, вопрос CS StackExchange 11611 «Какова «ближайшая» проблема к гипотезе Коллатца, которая была успешно решена?».
Нет, эти вещи представляют интерес. Спасибо.
FWIW, это все еще довольно неясно - вы соединили слова «гипотеза Коллатца» и «клеточный автомат», но на самом деле вы вообще не определили свой автомат и не объяснили, как, по вашему мнению, он моделирует проблему Коллатца. Здесь было бы очень полезно быть более конкретным, возможно, с примером.
Извини. Я постараюсь описать это лучше завтра, так как я скоро иду спать. Я могу кратко описать это, сперва в нескольких словах. Он моделирует проблему Коллатца следующим образом: каждая конфигурация, которую генерирует ЦС, производит следующее целое число в последовательности. По двоичным значениям, как и в правиле 110, он выводит результат с левой стороны, поэтому самый значащий бит находится в крайнем левом углу, где находится последний бит «1». Как и любая другая функция Коллатца, каждая итерация равна каждой CA-конфигурации. CA представляет собой 2-состояние 4-состояния соседства (L-образный с 2-временными состояниями одновременно).
Это только одно из 65 536 правил, порождающих (3n+1) последовательность Коллатца. Таким образом, функция перехода состояний уникальна. Но когда выход четный, правило меняется на правило сдвига вправо, так что четные числа всегда переходят в нечетные числа. так что справа есть граница состояния «1» (аналогично правилу 110 с одной черной ячейкой). Мы должны изменить функцию перехода, когда конфигурация (наименьший значащий бит) имеет другую четность. Но автомат в этом отношении довольно прост.
@NaturalNumberGuy «Простой», но из-за этого он перестает быть клеточным автоматом. В самом деле, я не думаю, что существует ЦС, который может работать с двоичным представлением числа. н производить н + 1 , по тонкой, но жизненно важной причине: ЦС по своей природе действуют локально ; значение ячейки в новом поколении может зависеть только от значений фиксированной конечной окрестности ячеек в предыдущем поколении (поколениях). Но такие операции, как сложение и умножение (не в степени двойки), изначально нелокальны в двоичных представлениях; они могут зависеть от битов сколь угодно далеко. (Считайте 111111+1)
@Steven Stadnicki: Это зависит от того, как вы настроили свой ЦС. Я знаю, что это работает локально, но то же правило применяется ко «всей» решетке. Я сделал двоичный сумматор с переносом один раз, используя те же идеи. Назовете ли вы это СА, машиной Тьюринга или как-то иначе, не имеет значения, важны операции, которые вы делаете. Кажется, мне никто не верит. 3 н + 1 просто, я уже дал примерное описание того, как я это сделал. Это делается так же, как и любая другая логическая операция, вы получаете логические вентили из правила. Однако написать статью об этом сложно, потому что я чувствую, что текст должен быть более формальным.

Ответы (1)

Задачу Коллатца можно еще проще сопоставить с клеточным автоматом по основанию 6, потому что деление на 2 по основанию 6 очень похоже на умножение на 3, и нет проблемы каскадных переносов. Довольно легко создать автомат с 7 состояниями, окрестность которого — это просто две соседние клетки в предыдущем поколении. 7 состояний соответствуют 6 цифрам основания 6, а нулевое состояние обозначает края вычислений. Кто-то закодировал представление гипотезы Коллатца в виде клеточного автомата с основанием 6 на сайте wolfram.com в 2011 году: https://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/

Клеточные автоматы в гипотезе Коллатца
СпросиСетьПолитика конфиденциальности1y, 0v