Плитки Вана для симуляции машин Тьюринга

Если зафиксировать начальное состояние ленты, то просто получится последовательность пар (состояние ленты, состояние КА).
Если КА при заданном входе останавливается, то последовательность — конечная.

Если рассматривать все возможные входы, то получится ориентированный граф, где вершины — пары из абзаца выше.