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