Некоторые алгоритмически неразрешимые проблемы, связанные с автоматными и самоподобными группами.

Несмотря на простоту своего задания, автоматные группы могут обладать весьма нетривиальными свойствами – например, среди них были найдены контрпримеры к неограниченной проблеме Бернсайда, группы промежуточного роста и аменабельные группы, не являющиеся элементарными аменабельными. Несмотря на то, что проблема равенства слов в автоматных группах алгоритмически разрешима, существование алгоритмов для многих других проблем (например, для проблемы распознавания конечности группы) остаётся открытым вопросом.
В совместной работе докладчика и Laurent Bartholdi была показана алгоритмическая неразрешимость ряда проблем, в частности, были построены автоматное действие группы на бесконечном дереве с неразрешимой проблемой распознавания конечности орбиты луча и (независимо с Pierre Gillibert) автоматная группа с неразрешимой проблемой распознавания конечности порядка элемента. Также в более широком классе самоподобных групп была построена группа с неразрешимой проблемой равенства слов.
Все самоподобные группы являются финитно аппроксимируемыми, и некоторые из вышеупомянутых задач имеют простую комбинаторную интерпретацию. Например, задача распознавания конечности порядка элемента автоматной группы эквивалентна следующей: Пусть в клетках бесконечной вправо ленты стоят буквы алфавита A. Машина Тьюринга, стартующая в начале ленты и двигающаяся только вправо, задаёт преобразование $A^\mathbb{N} \to A^\mathbb{N}$, и ставится вопрос, даёт ли какая-нибудь итерация этого преобразования тождественное