Понедельник, 20 октября, ауд. 106. Начало в 18:00.
Докладчик: Mika Hirvensalo (University of Turku).
Тема: Skolem's Problem - A Challenge for Decidability.
Abstract
In 1934, Norwegian mathematician Thoralf Skolem, better known from his results in mathematical logic, proved that the zero set of a linear recurrent sequence over integers is a union of a finite set and finitely many periodic sets. Later research has discovered that the finitely many periodic sets (i.e. a semilinear set) can be effectively constructed when the recurrence relation is given. However, characterization of the aforesaid finite set remains a long-standing open problem, and after 80 years of Skolem's result we do not know the decidability status of the following question: Given a linearly recurrent sequence over integers, does there exist a zero in the sequence. In this talk, I will give an overview of the problem and the recent progress on it.
