.. .
. ( ). . ( ) .
N . N , , N .
N - , S - ,..., N, , S, ,... - . N-M : N, , , , , N.
, = {, b, } N = ab, = bcb, = abcbcbab, N , bcbcbcbab abcbcbbcb, , , N, aabcbab bbb.
ab - bcb bacb, ab, bcb . .. . , .
P1 2 , .
, P1, 2,..., , , - .
, .
{ , b, , d, } - a, abac - abace
ad - da; eca - ae
bc - cb; eda - be
bd - db; edb - be
abcde acbde - ( bc - cb). abcde - cadbe .
, : N → ( , ). : , .
, . .
: , . , , .
|
|
: :
= { , b, } cb - cc
- b
ab b
: , ; .
, babaac bab :
babaac → bbcaaac →
bcacabc → bcacbcac → bcacccac → bb → ( ), .
.. , . . , .. , . . P1. , .
. : 1) ; 2) . .
, - ( ).
: :
= (+, 1) 1 + → + 1
+ 1 → 1
1 → 1
: 11+11+111
:
= 11 + 11 + 111 5 = + 1 + 111111
1 = 1 + 111 + 111 6 = ++ 1111111
2 = + 1111 + 111 7 = + 1111111
3 = + 111 + 1111 8 = 1111111
4 = + 11 + 11111 9 = 1111111
. : ,
. , , . , , ( ). , , A.
N , , N .
, , . : .
|
|
| , , , , , . .
I. . . () = (()),
II. . , , , () ().
III. . D , , D , , D(p) = (), () = , D(p) = B(p), () = , - .
IV. . () , () , , .
, , . , .
, .
, , . , , , .
, . . .
. X, Y - . ( ) Y <D(f), f>, D(f) Ì X ( f) f: D(f) Y. D(f) , f . , .
N . (N)n ( ³ 1) n - N , .. n - (1..., xn), i Ì N. (N)m (N)n .
f (N)m (N)n , (), Ì (N)m f(x), Ì D(f) , Ë D(f). () () . . ( ) - . (N)" (N)" , (), (N)" D(f), , D(f). , , .
|
|
f , , .
, . , , , . :
, P(t, x1,...,xn), g(t) - . , , g(t) - .
, , , : ) ; ) , , , .
:
suc: N N; suc (x) = x +1 - ;
l(n): (N)n N; l(n) (x1,..., n) = 1, ³ 0 - ;
r : (N)n N; pr (x1,..., n) = i, ³ 1 - .
:
) ( ) f (N)m (N)n g (N)n (N)p h = gof (N)m (N)p,
) fi (N)ni, i = 1,..., k (f i,..., fk) (N)m (N)n1 ... (N)nk,
) f (N)n N g (N)n+2 N h (N)n+2 N,
h(x1,..., n, 1) = f (x1, ...,x) ( ),
h (x1,...,n, k+1) = g(x1,...,xn, k, h(x1,...,n, k)) k ³ 1 ( ).
D(h) :
) , f (N)n+1 N h (N)n N,
.
, , :
) f i,... ,fN ( ) fN = f, f i - ; fi i ³ 2 , f i,..., fi-1 ( , );
) f ( ), ( ) .
:
|
|
) f , ;
) f , f XD(f).
Y(X Ì Y) ,
.
P1, P2,..., . . f N N:
, f XD(f) . .
1. ?
2. : ?
3. ?
4. ?
5. .
6. , .
7. ( ) , .
8. , .
9. ?
10. ?
11. . .
12. .
13. ?
14. ?
15. , , .
16. .
17. ?
18. .
19. ?
20. , .
21. ?
22. .
23. .
24. -?
25. - .
26. ? ?