This paper defines a new notion of bounded pseudorandomness for certain classes of sub-computable functions where one does not have access to a universal machine for that class within the class. In particular, we define such a version of randomness for the class of primitive recursive functions and a certain subclass of PSPACE functions. Our new notion of primitive recursive bounded pseudorandomness is robust in that there are equivalent formulations in terms of (1) Martin-L?f tests, (2) Kolmogorov complexity, and (3) martingales.
展开▼
