g: Nn N h: Nn+2 N. , (g, h) f: Nn+1 N, x1,,xn, Î N :
f(x1,,xn,0) = g(x1,,xn);
f(x1,,xn,y+1) = h(x1,,xn,y, f(x1,,xn,y)).
, , , , . : f = R(g,h). g h , f = R(g,h) .
n = 0, g Î N h: N2 N f = R(g,h) :
f(0) = g, f(y + 1) = h(y,f(y)).
f , s, 0 Inm ( , .)
2
o: N N, o(x)=0,
o(0) = 0;
o(y+1)= I22(y, o(y)).
n: Nn N, , , In1 In1: Nn N : N N. k ³ 1 ck: Nn N, k. ck n: Nn N k N N N, s, ck = sk on. , ck .
3
f: N2 N, f(x,y) = x + y, :
f(x,0) = x;
f(x,y + 1) = (x + y) +1 = f(x,y) + 1 = s(f(x,y)).
: g(x) = I11(x) = x, h(x,y,z) = s(z). f(x,0) = g(x)
f(x,y + 1) = h(x,y,f(x,y)), f = R(g,h) = R(I11,s I33). , f .
1 f(x1, , xn) g(x1, , xn) .
.
f(x1, , xn)+g(x1, , xn)= S(+,f,g) (x1, , xn).
4
f: N2 N, f(x,y) = x×y, :
f(x,0) = 0;
f(x,y + 1) = x (y + 1) = f(x,y) + x.
: g(x) = o(x), h(x,y,z) = x+z. f(x,0) = o(x)
f(x,y + 1) = h(x,y,f(x,y)), f = R(g,h) = R(o, S(+, I31,, I33). , f .
2 f(x1, , xn) g(x1, , xn) .
5
: f(x,y) = xy. f(x,0) = 1,
f(x,y + 1) = x×f(x,y) = g(x,y,f(x,y)), g(x,y,z) = x×z ( (I31, I33): N3 N2), f(x,y) .
6
d(x) = max(0,x 1). d(0) = 0
d(y + 1) = y = g(y,d(y)), g(y,z) = I21(y,z) = y. , d(x) .
|
|
7
r(x,y) = max(0,x y). r(x,0) = x
r(x,y + 1) = d(r(x,y)) = g(x,y,r(x,y)), g(x,y,z) = d(z) 5. , r(x,y) .
6 , f(x,y) =ôx-yô= r(x,y) + r(y,x) , x1 + x2 (r(x,y),r(y,x)): N2 N2 ( r(y,x) r(y,x) = S3(r, I22, I21)).
g: Nn+1 N . , f: Nn N , :
f(x1,,xn) = m y [g(x1,,xn,y) = 0],
: f(x1,,xn) y Î N , g(x1,,xn,0),,g(x1,,xn,y -1) 0, g(x1,,xn,y) = 0.
f: Nn N , 0, s, Inm , .
8
: g(x,y) = x Sg(y), Sg(y) = 0, y = 0, Sg(y) = 1, y > 0. :
f(x) = m y[ôx-Sg(y)ô= 0]
x > 1. y Î N, 0 Sg(y) = 0, 0, y, 1 Sg(y) = 0, 1. , f(0) = 0, f(1) = 1, f(x) x > 1. ôx Sg(y)ô , , f(x) .
. CA: N N, 0 . , . , N N, 0 1 , .
. f: N N , A Í N . fA: N N, fA(x) = f(x) x Î A x Ï A, .
. , fA(x) = f(x) + CA(x). fA , .
. , . , , . :
. ( ) .
, Q , , , . , , . , , . .
|
|
1
0,1,,9. :
9. 9 8 . 0.
.
T = (A,Q,p) , A = {a0,a1,,an}, Q = {q0,q1,,qm}
p: Q ´ A Q ´ A ´ {L,S,R}.
{L,S,R} , . : L , R , S .
, . a0 a1 : a0 = 0, a1 = 1. q0,,qm .
p , (qi,qj)
p(qi,qj) Î Q ´ A ´ {L, S, R}, :
qiaj qkae (qk,ae,S) = p(qi,aj),
qiaj qkaeR (qk,ae,R) = p(qi,aj),
qiaj qkaeL (qk,ae,L) = p(qi,aj).
T(i,j).
, , : aqkaeb,
0 £ k £ m, 0 £ e £ n, a b (, ), . , x , : .
: aqkaeb , ae, qk, , a, b. 1 : 20qi931 i.
M = aqiajb, 0 £ i £ m. MT , ( ) :
1) i = 0 MT = M;
2) i > 0 :
T(i,j) = qiaj qkae, MT = aqkaeb;
T(i,j) = qiaj qkaeR,
b , MT = aqeakb, MT = aqeaka0;
T(i,j) = qiaj qkaeL,
a = a1as a1 as, MT = a1qkasaeb,
(.. a ) MT= qka0aeb ( ).
: MT0 = M, MT(n+1) = (MT(n)).
, 1, MT(n) = M1 n ³ 0. : ÞT M1, 1, ( MT).
, f: Nn N, :
(x1,,xn) Î Dom(f), , .. q101x101xn0 aq0b, aq0b f(x1,,xn) 1 ( x1, , xn x1,..., xn);
(x1,,xn) Dom(f), ,
M = q101x101xn0, , .. q0 MT(n) n ³ 0.
, f: Nn N, :
(x1,,xn) Î Dom(f), q101x101xn0 ÞTq001f(x1,,xn)00;
, q101x101xn0, .
f () , , () f.
2
T = {A, Q, p}, A = {0,1}, Q = {q0,q1,q2} :
q0 | q1 | q2 | |
q20R | q01S | ||
q21R |
: M = q101110. q10q20R. : MT = 0q21110. , , 0111q20, q21 q21R. q20 q01, , q0 . , x , , x. x + 1 , : s(x) = x + 1.
|
|
3
: s(x) = x+1 2 . :
q0 | q1 | q2 | q3 | q4 | |
q20R | q31R | q40L | q00L | ||
q21R | q41L | q41L |
, : o(x) = 0.
:
Imn(x1,,xn), 1 £ m £ n.
, , . . , .
1. , .
, , .
, , , . , : T0, T1, .
( ). T0,T1, T2, , , h(n,k) , 1, Tn , q101k0, h(n,k) = 0 . h: N2 N . , , , , k.
. . h(n,k) . :
f(n) = My[h(n,n) + y = 0]
. m , f Tm. f(m) = 0, h(m,m) = 0. h h(m,m) = 0 , Tm , q101m0. f Tm, , Tm , m, f(m) . : f(m) = 0, f(m) , , h .
, , (), , , . , , , , , . , .
|
|
, : , , . , n l(n) = [log2n] + 1, .
fmax(n), , , n . , n- (x1,,xn) Î D (, ) t(x1,,xn), . max{t(x1,,xn):(x1,,xn) Î D}. : , ôDô D Í Nn, x = (x1,,xn) D. : fmin(n) = min{t(x):x Î D}. . t(x1,,xn) u(x1,,xn) , , x1,,xn.
: , f(n) , g(n), : f(n) = O(g(n)), C > 0, n (.. , n) f(n) £ Cg(n). , f(n) = O(g(n)) g(n) = O(f(n)).