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

Абстрактный

Методы понимания вычислений машины Тьюринга

Джон Никсон

Эта статья представляет собой ab initio исследование способов описания поведения машины Тьюринга (TM). Показано, как результаты для TM, ограниченной конечной длиной ленты, могут быть использованы для ускорения любого вычисления TM. Неизбыточный набор таких правил называется неприводимыми регулярными (вычислительными) правилами (IRR), и описан алгоритм для их генерации для любой TM для произвольной длины ленты. Этот алгоритм был реализован на C++, поскольку он свободно доступен. Изученные примеры показывают, что IRR может быть как конечным, так и бесконечным числом. Для нескольких TM, когда они бесконечны, были найдены рекурсивные формулы для них, и ожидается, что это всегда возможно. Эти формулы были найдены путем изучения IRR в каждом примере отдельно и правильного угадывания его и доказательства его по индукции. Таблица, показывающая, какие IRR следуют за другими в зависимости от следующего прочитанного символа, была найдена для изученных примеров и дает много информации о поведении TM. Ожидается, что таким образом можно будет проанализировать универсальную ТМ и выяснить, как работает цикл интерпретации.