A specialized recursive language for capturing time-space complexity classes

We provide a resource-free characterization of register machines that computes their output within polynomial time O(n^k), by defining our version of predicative recursion and a related recursive programming language. Then, by means of some restriction on composition of programs, we define a programming language that characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously. A simple syntactical analysis allows us to evaluate the complexity of a program written in these languages.