Page 24

		2.8 Definition A recursive function s is a program size measure for v if and only if there exists a recursive function bound such that, for all  n -programs p and all , if , then .

		Clearly, and are examples of program size measures. Blum [20] showed that all program size measures are equivalent in the following sense.

		2.9 Theorem Suppose s and s' are both program size measures for v. Then there is a recursive function h such that, for all p,

		and .

		Thus, for recursively invariant results concerning program size (which is all that we will be concerned with in this book), the choice of program size measure does not matter. Therefore, for simplicity we take the size of  n -program p to be just p itself. For each partial recursive function  a , we define MinProg n ( a ) to be the least number p such that  n p =  a . Also, for each language L, we define MinGram n (L) to be the least number i such that .

		Dynamic Program Complexity.

		A two-place partial recursive function  F  is a complexity measure (Blum [19]) for  j  if and only if  F  satisfies the two Blum axioms:

		(i) For all p, .

		(ii) The predicate is recursively decidable.

		By convention, for all p,  F p denotes . Intuitively,  F p(x) is the amount of some dynamic resource used by  j -program p in computing  j p(x). Here is an example. Suppose  j  is an acceptable programming system based on deterministic multi-tape Turing Machines, and suppose  F (p, x) is the number of instructions the Turing Machine coded by p executes on input x, where  F (p, x) is undefined if the Turing Machine fails to halt on input x. Then  F  satisfies the Blum axioms. Blum showed that complexity measures are all equivalent in the following sense.

		2.10 Theorem Suppose  F  and  F ' are complexity measures for  j  Then, there is a recursive function h such that, for all p and all but finitely many x,

		and .

		Thus, for recursively invariant results concerning computational complexity (which is all that we will be concerned with in this book), the choice of complexity measure does not matter. Thus,  F  will denote a fixed, arbitrary complexity measure.