Neural dynamical systems with stable attractor structures such as point attractors and continuous attractors are widely hypothesized to underlie meaningful temporal behavior that requires working memory. However, perhaps counterintuitively, having good working memory is not sufficient for supporting useful learning signals that are necessary to adapt to changes in the temporal structure of the environment. We show that in addition to the well-known continuous attractors, the periodic and quasi-periodic attractors are also fundamentally capable of supporting learning arbitrarily long temporal relationships. Due to the fine tuning problem of the continuous attractors and the lack of temporal fluctuations, we believe the less explored quasi-periodic attractors are uniquely qualified for learning to produce temporally structured behavior. Our theory has wide implications for the design of artificial learning systems, and makes predictions on the observable signatures of biological neural dynamics that can support temporal dependence learning. Based on our theory, we developed a new initialization scheme for artificial recurrent neural networks which outperforms standard methods for tasks that require learning temporal dynamics. Finally, we speculate on their biological implementations and make predictions on neuronal dynamics.