Dishonest Representations

The complexity attributed to the computation of a function f over some abstract domain A, say graphs, is normally measured in terms of resources required by its best implementation on some particular model of computation, most commonly the random access machine (RAM). This implementation, however, computes a function f over some concrete domain C, say binary strings, rather than A. So, prior to considering the cost of running f, one should first establish that f does actually implement f .

However, there is little meaning to a claim that a single function f over some domain C implements the intended function f over domain A without also specifying how the two domains are related. The following definition is common.[1]

Definition 6.1 (Simulation [single-valued representation]) A concrete (partial) function f : C ^ C simulates an abstract (partial) function f : A ^ A with respect to a particular injective representation p : A —^ C if p(f (x)) = f (p(x)) for all x e A. [In the case of partial functions, we also demand that f (p (x)) be undefined whenever f (x) is.]

One clearly needs to require, as we have, that a representation be injective. Otherwise, any and all functions could be simulated by the identity function with respect to a representation that maps the whole abstract domain to a single constant.

The above definition will be extended to functions with arity wider than 1 and multivalued representations in Definitions 6.2 and 6.4 below. Figure 6.1 depicts the multivalued case.

Fig. 6.1 The function f simulates the function f via a representation p between their domains

The choice of representation can make all the difference in the world. If one is not honest, then a computable function can end up implementing an incomputable one by getting the representation itself to do the bulk of the work.

Example 6.1 Consider any standard enumeration TMm, m = 0, 1,..., of Turing machines, and define the following incomputable functions over the natural numbers N:

  • h : N ^ N enumerates (the numerical “codes” of) those machines that halt on the empty tape;
  • h : N ^ N enumerates those that do not.

So h(N) Ы hi (N) = N, where h(N) is the image {h (n) | n e N} of h and h(N) is the

image of hi. Then the incomputable function

is implemented by the computable parity function (n mod 2) under the following bijective representation:

We have

as required. ?

The problem with the above “implementation” of the halting function obviously lies in the representation, which clearly gives the impression of itself doing the (computationally) impossible.

  • [1] Allowing different representations for input and output, as in “A more general notion of simulationis obtained if we let drop the requirement that R® and R® have the same input and output sets....R® can be weakly simulated on R® if there exist such E and D with the property that for eachprogram П1 for R® there exists a program n on R® such that DR®E = R® ” [14, p. 21], canlead—if one is not careful—to the same kinds of problems we will encounter in Sect. 6.9.
< Prev   CONTENTS   Source   Next >