State, Polynomials, and Parallelism in a Time of Neural Sequence Modeling

Abstract: Is there an algorithm that learns the best fit parameters of a Transformer to any dataset?  If I trained a neural sequence model and promised you it is equivalent to a program, how would you even be convinced?  Modern RNN’s are functions that admit parallelizable recurrence; what is the design space of parallelizable recurrences?  Are there unexplored function families that lie between RNN’s and Transformers?  We explore these questions from first principles starting with state, polynomials, and parallelism.