Z(x) = 0 S(x) π n i (x 1,, x n ) = x i n 1 i n n g : N n N h : N n+2 N n- (n + 2)- (n + 1)- f : N n+1 N g h f(x 1,, x n, 0) =

Size: px

Start display at page:

Download "Z(x) = 0 S(x) π n i (x 1,, x n ) = x i n 1 i n n g : N n N h : N n+2 N n- (n + 2)- (n + 1)- f : N n+1 N g h f(x 1,, x n, 0) ="

锵柔公叔
5 years ago
Views:

1 Z(x) = 0 S(x) π n i (x 1,, x n ) = x i n 1 i n n g : N n N h : N n+2 N n- (n + 2)- (n + 1)- f : N n+1 N g h f(x 1,, x n, 0) = g(x 1,, x n ), f(x 1,, x n, y + 1) = h(x 1,, x n, y, f(x 1,, x n, y)) y + 1 y S(y) 0- g c f g h f(0) = c, f(y + 1) = h(y, f(y)) (7.1) 1

2 C : (1) C (2) C f(x 1,, x n ) = g(h 1 (x 1,, x n ),, h r (x 1,, x n )) g(y 1,, y r ) h i (x 1,, x n ) 1 i r C f C (3) C C?????? f f 1, f 2,, f n f n = f 1 i n f i f : N n N domf = N n 7.1. x + 0 = x, x + (y + 1) = S(x + y) S(x 1 ) π 1 1(x 1 ) = x 1 π 3 3(x 1, x 2, x 3 ) = x 3 g(x 1, x 2, x 3 ) = S π 3 3(x 1, x 2, x 3 ) = S(x 3 ) f(x 1, x 2 ) f(x, y) = x + y 7.1. f(x 1, 0) = π 1 1(x 1 ); f(x 1, y + 1) = g(x 1, y, f(x 1, y)) 1. C n k (x 1,, x n ) = k k 2. x y x y x! 2

3 σ δ: { { 0, x = 0 σ(x) = 1, x 0 δ(x) = 4. pred(x) 5. { : x y = 0, x < y x y, 1, x = 0 0, x f : N k N g : N r N g(x 1,, x r ) = f(y 1,, y k ) y j x i 1 i r g : g f f(x, y) g(x) = f(x, x) h(x, y, z) = f(z, y) k- P { 1, P ( x) ; χ P ( x) = 0, N k A k- P k- P { x : P ( x)} 7.3. = 1. A, B N k N k A, A B A B 3

4 P Q P P Q P Q 7.4 ( ). f 1 f 2 P { f 1 (x), P (x) f(x) = f 2 (x), : f(x) = f 1 (x)χ P (x) + f 2 (x)(1 χ P (x)) quo(x, y) rem(x, y) x y quo(0, y) = 0 rem(0, y) = quo(x, y) rem(x, y) : { rem(x, y) + 1, rem(x, y) + 1 x rem(x, y + 1) = 0, quo(x, y + 1) = { quo(x, y) + 1, quo(x, y), rem(x, y) + 1 = x ( x < a)φ(x) x(x < a φ(x)) ( x < a)φ(x) x(x < a φ(x)) µ 7.3. P ( x, z) (k + 1)- { P ( x, z) y z, (µz y)p ( x, z) = y + 1, 7.6. f( x, y) y z f( x, y) y z f( x, y) : 4

5 7 1 X := Y X Y Y X 7.7. P ( x, z) (a) E( x, y) := ( z y)p ( x, z) A( x, y) := ( z y)p ( x, z) (b) f( x, y) := (µz y)p ( x, z) : (a) ( z y)p ( x, z) z y χ P ( x, z) = 1 ( z y)p ( x, z) ( z y) P ( x, z) (a) (b) (µz y)p ( x, z) = y z=0 z r=0 χ P ( x, r) z y (1) x y (2) x x (3) p(n) := n p(n) p n p 0 = 2, p 1 = 3, p 2 = 5, : 7.4. (1) a 0,, a n p a p a n+1 n (a 0,, a n ) 1 (2) lh : N N lh(a) = µk a (p k a) lh(a) lh(1) = 0 a = a 0,, a n lh(a) = n + 1 (3) a i (a) i = µk a [p k+2 i a] (a) i a i a = a 0,, a n (a) i = a i 0 i n (4) a, b a^b a^b = a 5 i<lh(b) p (b) i+1 lh(a)+i

6 2 7 lh(a) (a) i lh a (a) i i lh(a) 7.9. (1) (2) lh(a) (a) i (3) a^b a 0,, a n ^ b 0,, b m = a 0,, a n, b 0,, b m a b a^b : f(y + 1) f f(y) f(y + 1) f(z) z y f : N k+1 N F ( x, n) = p f( x,0)+1 0 p f( x,1)+1 1 p f( x,n)+1 n f f g h f( x, 0) = g( x); f( x, y + 1) = h( x, y, F ( x, y)) f g h g h f : f F ( x, y) F ( x, 0) = 2 g( x)+1 ; h( x,y,f ( x,y))+1 F ( x, y + 1) = F ( x, y) py+1 f( x, y) = (F ( x, y)) y??

7 7 2 g 0, g 1,... F : N N F (n) = g n (n) + 1 F A(x, y) A(0, y) = y + 1, A(x + 1, 0) = A(x, 1), A(x + 1, y + 1) = A(x, A(x + 1, y)) A(1, y) = y + 2 A(2, y) = 2y + 3 A(3, y) = 2 y+3 3 A(x + 1, y) y A(x, y) A(x, y) x y A(x, y) i = 1 n 7.5. f : N n+1 N g( x) f µ- x yf( x, y) = 0 g( x) f( x, y) = 0 y µ g( x) = µy[f( x, y) = 0] 7.6. x yg( x, y) = 0 y f : A B f A A x f(x) f x f(x) f(x) f x f(x) 7

8 f g f µ- g( x) = µy [ z y(f( x, z) ) f( x, y) = 0] z y(f( x, z) ) f( x, y) y 0 z 0 z 0 y 0 f( x, z 0 ) z y(f( x, z) )?? : S (a) (0, y, z) S z = y + 1 (b) (x + 1, 0, z) S (x, 1, z) S 8

9 7 3 (c) (x + 1, y + 1, z) S u (x + 1, y, u) S (x, u, z) S S (x, y, z) S (1) z = A(x, y) (2) S A(x, y) (x, y, A(x, y )) (x, y, z) x, y, z = 2 x+1 3 y+1 5 z+1 {u 1,, u k } u 1, u 2,, u k v S v v (x, y, z) S v i < v((v) i = x, y, z ) S v R(x, y, v) := v z < v ((x, y, z) S v ) f(x, y) = µvr(x, y, v) A(x, y) = µz((x, y, z) S f(x,y) ) f(x, y) A(x, y) computor 1 On Computable Numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 9

10 3 7 q : 1. 0 A = {a 1, a 2,, a n, 0} Q = {q 1,, q n } q i 7.9. A L R Q δ (a) qaa q q, q Q a, a A (b) qalq q, q Q a A (c) qarq q, q Q a A q a qa Q A (A {R, L}) Q qaa q q a a a q qalq qarq 10

11 7 3 {0, 1} qaa q D D = L R S - q a qa qa q C = uqav q u v A a A u a v?? uq1v u = 10 v = 0011 C = uqav δ qa C C C C (a) qaa q δ C = uq a v (b) qarq δ C = uaq bv v = b ^v (c) qalq δ C = u q bav u ^ b = u C i i C i C i C i+1 11

12 3 7 q s q h 1 x x 1 x = (x 1, x 2,, x k ) q s 1 x x x k+1 q h 1 y y 0 y 1 x x x = 0 1 y f : N k N M M f y, M x y f( x) =, M 7.2. f(x) = 2x. x x a 1 b 1 a b q s 1aq 1, q 1 arq 1, q 1 1Rq 1, q 1 brq 1, q 1 0bq 2, q 2 bbq 3, q 3 blq 3, q 3 1Lq 3, q 3 arq 4, q 4 11q s a 1 q 4 brq 4, q 4 0Lq 5, q 5 b1q 5, q 5 1Lq 5, q 5 a1q 5, q 5 0Rq 6 b a b 1 1 q 6 10q 6, q 6 0Rq 7, q 7 10q 7, q 7 0Rq h 12

13 {0, 1} (1) R = {q s 0Rq h, q s 1Rq h } L = {q s 0Lq h, q s 1Lq h } (2) P 0 = {q s 00q h, q s 10q h } P 1 = {q s 01q h, q s 11q h } 0 1 P 0 0 a P a a 7.4. A = {0, 1, a, b, c, d} R a a R a. R a {q s 0Rq 1, q s 1Rq 1, q s arq 1, q s brq 1, q s crq 1, q s drq 1 } {q 1 0Rq 1, q 1 1Rq 1, q 1 aaq h, q 1 brq 1, q 1 crq 1, q 1 drq 1 } a 7.5. M 1 M 2 M M 1 M 2 M 1 M 2 M. M 2 M 1 M 1 M M 1 M 2 M 0 M 1 M 2 M 13

14 4 7 s 0 M 1 A {0} M 2. M 1 M 2 q 1 s, q 1 h, q2 s, q 2 h M 1 M 2 A M 1 M 2 q s, q h M δ 1 δ 2 {q s 00q 1 s} {q s aaq 2 s : a A \ {0}} {q 1 haaq h, q 2 haaq h : a A} δ 1 δ 2 M 1 M f(x, y) = 2x + y. q s 1 x+1 01 y+1 0R 2 0L x 01 y y- 1 y = 0 0 s 0R 2 0 L0 L 2 0R 0 1 R(halt) 0R 2 01R1 L 2 0R x R 2 01R1 0 x

15 :?? g(h 1 (x 1, x 2 ), h 2 (x 1, x 2 )) x 1 x 2 h 1 (x 1, x 2 ) M 1 M 2 : z y x a b c d M 1 A $ a b c d $ x y z a x (a, x) A A M 2 $ (a,x) (b,y) (c,z) (d,0) (0,0) 15

16 4 7 M 2 M 1 1 x+1 (1, 0) x+1 $ M 1 M 1 q M 2 (q, 1) (q, 2) (q, 1) (q, 2) M 1 δ 1 M 2 δ 2 M 2 (1) M 1 qaa q δ 1 b A (q, 1)(a, b)(a, b)(q, 1) δ 2 qalq δ 1 qarq δ 1 b A (q, 1)(a, b)l(q, 1) (q, 1)(a, b)r(q, 1) δ 2 (2) M 1 qaa q δ 1 b A (q, 2)(b, a)(b, a )(q, 2) δ 2 qalq δ 1 qarq δ 1 b A (q, 2)(b, a)r(q, 2) (q, 2)(b, a)l(q, 2) δ 2 (3) M 1 q (q, 1)$R(q, 2) (q, 2)$R(q, 1) δ 2 M 2 M 1 M 1 C 1 C 2 M 2 C 1 D 1 C 2 D 2 M 1 M $ h $ $ $ f(x 1, x 2,, x n ) = g(h 1 (x 1, x 2,, x n ),, h r (x 1, x 2,, x n )) g h 1,, h r f?? r + 1 x 1, x 2,, x n y i = h i (x 1, x 2,, x n ) i = 1,, r 16

17 7 4 h i g g(y 1, y 2,, y r ) M O O A = {0, 1} 0 L = 2 R = 3 M Q {4, 5,, n} 4 q s n q h qaa q q, a, a, q = 2 q+1 3 a+1 5 a +1 7 q +1 M δ = {s 1, s 2,, s n } δ = s 1, s 2,, s n e = δ M M e = M M M e e s q e : C = b 1 b 0 qac 0 c 1 {0, 1} x = b i 2 i y = c i 2 i C C x, q, a, y = 2 x+1 3 q+1 5 a+1 7 y c : : M e = M 17

18 4 7 IN(x 1, x 2,, x n ) = C 0 C 0 q s 1 x x x k+1 NEXT NEXT (e, c) = d c d C D C D C D e e T ERM(e, c) c e OUT (c) c c = C C = q1 y q OUT (c) = y IN, OUT, NEXT T ERM : T ERM T ERM(e, c) c (c) 1 c q e???? T ERM T (e, x, z) z e x T T T (e, x, z) : T (e, x, z) z C 0,, C m C 0 = IN(x) ( i < m)next (e, C i ) = C i+1 T ERM(e, C m ) 3 µ- T T (e, x, z) z f : f e x µ- z z C m f( x) OUT ( C m ) T (e, x, z) OUT f( x) λ- λ- 18

19 7 4 f f f ( ). U : N N T (e, x, z) f : N N e f(x) = U(µz T (e, x, z)) 7.2. Proof. f e f(x) = U(µz T (e, x, z)) µ- T (e, x, z) f x T (e, x, z) z f 7.4 ( ). Φ : N 2 N f : N N e x f(x) = Φ(e, x) : Φ(e, x) = U(µz T (e, x, z)) Φ(e, x) φ 0, φ 1, φ e (x) = Φ(e, x) 7.5. T : N 2 N f : N N e x f(x) = T (e, x) 19

20 5 7 : 7.8. f(x) g(x) n dom(f) f(n) g(n). : f(x) = Φ(x, x) + 1 Φ(x, y) g m g(x) = Φ(m, x) g(x) Φ(m, m) m dom(f) f(m) = Φ(m, m) + 1 Φ(m, m) = g(m) A r.e. 2 A = A f : N N A = {y : x f(x) = y} f(0) = 7f(1) = 2, f(2) = 7, f(3) = 4, 7, 2 7 A = ran(f) = {2, 4, 7, } A N (a) A (b) A A (c) A (d) A A χ AP (x) { 1, x A χ AP (x) =, (e) A 2 r.e. recursively enumerable 20

21 7 5 (f) R(x, y) A = {x : y R(x, y)} r.e. (d) r.e. (e) (f) : (c) (b) (a) (f) (e) (d) (c) (c) (b) A (c) f(x) A = f[n] U : N N T (e, x, z) e 0 N f(x) = U(µz T (e 0, x, z)) A = (b) A a 0 A F : N 2 N { U(µz n T (e 0, x, z)), z n T (e 0, x, z) F (x, n) = a 0, F F [N 2 ] = A g(z) = F ((z) 0, (z) 1 ) (z) 0 (z) 1?? (b) g (b) (a) (a) (f) A = R = A A = f[n] f R(x, y) f(y) x = 0 f(x) x A y R(x, y) (f) (e) R A = {x : y R(x, y)} g(x) = µyr(x, y) g dom(g) = A (e) (d) A = dom(g) g C 1 1 C 1 (x) = 1 χ AP (x) = C 1 g (d) (c) A χ AP f : N N f(x) = x χ AP (x) f dom(f) = dom(χ AP ) = A a A f(a) = a 1 = a (c) 7.6. A A N \ A : 21

22 5 7?? N N k ϕ : N k N A N k r.e. A ϕ ϕ[a] N r.e N k A B (a) A B A B (b) C = { x N k 1 : y ( x, y) A} : 7.8. K = {e : φ e (e) } φ e (e) e e K?? : K r.e. Φ(x, x) K N \ K x K x K { φ x (x) + 1, x K f(x) = 0, x K e x f(x) = φ e (x) x = e e K f(e) = φ e (e) + 1 φ e (e) x K f(e) = 0 φ e (e) K 7.3. :?? K N\K?? K?? 22

untitled

untitled 8.1 f G(f) 3.1.5 G(f) f G(f) f = a 1 = a 2 b 1 = b 2 8.1.1 {a, b} a, b {a} = {a, a}{a} 8.1.2 = {{a}, {a, b}} a, b a b a, b {a}, {a, b}{a} {a, b} 8.1.3