Free interpretation

III. PROGRAM SCHEMES - BASIC PROPERTIES A. HERBRAND OR FREE INTERPRETATIONS... 

A free interpretation, loosely speaking, is a minimal one - one in which we make as few decisions as possible in fulfilling the definition of an interpretation of P. In particular, we establish no relations whatsoever among members of the domain and establish no connections between objects, functions, and the values of functions on those objects, except those required by formal identity. Thus f(x,g(y,z)) must be equal to itself and must be the result of applying f to x and g(y,z) - but we assume that it is distinct from, say, g(f(x,x),y)) and that there is no relationship whatsoever between g(y,z) and f(x,x) or g(x,x). ... 

DEFINITION An interpretation I of a scheme P is a free interpretation (or Herbrand interpretation) of P if ... 

When we looked for an interpretation to make the scheme in Example II-3 diverge, we constructed a free interpretation of that scheme under which it diverged. In fact this was the correct procedure, as the next series of results we will show. 

Vfe distinguish between a path through a scheme P (which is any sequence of boxes, or addresses of instructions which follows the arrows from the START box) and an execution sequence (which is the series of addresses of instruction actually followed during sene computation under some interpretation). We now show that every execution sequence is the execution sequence of some computation under a free interpretation. 

I(T)(val(u, i),...,val(un,i)). Thus at each step we shall have the relation we desire at the conclusion (if it halts) and the computation on the free interpretation I will exactly parallel the original computation on interpretation I. ... 

Thus we must have Q(s,T,Q) n Q(s,T,l) = for each test T and so I is a legitimate free interpretation with the desired properties. ... 

Since any execution sequence must be an execution sequence under some free interpretation, any infinite execution sequence must be an infinite execution sequence under some free interpretation. So if P fails to halt for some interpretation and some input, there is a free interpretation under which it fails to halt. Thus we can characterize the condition of always halting in terms of consistent paths or in terms of halting under all free interpretations. 

A scheme P is always halting if and only if it halts everywhere under all free interpretations. 

By the definition of strong equivalence, (1) implies (2). Evidently (2) implies (3) since I, is a particular free interpretation. 

P and P are weakly equivalent if and only if for every free interpretation... 

Thus free interpretations will be one of our primary tools for handling such questions. Notice that in a free interpretation the domain is recursive and the functions assigned to function letters are recursive but the interpretations of the predicate letters my not be recursive. 

Let P be any program scheme. Using our algorithm for testing whether a path is an execution sequence, we construct a tree T(P) of all possible execution sequences for P under free interpretations. The tree T(P) may be finite or infinite our main result on the subject will say that T(P) is finite if and only if P is always halting. The nodes of T(P) are labelled with execution sequences. At level n (declaring the root or initial node to be at level 1)... 

Under any free interpretation I, the computation (P,I,X) never applies the same n-placed test T twice to the same n-tuple of members of U(P). ... 

Flowchart C in Example 1-3 is free. Every time P(u) is applied, the value of u in a free interpretation las been changed to a new one. The path which traces out the loop n times, n > 0, corresponds to a free interpretation with P(fn(x)) = TRUE but P(fk(x)> = FALSE for 0 < k < n-1. For similar reasons, the flowchart of Example II-l is clearly free. 

Since there is only one output variable, z, and all functions are monadic, at any given time at most one variable in the computation under a free interpretation can contain a value which ultimately affects the final output value. Since P is free, all paths are execution sequences under scane free interpretation. Thus if we concentrate on just the contents of that register which we believe will ultinately be transferred to z, and ignore other values, we cannot be trapped into following a "tad" path. If v is our "guessed" variable and we have stored the current value of v, that suffices. All continuations of the current path must be valid (consistent). 

This construction works because G is free and we are dealing with free interpretations. When we come to a test we can nondeterministically select either path - seme free interpretation will take either path. The final output under any free interpretation must be either f. -.f x for some input variable x or else for some constant o. In the first case, G guesses this will... 

The values of the IgCZ ) and Ig(T) are unimportant elsewhere and can be specified arbitrarily. It is clear that this correspondence works both ways - if I is a free interpretation such that for some m+1 > 2, I(Zk)(gm+ (x)) = 1 for... 

We stall stow that every liberal scheme is strongly equivalent to a free scheme. The converse is not true. Example III-5 contains a free scheme P which is not strongly equivalent to any liberal scheme. Under free interpretation I, if 2n+l = Min k > 3 k odd, I(T)(f (x)) - 0, then (P,I,x) halts with output (Ax), f2n+1(x)). To compute f n+1(x) and test it, we must first compute fn(x), and store it until f2n+l(x> is tested the time lag n+1 becomes arbitrarily large so either we need arbitrarily many registers - violating the definition of a program scheme - or else we must recompute fn(x) violating the definition of a liberal scheme. 

So case one is impossible the argument for case three is similar, using free interpretation I2 defined by I2 CQ) CE) = I(Q)(E) and IgCTXE) = TRUE for all E. The second case is impossible, since at this point val(u) = fn(x), ... 

The general approach will be to set up a 1-1 correspondence between free interpretations of schemes in S2 and infinite binary tapes. Obviously in a free interpretation of such a scheme (notice that Sn does not allow constants) only the values of T on f x) could affect the flow of computation and the ultimate output and so we can consider everything else to be fixed. Given an expression E of the form f Cx) and a free interpretation I, let... 

Now it is clear that given an infinite binary tape t there is a free interpretation on Sn for which t - t (x). The schemes in Sn that we shall use to establish our undecidability results will actually test only expressions of the farm f Vx) far m > 2 and so for all purposes a tape t can be considered to correspond to a "unique" (unique as far as concerns operation of the schemes in question) free interpretation I such that... 

LEMMA 6.5 The computation of P (M) under free interpretation I on input x ... 

---