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

[GlukKazan]

Ковры Вана

[Deosis]

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

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