Abstract first order computability. I, II
Yiannis N. Moschovakis · Transactions of the American Mathematical Society · 1969
The preparation of this paper was sponsored in part by an NSF Grant.427 Case CO.Seq (/) & (/)0 = 3 & (/)i = 0 & 1 = (f)3 = /Case C5.Seq (/) & (f)0 = 4 & (f)y = 5 & (f)2 s a> & (f)3 e PRI & (/)4 e PRI & (/)4,2 = (/)2 & (/)3>2 = (/)2 +1.(Here (x)u = ((*),),.)Case C6.Seq (/) & (/)0 = 4 & (f)y = 6 & (/)2 = 1 & (/)3 e PRI & (/)4 e FF/ & (/)3>2 = (f)2 & (/)4>2 = (f)2 + 3. Case C7.Seq (/) & (/)0 = 4 & (f)y = 7 & 0 = (/)3 2 = (/)2.We prove (b) by induction on a primitive recursive derivation of (u) from schemata S1-S6 of [6].Case SI. tb(y, x)=y+1.Set f(y, x) = (y, 0) using C2, (a), C3 and C5.Case S2. (u)=q e co.Immediate from (a).Cases S3, S4 and S6 are immediate by C2, C5 and C7.Case S5. (0, x) = ^(x), (y +1, x) = x(y, /i(x) and x(.v, "> x) respectively when restricted to co.By Lemma 2 and C7 the functions g'(y, x) = g(x), h'(u, v, s, t, x) = h(s, u, x) are combinatorial.We set by C6 %y, x) = g'(y, x) = g(x), f((s, t), x) = h'(f(s, x), f(t, x), s, t, x) = h(i, f(s, x), x),