Семинар лаборатории теоретической информатики: "Solving equations in sequences", Глеб Погудин

25 сентября на семинаре лаборатории теоретической информатики состоится доклад Глеба Погудина "Solving equations in sequences". 

Abstract: 

Consider any recurrence relation, for example, the one for Fibonacci numbers: $f_{n + 2} = f_{n + 1} + f_n$. One can think of this equations as a relation between the sequence itself and its shifts. A natural general framework that would incorporate equations of this sort would be a language including not only arithmetic operations, but also a shift operator S. In this language, the above recurrence will recast to $S^2(f) = S(f) + f$. Many questions about nonlinear recurrences and discrete-time dynamical systems can be stated as questions about solutions of equations in this extended language (so-called difference equations) in the ring of sequences. In 2007, Hrushovski and Point showed that the first order theory of sequences in this language is undecidable, that is, there is no algorithm for verifying correctness of first-order formulas. On the other hand, in our recent work with A. Ovchinnikov and T. Scanlon, we have shown that the problem of determining existence of a solution of a system of difference equations in the complex-valued sequences is decidable. In the talk, I will describe this decidability result as well as undecidability results from our recent preprint with T. Scanlon and M. Wibmer that show that almost all reasonable extensions of the consistency problem are, in fact, undecidable including determining the existence of a solution in real-valued sequences and membership problem for radical difference ideals.