Introduction to Theoretical Computer Science (Series in by Xiwen Ma

Show description

This function is called the length function and is denoted by length. Structure-recursive Definition of Functions A function can be defined recursively on the structure of its argument. Let go, •'•, g, be given functions, where g}: Xi+i-*-X is defined for all {y, y\, •••, yj) such that itjiy) is true. 2. 2. 11. Therorem. (Structure-recursive definition). Let go, ***, g. be given. There exist a unique function / recursively defined by go, •••, g.. In addition, this function is total. Proof. Denote the vector representation of domain X onto the formal solution Y by p.

In this situation, we define: Tfl(z) = Oj, T{(X) = z l t •••, r'j{x) = Xj, and call *{ the i-th component function of type j . Moreover, we have: o v O i O ) . x), , r j ( x ) ) = x, for z 6 Xj. In the case of formal solution, the component functions are exactly the pro­ jections functions. In summary, we have proved: 2. 2. 1. Lemma. (Z) is true; ( 2 ) For any j = l , •••, n and a^Aj, xu •••, Z ; £ X , ^(o-j(a ; , i , , •••, z , ) ) is true. ( 3 ) Let Ttjix) and itjiy) be true. Then x = y if and only if T / ( Z ) = T / ( J ) , for all i = 0, •", j .

2. 9. Problem. Let p(z) be a function of words such that /<«*>> if x 6 M 10 otherwise show that g is the unique function satisfying: f if X= < ) />(*) = ip(y) if x = a0 • y 10 otherwise. The function p in this problem is a decision function determining 30 CHAPTER 2 S-EXPRESSIONS whether a word x is a natural number or not, and is called the number-predi­ cating function, denoted by numbery. 2. 2. 10. Problem. Let l(x) be a function of words, such that if x con­ tains n letters, then l(xs)=n.