n^n is not poly-recursive

Prelegent(ci)

Michał Pilipczuk

Afiliacja

Uniwersytet Warszawski

Termin

30 października 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

A sequence (a_n)_{n\geq 0} is poly-recursive if there is a finite set of sequences,
one of them being (a_n)_{n\geq 0}, which can be defined using a system of recursive equations of the following form:
the nth entry of each sequence is equal to a polynomial of the (n-1)st entries of all the sequences.
We prove that the sequence a_n = n^n is not poly-recursive.

This is a joint work with Michaël Cadilhac, Charles Paperman, Filip Mazowiecki, and Géraud Sénizergues.

---