Machine dependence of degrees of difficulty

One may define a degree-of-difficulty relation for total recursive functions by saying that/2:g (/ is at least as difficult as g) if, to each program for computing/, there corresponds a program for computing g such that g(x) takes no more steps to compute than f(x) for almost all x.2 Unfortunately, such an ordering is highly dependent on our choice of a mathematical model for a computer (cf.Hartmanis and Steams l, 111).It is the purpose of this note to so modify our degree-of-difficulty relation as to lessen this machine dependence.1. Monoid-induced machine equivalence.Let 5 be a monoid of 2variable functions, increasing for x and y positive.The associative multiplication is f*g(x,y) =/(*, g(x, y)), and 5 contains the identity e(x, y) =y.Let A and G be two partial recursive functions of a single variable.We say that A 5-bounds G iff F(x) defined implies G(x) defined, and there exists a function p(ES such that p(x, F(x)) 2:G(x) for almost all x for which A(x) is defined.A machine M may be thought of as supplied with a collection of programs P (t = l, 2, 3, ); (x).3(For a given partial recursive function /, there will, in general, be infinitely many i such that <,=/; cf. a universal Turing machine.)For such a machine M, we then say that