Constructing New Families of Nested Recursions with Slow Solutions

Abstract

A recurring theme in nested recursions research has been the search for recursion families. By a recursion family we mean a collection of recursions with a common or at least highly similar structure, and where, with appropriate (but usually different) initial conditions for each recursion, their respective solutions behave similarly in key respects. Our key result is a general method for generating a family of recursions with slow solutions from any nested recursion of the form either $R(n)=R(n-s_1-R(n-a_1))+R(n-s_2-R(n-a_2))$ (a two-term generalized Conolly recursion) or $R(n)=R(n-s_1-R(n-a_1))+R(-t_1+R(n-b_1))$ (a generalized Conway recursion) so long as the recursion with which we start, together with its initial conditions, has a known slow solution. We apply this method to discover new families of recursions with slow solutions based on the well-known Hofstadter $V$ and Conway recursions, respectively.