Математика Этерна
Открытый доступ

Абстрактный

Обратное проектирование машин Тьюринга и понимание гипотезы Коллатца.

Джон Никсон

В этой статье я расширил свою более раннюю работу [3] по малым машинам Тьюринга (TM), разработав метод получения рекурсивных определений неприводимых регулярных правил (IRR) для TM, когда явные формулы для них не могут быть получены. Это было проиллюстрировано двумя примерами. Первый пример был выбран случайным образом, а второй пример был разработан для моделирования гипотезы Коллатца. Анализ этой TM на основе ее IRR предложил новые подходы, которые могут быть основой для доказательства этой гипотезы. Метод включает в себя запуск TM в обратном направлении из набора конфигураций (CS). Это в общем случае создает дерево CS на каждом шаге. Цель состоит в том, чтобы найти CS y, которые достижимы из CS x, которая просто указывает символ, который должен быть прочитан, и состояние машины. Это означает, что следуя вычислению вперед от x, добавляя некоторые символы, когда это необходимо, в указатель, CS y может быть достигнута. Эти CS образуют основу LHS IRR.