n^n is not poly-recursive

Speaker(s)

Michał Pilipczuk

Affiliation

Uniwersytet Warszawski

Date

Oct. 30, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---