Ordinary complexity theory deals with computation over finitary inputs, typically represented as binary strings. In many settings, it is natural to consider computation over non-finitary inputs, for example real numbers, continuous functions, or even arbitrary functions. The study of computation in such settings has a long history, dating back to Turing's original work. Complexity in this setting has not been received as much attention. However, starting with work by Constable and Mehlhorn in the 1970s, the question of how polynomial time might be extended to more general settings has been addressed by a number of researchers. In this talk I will survey this work, with a focus on my own contributions, starting with work with S.A. Cook in the early 1990s, and concluding with more recent results with F. Steinberg and with E. Hainry, J.-Y. Marion and R. Pechoux. Along the way I will touch on other works and provide some motivation for the development of the theory.