1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

After all, mn is 1 if n = 0, andotherwise it is m· m n-I. Multiplication itself can be defined recursively in termsof addition -and so on.In principle, we should be able to start with functions from natural numbers to natural numbers that are so simple that they will be unequivocallyconsidered computable (e.g., the identity function and the successor functionsucc(n) = n + 1), and combine them slowly and patiently through combinatorsthat are also very elementary and obviously computable -such as compositionand recursive definition- and finally get a class of functions from numbers tonumbers that are quite general and nontrivial. In this section we shall undertakethis exercise.

Significantly, the notion of computation thus defined will then beproved identical to the notions arrived at by the other approaches of this chapter -Turing machines, their variants, and grammars- that are so different inspirit, scope, and detail.Chapter 4: TURING MACHINES234Definition 4.7.1: We start by defining certain extremely simple functions from(a O-ary function is, of course, a constant,as it has nothing on which to depend). The basic functions are the following:(a) For any k ~ 0, the k-ary zero function is defined as zerok(nl,"" nk) =for all nl, ... , nk E N.(b) For any k ~ j > 0, the jth k-ary identity function is simply the functionidk,j(nl, ...

,nk) = nj for all nl, ... ,nk EN.(c) The successor function is defined as succ(n) = n + 1 for all n E N.Next we introduce two simple ways of combining functions to get slightlymore complex functions.(1) Let k, € ~ 0, let 9 : Nk H N be a k-ary function, and let hI"", hk be€-ary functions. Then the composition of 9 with hI, ... , hk is the €-aryfunction defined asNk to N, for various values of k ~°°(2) Let k ~ 0, let 9 be a k-ary function, and let h be a (k + 2)-ary function.Then the function defined recursively by 9 and h is the (k + 1)-aryfunction f defined asf(nl, ... ,nk,O) = g(nl, ... ,nk),f(nl, ...

,nk,m+ 1) =h(nl, ... ,nk,m, f(nl, ... ,nk,m))for all nI, ... ,nk,m EN.The primitive recursive functions are all basic functions, and all functions that can be obtained by them by any number of successive applications ofcomposition and recursive definition.Example 4.7.1: The function plus2, defined as plus2(n) = n+2 is primitiverecursive, as it can be obtained from the basic function succ by composition withitself.

In particular, let k = € = 1 in (1) of Definition 4.7.1, and let 9 = hi = succ.Similarly, the binary function plus, defined as p!us(m, n) = m + n is primitive recursive, because it can be recursively defined from functions obtainedby combining identity, zero, and successor functions. In particular, in Part 2of Definition 4.7.1 set k = 1, take 9 to be the idl.1 function, and let h be theternary function h(m, n, p) = succ(id 3,3(m, n, p)) -the composition of succ withid 3,3. The resulting recursively defined function is precisely the plus function:plus(m,O)plus(m, n= m,+ 1) = succ(plus(m, n)).4.7: Numerical Functions235Why stop? The function multiplication mult(m, n) = m· n is defined recursivelyasmult(m,O) = zero(m),mult(m, n+ 1)= plus(m, mult(m, n)),and the function exp(m, n) = mn is defined asexp(m,O) = succ(zero(m)),+ 1)exp(m, n= mult(m, exp(m, n)).Hence all these functions are primitive recursive.All constant functions of the form f(nl, ... , nk) = 17 are primitive recursive,since they can be obtained by composing an appropriate zero function withthe succ function, in this example seventeen times.

Also, the sign functionsgn(n), which is zero if n = 0, and otherwise it is one, is also primitive recursive:sgn(O) = 0, and sgn(n + 1) = l.For better readability, we shall henceforth use m + n instead of plus(m, n),m . n instead of mult(m, n), and m t n instead of exp(m, n). All numericalfunctions such asm· (n + m 2 ) + 178 mare thus primitive recursive, since they arc obtained from the ones above bysuccessive compositions.Since we are confined within the natural numbers, we cannot have truesubtraction and division. However, we can define certain useful functions alongthese lines, such as m ~ n = max{m - n, O}, and the functions div(m, n) andrem(m, n) (the integer quotient and remainder of the division of m by n; assumethat they are both 0 if n = 0).

First define the predecessor function:pred(O) = 0,pred(n+ 1) = n,from which we get our "nonnegative subtraction" functionm~O=m,m~n+1=pred (m~n).The quotient and remainder functions will be defined in a subsequent example.OIt is rather clear that we can calculate the value of any primitive recursivefunction for given values of its arguments. It is equally self-evident that we cancalculate the validity of assertions about numbers such asm .n> m 2 + n + 7,Chapter 4: TURING MACHINES236for any given values of m and n. It is convenient to define a primitive recursivepredicate to be a primitive recursive function that only takes values 0 and1.

Intuitively, a primitive recursive predicate, such as greater-than(m, n), willcapture a relation that mayor may not hold between the values of m and n.If the relation holds, then the primitive recursive predicate will evaluate to 1,otherwise to O.Example 4.7.2: The function iszero, which is 1 if n = 0, and 0 if nprimitive recursive predicate, defined recursively thus:> 0, is a= 1,iszero(m + 1) = O.iszero(O)Similarly, isone(O) = 0, and isone(n + 1) = iszero(n). The predicate positive(n)is the same as the already defined sgn(n). Also, greater-than-or-equal(m, n),written m ;::: n, can be defined as iszero(n '" m). Its negation, less-than(m, n)is of course 1 '" greater-than-or-equal(m, n).

In general, the negation of anyprimitive recursive predicate is also a primitive recursive predicate. In fact,so are the disjunction and conjunction of two primitive recursive predicates:p(m,n) or q(m,n) is 1 '" iszero(p(m,n) + q(m,n)), and p(m,n) and q(m,n) is1 '" iszero(p(m, n) . q(m, n)). For example, equals(m, n) can be defined as theconjunction of greater-than-or-equal(m, n) and greater-than-or-equal(n, m).Furthermore, if f and g are primitive recursive functions and p is a primitiverecursive predicate, all three with the same arity k, then the function definedby casesif p(nl,"" nk);otherwiseis also primitive recursive, since it can be rewritten as:As we shall see, definition by cases is a very useful shorthand.OExample 4.7.3: We can now define div and rem.rem(O, n) = 0,rem (m+ 1, n)= { 0 () 1rem m,n +if equal(rem(m, n), pred(n));otherwise,2374.7: Numerical Functionsanddiv(O, n)d ·IV (m= 0,+ 1, n) + 1+ 1,n) -_ {diV(md'IV (m,n )if equal(rem(m, n), pred(n));otherwise.Another interesting function that turns out to be primitive recursive isdigit(m, n,p), the m-th least significant digit of the base-p representation of n.(As an illustration of the use of digit, the predicate odd(n), with the obvious meaning, can be written simply as digit(l, n, 2).) It is easy to check thatdigit(m, n,p) can be defined as div(rem(n,p t m),p t (m '" 1)).0Example 4.7.4: If f(n,m) is a primitive recursive function, then the sumsumf(n,m) = f(n,O)+ f(n, 1) + '" + f(n,m)is also primitive recursive, because it can be defined as sumf(n,O) = 0, andsumf(n, m + 1) = sumf(n, m) + f(n, m + 1).

We can also define this way theunbounded conjunctions and disjunctions of predicates. For example, if p(n, m)is a predicate, the disjunctionp(n,O) or p(n, 1) or p(n, 2) or '"or p(n, m)is just sgn(sump(n, m)).OEvidently, starting from the extremely simple materials of Definition 4.7.1,we can show that several quite complex functions are primitive recursive. However, primitive recursive functions fail to capture all functions that we shouldreasonably consider computable. This is best established in terms of a diagonalization argument:Example 4.7.5: The set of primitive recursive functions is enumerable. Thisis because each primitive recursive function can in principle be defined in termsof the basic functions, and therefore can be represented as a string in a finitealphabet; the alphabet should contain symbols for the identity, successor, andzero functions, for primitive recursion and composition, plus parentheses andthe symbols and 1 used to index in binary basic functions such as id 17 ,ll (seeSection 5.2 for another use of such indexing, this time to represent all Turingmachines).

We could then enumerate all strings in the alphabet and keep onlythe ones that are legal definitions of primitive recursive functions -in fact, wecould choose to keep only the unary primitive recursive functions, those withonly one argument.°Chapter 4: TURING MACHINES238Suppose then that we list all unary primitive recursive functions, as strings,in lexicographic orderfo,/I,/2,/s, ...In principle, given any number n 2 0, we could find the n-th unary primitiverecursive function in this list, f n, and then use its definition to compute thenumber fn(n) + 1.

Call this number g(n). Clearly, g(n) is a computable function -we just outlined how to compute it. Still, 9 is not a primitive recursivefunction. Because if it were, say 9 = fm for some m 2 0, then we would havefm(m) = fm(m) + 1, which is absurd.This is a diagonalization argument. It depends on our having a sequentiallisting of all primitive recursive functions; from that listing one can define afunction which differs from all those in the list, and which, therefore, cannotitself be in the list. Compare this argument with the proof of Theorem 1.5.2,stating that 2N is uncountable. There we started with a purported listing of allthe members of 2N , and obtained a member of 2N not in the listing.<)Evidently, any way of defining functions so that they encompass everythingwe could reasonably call "computable" cannot be based only on simple operations such as composition and recursive definition, which produce functions thatcan always and reliably be recognized as such, and therefore enumerated.

Wehave thus discovered an interesting truth about formalisms of computation: Anysuch formalism whose members (computational devices) are self-evident (that is,given a string we can decide easily whether it encodes a computational devicein the formalism) must be either too weak (like finite-state automata and primitive recursive functions) or so general as to be useless in practice (like Turingmachines that mayor may not halt on an input). Any formalism that captures all computable functions, and just these, must include functions that arenot self-evident (just as it is not self-evident whether a Turing machine haltson all inputs, and thus decides a language).

Характеристики

Список файлов решённой задачи