Комментарии 4
Если зафиксировать начальное состояние ленты, то просто получится последовательность пар (состояние ленты, состояние КА).
Если КА при заданном входе останавливается, то последовательность — конечная.
Если рассматривать все возможные входы, то получится ориентированный граф, где вершины — пары из абзаца выше.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Плитки Вана для симуляции машин Тьюринга