Honest Universality

A (partial) function ш is said to be “universal” for a whole family F of (partial) functions (such as all the recursive functions, for instance) if it computes the whole family by being supplied with the code rf n of the desired f e F as an extra argument. If ш works with a concrete domain C, whereas the functions in F operate on an abstract domain A, then representations p : A ^ C are in order once again. Then we would say that varyadic ш is universal for F (with respect to encoding r-n : F ^ C and representation p : A ^ C) if

for all f e F and I e A* of the right length for the arity of f.

Another potential problem with the notion of universal function is that some models of computation—like Turing machines—do not take their inputs separately, but, rather, all functions are unary (string-to-string for Turing machines). In such cases, one needs to be able to represent pairs (and tuples) as single elements. One standard pairing function for the naturals is the injection (i, j) := 2‘ 3j. For strings, one usually uses an injection like (u, w) := u ; w, where “;” is some symbol not in the original string alphabet.

There are several ways to go. The pairing function could reside in the abstract domain A, or in the concrete domain C, or in the representation of A as C. Regardless, this need raises a critical issue. Unless we demand that pairing be effective, there could be an implementation of the universal function that does too much, computing even non-effective functions. For example, a naive definition might simply ask that pairing be injective and say that rn is universal for some set F of functions if f (x) = ш((гfn, x)) for all f e F and x e C, for some arbitrary encoding r-n : F ^ C of functions. The problem is that an injective pairing could cheat and include the answer in the “pair”. For Turing machines, say, the pair (u, w) might be represented as u ; w when machine u halts on input w and as u : w when it doesn’t. Better yet, one could map (rf n, y) ^ [f (y), rf n, y], where the square brackets are some ordinary tupling function for the domain. Then a putative universal machine could effortlessly “compute” virtually anything, computable or otherwise, just by reading the encoded input pair.

Davis [7] and, later, Rogers [20] proposed general definitions of universality for Turing machines and for partial-recursive functions, respectively. Both insist that pairing be effectively computable. But we are talking about models in which no function takes two arguments, so we might not have an appropriate notion of computable binary function at our disposal. To capture effectiveness of pairing in such circumstances, we demand the existence of component-wise successor functions. Given a “successor” function у for domain C (that is, C = {sn (x0)} for some x0 e C) and a pairing function (?, ?) : C x C C, the component-wise successor functions operate as follows: s1 : (a, b) ^ (s(a), b) and s2 : (a, b) ^ (a, s(b)).lfs, si, and s2 are all computable, then we will say that pairing is effective. This is because one can program pairing so that (z, y) := si (s2 (x0, x0)), where z = s1 (x0) and y = sj(x0). And if pairing is effective, then its two projections (inverses), 1st : (a, b) ^ a and 2nd : (a, b) ^ b, are likewise effective. (Generate all representations of pairs in a dovetailed, zig-zag fashion, until the desired one is located. What the projections do with non-pairs is left up in the air.)

Another concern is that requiring that pairing be computable is too liberal for the purpose. One does not really want the pairing function to do all the hard real work itself. For example, the mapping could include f (x) in the pair, even if it only can do that for f that are known to be total (like, for the primitive recursive functions, of which there are infinitely many), or all functions that halt within some recursive bound. That would make it a trivial matter to be universal for those functions—just transcribe the answer from the input.

Definition 6.8 (Honest Pairing) A pairing function is honest if it is effective and bijective.

This way, there is no room for hiding information.

For bijective pairing with computable projections, there is an effective means of forming a pair (a, b) by enumerating all of C until the two projections give a and b, respectively. With bijectivity alone, sans computability, one could still hide a fair amount of incomputable information in a bijective mapping. For instance, imagine that 0 is the code of the totality predicate and that the rest of the naturals code the partial-recursive functions in a standard order. Map pairs (i + 1, z) to 3(i, z), where (?, ?) is a standard pairing; map (0, z) to 3 j + 1 when z is the (code of the) jth total (recursive) function; and map (0, z) to 3k + 2 when z is the kth non-total (partial recursive) function. Now, let U be some standard computable universal function. Then, for y divisible by 3, ш(у) := U(y/3) would compute all the partial-recursive functions, whereas ш(у) := у = 1 (mod 3) would compute the incomputable totality predicate when у = (0, z) is not divisible by 3.

Definition 6.9 (Honest Universality) Let F be some family of unary functions over an abstract domain A. Unary function rn over concrete domain C is universal for F, via pairing function (?, ?) over C, if [ку.ш(а, у) a e C} implements F. If, in addition, pairing is bijective, then we call the universal function honest.

That is, rn is universal if, for fixed representation p : A ^ C and encoding r-n : F ^ C ,wehave ш(гf n, p(x)) = p( f (x )),for f e F and x e A. Of course, we are interested in the case where both pairing and the universal function are effectively computable.

Theorem 6.3 ([10]) Let F be some family of unary functions over a domain A, including generators and equality. Then, if there is a computable unary universal function (over any domain C)for F, via an effective pairing, then all the implemented functions in F are also computable.

Suppose F = {fz}z is some standard enumeration of (the definitions of) the partial-recursive functions. Based on Davis’s (second) definition of a universal Turing machine, which relies on a notion of effective mappings between strings and numbers, namely, recursive in Godel numberings, Rogers defines (in his third definition) what we may refer to as the universal property of a unary numerical function rn, namely, that fz(x) = n(rn(z, x)) for some recursive bijection n and effective (but perhaps dishonest) pairing (?, ?).

The following follows from the definitions:

Theorem 6.4 ([10]) If a function has the universal property, then it is honestly universal. Furthermore, there must exist an honest computable universal function.

< Prev   CONTENTS   Source   Next >