Proper complexity function
A proper complexity function is a function f mapping natural numbers to natural numbers such that:
- f is nondecreasing;
- there exists a k-string Turing machine M such that on any input of length n, M halts after O steps, uses O space, and outputs f consecutive blanks.
Similar notions include honest functions, space-constructible functions, and time-constructible functions.