We study the space and time complexity of functions computable by simple loop-free programs operating on integers. In particular, we show that any function $f(x_1 , \cdots ,x_k )$ computable by a program using only comparison-based conditional forward branching instructions and the arithmetic operations $ + , - $, and truncating division by integer constants (such programs compute exactly the functions definable in Presburger arithmetic) can be computed by an off-line Turing machine in space $s(n)$ and time $n^2 /s(n)$ for any reasonable space bound $s(n)$ between $\log n$ and n. Moreover, the space-time trade-off is optimal.

It has long been known that deterministic 1-way counter machines recognize exactly all r.e. sets. Here we investigate counter machines with general recursive bounds on counter reversals. Our main result is that for bounds which are at least linear, counter reversal is polynomially related to Turing machine time, for both 1-way and 2-way counter machines and in both the deterministic and the nondeterministic cases. This leads to natural characterizations of the classes P and NP, and hence of the P =? NP question, on the counter machine model. We also establish reversal complexity hierarchies for counter machines, using a variety of techniques which include translation of Turing machine time hierarchies, padding arguments as well as more ad hoc counting arguments.