1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 50
Текст из файла (страница 50)
Indeed, we define next a subtleroperation on functions, corresponding to the familiar computational primitiveof unbounded iteration -essentially the while loop. As we shall see, unboundediteration does introduce the possibility that the result may not be a function.Definition 4.7.2: Let 9 be a (k + 1)-ary function, for some kminimalization of 9 is the k-ary function f defined as follows:f(nl, ...
,nk) = {the least m such t.hat g(nl, .. " nk, m)if such an m eXIsts:o otherwise.> O. The= 1,We shall denote the minimalization of 9 by JL m[g(nl,"" nk, m) = 1].2394.7: Numerical FunctionsAlthough the minimalization of a function 9 is always well-defined, there isno obvious method for computing it ---even if we know how to compute g. Theobvious methodm:=O;while g(nl,"" nk, m)output mi- 1 do m:= m+ 1;is not an algorithm, because it may fail to terminate.Let us then call a function 9 minimalizable if the above method alwaysterminates. That is, a (k + 1)-ary function 9 is minimalizable if it has thefollowing property: For every nl, ...
, nk E N, there is an mEN such thatg(nl, ... , nk, m) = l.Finally, call a function fL-recursive if it can be obtained from the basicfunctions by the operations of composition, recursive definition, and minimalization of minimalizable functions.Note that now we cannot repeat the diagonalization argument of example4.7.5 to show that there is a computable function that is not fL-recursive. Thecatch is that, given a purported definition of a fL-recursive function, it is notclear at all whether indeed it defines a fL-recursive function -that is, whether allapplications of minimalization in this definition indeed acted upon minimalizablefunctions!Example 4.7.6: We have defined an inverse of addition (the '" function), andan inverse of multiplication (the div function); but how about the inverse ofexponentiation -the logarithm? Using minimalization,t we can define the logarithm function: log(m, n) is the smallest power to which we must raise m + 2to get an integer at least as big as n + 1 (that is, log( m, n) = flogm+2 (n + 1)1;we have used m + 2 and n + 1 as arguments to avoid the mathematical pitfallsin the definition of logm n when m ::; 1 or n = 0).
The function log is defined asfollows:log(m, n) = fL p[greater-than-or-equal((m+ 2) tp, n+ 1)].Note that this is a proper definition of a fL-recursive function, since the functiong(m,n,p) = greater-than-or-equal((m + 2) t p,n + 1) is minimalizable: indeed,for any m, n ~ 0 there is p ~ 0 such that (m + 2)P ~ n -because by raising aninteger ~ 2 to larger and larger powers we can obtain arbitrarily large integers.<)We can now prove the main result of this section:tThe logarithm function can be defined without the minimalization operation,see Problem 4.7.2.
Our use of minimalization here is only for illustration andconvenience.240Chapter 4: TURING MACHINESTheorem 4.7.1: A function f : NkH N is p,-1'ec1l1'sive if and only if it isrecursive (that is, computable by a Turing machine),Proof: Only if: Suppose that f is a p,-recursive function. Then it is definedfrom the basic functions by applications of composition, recursive definition,and minimalization on minimalizable functions, We shall show that f is Turingcomputable.First, it is easy to see that the basic functions are recursive: vVe have seenthis for the successor function (Example 4.2.3), and the remaining functions onlyinvolve erasing some or all of the inputs.So, suppose that f : N k H N is the composition of the functions 9 : N< HN and hi, ...
, he : N k H N, where, by induction we know how to compute 9 andthe h;'s. Then we can compute f as follows (in this and the other cases we giveprograms in the style of random access Turing machine programs that computethese functions; it is fairly easy to see that the same effect can be achieved bystandard Turing machines):ml:= hl(nl, ... ,nk);'1n2 := h 2 (nl,'" ,Uk);mc := he(nl, ... , nd;output g(ml, . .. , me.Similarly, if f is defined recursively from 9 and h (recall the definition),then f(nl,' .. , nk, m) can be computed by the following program:v:=g(nl, ...,nk);if m = 0 then output velse for i := 1,2, ...
,m dov:= h(nl, ... ,nk,i-1,v);output v.Finally, suppose that f is defined as p, m[g(nl, ... , Uk, m)], where 9 is minimalizable and computable. Then f can be computed by t.he programm:=O;while g(nl, ... ,nk,m) -::j:. 1 do m:= moutput m+ 1;Since we are assuming the 9 is minimalizable, the algorithm above will terminateand output a number.We have therefore proved that all basic functions are recursive, and thatthe composition and the recursive definition of recursive functions, and the minimalization of minimalizable recursive functions, are recursive; we must conclude2414.7: Numerical Functionsthat all {t-recursive functions are recursive.
This completes the only if directionof the proof.If. Suppose that a Turing machine M=(K,~,IS, 8, {h}) computes a functionf is unary;the gelleral case is an easy extension (see Problem 4.7.5). We shall show that fis {t-recursive. We shall patiently define certain {t-recursive functions pertainingto M and its operation until we have accumulated enough materials to define fitself.Assume without loss of generality that K and ~ arc disjoint. Let b = I~I +IKI, and let us fix a mapping E from ~UK to {O, 1, ... , b-1}, such that E(O) = 0and E(l) = 1 -recall that, since M computes a numerical function, its alphabetmust contain 0 and 1.
Using this mapping, we shall represent configurations ofAl as integers in base-b. The configuration (q, ala2 ... ak ... an), where the ai'sare symbols in ~, will be represented as the base-b integer ala2 ... akqak+l ... an,that is, as the integerf :NHN -we are assuming for simplicity of presentation thatWe are now ready to embark on the definition of f as a {t-recursive function.Ultimately, f will be defined asf(n)= num(output(last(comp(n)))).num is a function that takes an integer whose base-b representation is a string ofO's and l's and outputs the binary value of that string. output takes the integerrepresenting in base b a halted configuration of the form to> U hw, and omits thefirst three symbols to> U h. comp(n) is the number whose representation in baseb is the juxtaposition of the unique sequence of configurations that starts withlto> U 8W, where w is the binary encoding of n, and ends with to> U hw , where Wi isthe binary encoding of f (n); such a sequence exists, since we are assuming thatM computes a function-namely, f.
And last takes an integer representingthe juxtaposition of configurations, and extracts the last configuration in thesequence (the part between the last to> and the end).Of course, we have to define all these functions. We give most of the definitions below, leaving the rest as an exercise (Problem 4.7.4). Let us startwith, well, last. We can define lastpos(n), the last (rightmost, least significant)position in the string encoded by n in base b where a to> occurs:lastpos(n) ={tm[equal(digit(m, n, b), E(tO») or equal(m, n)].Notice that, in order to make the function within the brackets minimalizable,we allowed lastpos(n) to be n if no to> is found in n. Incidentally, this is another242Chapter 4: TURING MACHINESsuperficial use of minimalization, as this function can be easily redefined withoutthe use of minimalization.
We can then define last(n) as rem(n, b t lastpos(n)).We could also define rest(n), the sequence that remains after the deletion oflast(n), as div(n, b t lastpos(n)).output(n) is simply rem(n, b t log(b '" 2, n '" 1) '" 2) -recall our conventionthat the arguments of log must be decreased by 2 and 1, respectively.The function num(n) can be written as the sumdigit(l, n, b) . 2+digit(2, n, b) ·2t 2 + ., .+digit(log(b '" 2, n '" 1), n, b) . 2 t log(b '" 2, n '" 1).This is a fL-recursive function since both the summand and the bound log(b '"2, n '" 1) are. Its inverse function, bin(n), which maps any integer to the stringthat is its binary encoding, encoded again in as a base-b integer, is very similar,with the roles of 2 and b reversed.The most interesting (and hard to define) function in the definition of f(n)above is comp(n), which maps n to the sequence of configurations of M thatcarries out the computation of f(n) -in fact, the base-b integer that encodesthis sequence.
At the highest level, it is justcomp(n) = fL m[iscomp(m, n) and halted(last(m))],(1)where iscomp(m, n) is a predicate stating that m is the sequence of configurationsin a computation, not necessarily halted, starting from I>~b(n). (Incidentally,this is the only place in this pmof in which minimalization is truly, inherentlyneeded.) Notice that the function within the brackets in (1) is indeed minimalizable: Since M is assumed to compute f, such a sequence m of configurations willexist for all n. halted(n) is simply equal(digit(log(b - 2, n '" 1) '" 2, n, b), E(h)).We leave the precise definition of iscomp as an exercise (Problem 4.7.4).It follows that f is indeed a wrecursive function, and the proof of thetheorem has been completed .•Problems for Section 4.74.7.1. Let f : N t--t N be a primitive recursive function, and define F: N t--t N byF(n) = f(f(f(··· f(n) ..
.))),where there are n function compositions. Show that F is primitive recursive.4.7.2. Show that the following functions are primitive recursive:(a) factorial(n) = nl.(b) gcd(m, n), the greatest common divisor of m and n.(c) prime(n), the predicate that is 1 if n is a prime number.(d) p(n), the nth prime number, where p(O) = 2, p(l) = 3, and so on.(e) The function log defined in the text.243References4.7.3. Suppose that f is a JL-recursive bijection from N to N. Show that its inverse,1-1, is also JL-recursive.4.7.4.
Show that the function iscomp described in the proof of Theorem 4.7.1 isprimitive recursive.4.7.5. Which modifications must be made to the construction in the proof of theif directions of Theorem 4.7.1 if M computes a function f : N k H N withk> I?4.7.6. Develop a representation of primitive recursive functions as strings in analphabet I: of your choice (see the next chapter for such a representationof Turing machines). Formalize the argument in Example 4.7.5 that not allcomputable functions can be primitive recursive.REFERENCESTuring machines were first conceived by Alan M.
Turing:o A. M. Turing "On computable numbers, with an application to the Entscheidungsproblem," Proceedings, London Mathematical Society, 2, 42 pp. 230- 265,and no. 43, pp. 544-546, 1936.Turing introduced this model in order to argue that all detailed sets of instructions thatcan be carried out by a human calculator can also be carried out by a suitably definedsimple machine. For the record, Turing's original machine has one two-way infinitetape and one head (see Section 4.5).
A similar model was independently conceived byPost; see"Finite Combinatory Processes. Formulation I," Journal of SymbolicLogic, 1, pp. 103-105, 1936.The following books contain interesting introductions to Turing machines:o E. L. Posto M. L. Minsky Computation: Finite and Infinite Machines, Englewood Cliffs,N.J.: Prentice-Hall, 1967.Introduction to Computability, Reading, ~1ass.: Addison-Wesley,o F. C.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
