Аннотация:
Доклад посвящён алгоритмической задаче проверки, является ли данный
набор квадратных целочисленных матриц базисом свободной полугруппы.
Доказано, что эта задача алгоритмически неразрешима уже для матриц
размера $3\times 3$, а для матриц $2\times 2$ этот вопрос открыт.
Эта задача также тесно связана с вопросом Эрдёша–Грэхэма о плотностях
орбит целочисленных линейных функций одной переменной, который возник
из исследования существования латинских квадратов чётных размеров,
и которая также остаётся нерешённой уже более 40 лет.
Будет рассказано о результатах докладчика в этих двух направлениях.
|
