Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
x
0
, . . . , x
k−1
p
x
0
+1
0
· . . . · p
x
k−1
+1
k−1
,
hx
0
, . . . , x
k−1
i
1 hi = 1
h1, 2, 3i = 2
1+1
· 3
2+1
· 5
3+1
= 67500
x
0
, . . . ,x
k−1
x = hx
0
, . . . ,x
k−1
i
(x) = µi ( (i, x) = 0),
i x
i
(x)
i
= (i, x)
˙
−1.
(x)
x p
i
p
j
j < i
(x) ⇔ (x 6= 0) & ∀i < x ( (p
i
, x) → ∀j < i (p
j
, x)).
∀i < x p
i
x 6= 0 i < p
i
6
x = . . . ·p
m
i
·. . . i < x
(x)
i
<
x x > 0
2
x
> x
(x)
i
= (i, x)
˙
−1 6 (i, x) < 2
(i,x)
6 p
(i,x)
i
6 x.
F
0
(y, x) F
1
(y, x)
F
0
(0, ¯x) = G
0
(¯x)
F
1
(0, ¯x) = G
1
(¯x)
F
0
(y + 1, ¯x) = H
0
(F
0
(y, ¯x), F
1
(y, ¯x), y, ¯x)
F
1
(y + 1, ¯x) = H
1
(F
0
(y, ¯x), F
1
(y, ¯x), y, ¯x),
G
i
(¯x) H
i
(z
0
, z
1
, y, ¯x)
F
0
F
1
G
i
(¯x) H
i
(z
0
, z
1
, y,
0
¯x)
F
0
F
1
F (y, ¯x) = hF
0
(y, ¯x), F
1
(y, ¯x)i,
F
0
(y, ¯x) = (F (y, ¯x))
0
F
1
(y, ¯x) = (F (y, ¯x))
1
¤
( ) = h0, Ii
( ) = h1, I, Ji
0 :
0
···
k − 1 :
k−1
h (
0
), . . . , (
k−1
)i.
(x) ⇔ x
⇔ x = h0, (x)
1
i ∨ x = h1, (x)
1
, (x)
2
i
(x) ⇔ x
⇔ (x) & ∀i < (x) ((x)
i
)
e
m
e
m
(e, x, n) (e, x, n)
x hx
0
, . . . , x
k−1
i e
(e, x, n) n
e
0, x
0
, . . . ,x
k−1
, 0, . . .
(e, x, n) = hr
0
, . . . ,r
e+k
i r
i
i = 0, . . . ,e+k
i n
e
0, x
0
, . . . ,x
k−1
, 0, . . .
e x
hx
0
, . . . , x
k−1
i hr
0
, . . . ,r
e+k
i = (e, x, n)
r
i
i n
e
0, x
0
, . . . , x
k−1
, 0, . . .
n
0 1 e + k
e
e e+k+1 e+k +2
(e, x, 0) (e, x, 0)
(e, x, 0) = 0.
(e, x, 0) =
D
0, (x)
0
, . . . , (x)
(x)
˙
−1
, 0, 0, . . .
E
e+ (x) +1
(e, x, 0) = µz [ (z) & (z) = e + (x) + 1 & (z)
0
= 0 &
∀j < (x) ((z)
j+1
= (x)
j
) &
∀j < (z) (j > (x) → (z)
j
= 0)];
(e, x, n +1)
(e, x, n)
(e, x, n) + 1
I
m
I
(e, x, n) (e)
(e,x,n)
h0, Ii
h1, I, mi (e, x, n)
¡
(e)
(e,x,n)
¢
= 2 I
¡
(e)
(e,x,n)
¢
1
(e, x, n)
¡
(e)
(e,x,n)
¢
= 3
m
¡
(e)
(e,x,n)
¢
2
I
¡
(e)
(e,x,n)
¢
1
I ( (e, x, n))
I
( (e, x, n))
³
(e)
(e,x,n)
´
1
(e, x, n + 1)
(e, x, n + 1) =
(e, x, n) + 1,
¡
((e)
(e,x,n)
¢
= 2)∨
h
¡
(e)
(e,x,n)
¢
= 3 &
( (e, x, n))
³
(e)
(e,x,n)
´
1
= 0
i
¡
(e)
(e,x,n)
¢
2
,
(e, x, n+1) (e, x, n) =
hr
0
, r
1
, . . .i r
j
j
(e, x, n + 1) =
(e, x, n)
(e, x, n)
(e, x, n + 1) = hr
0
, r
1
, . . . , r
I
+ 1, . . .i = p
1+r
0
0
· p
1+r
1
1
· . . . · p
1+(r
I
+1)
I
· . . .
(e, x, n) = hr
0
, r
1
, . . . , r
I
, . . .i = p
1+r
0
0
· p
1+r
1
1
· . . . · p
1+r
I
I
· . . .
p
I
(e, x, n + 1) = p
I
· (e, x, n).
I =
¡
(e)
(e,x,n)
¢
1
(e, x, n + 1) = p
³
(e)
(e,x,n)
´
1
· (e, x, n).
(e, x, n + 1) =
·
(e, x, n)
p
I
¸
=
(e, x, n)
p
³
(e)
(e,x,n)
´
1
.
(e, x, n+1) =
(e, x, n),
¡
(e)
(e,x,n)
¢
= 3 &
( (e, x, n))
³
(e)
(e,x,n)
´
1
= 0
p
³
(e)
(e,x,n)
´
1
× (e, x, n),
¡
(e)
(e,x,n)
¢
= 2
(e,x,n)
p
µ
(e)
(e,x,n)
¶
1
,
e
0, x
1
, . . . ,x
k
, 0, 0, . . .
h (e, x, 0), . . . , (e, x, m)i,
x = hx
1
, . . . ,x
k
i
m
y
y U(y) = ((y)
(y)
˙
−1
)
0
U
(e, x, n) ⇔ x x
1
, . . . , x
k
e
0, x
1
, . . . ,x
(x)
, 0, . . .
n
(e, x, n)
n
(e, x, n)
(e, x, n) > (e) & (∀j < n (e, x, j) < (e)),
T
k
(e, x
1
, . . . ,x
k
, y) ⇔ e y
0, x
1
, . . . ,x
k
, 0, . . .
(e) & (y) & (e, hx
1
, . . . ,x
k
i, (y)
˙
−1)
& ∀i < (y) ((y)
i
= (e, hx
1
, . . . ,x
k
i, i)).
T
k
A
P
k
e
P
A
P
k
(x
1
, . . . ,x
k
) ' U(µy T
k
(e, x
1
, . . . ,x
k
, y)).
ψ(x
1
, . . . ,x
k
)
e
ψ(x
1
, . . . ,x
k
) ' U(µy T
k
(e, x
1
, . . . ,x
k
, y)).
y µ
e
U(µy T
k
(e, x
1
, . . . ,x
k
, y))
e
k = 1, 2, . . .
ϕ(e, x
1
, . . . ,x
k
)
ψ(x
1
, . . . ,x
k
) e
ψ(x
1
, . . . ,x
k
) ' ϕ(e, x
1
, . . . ,x
k
).
ϕ(e, x
1
, . . . ,x
k
) ' U(µy T
k
(e, x
1
, . . . ,x
k
, y))
¤
{e}(x
1
, . . . ,x
k
) ' U(µy T
k
(e, x
1
, . . . ,x
k
, y)).
{e}(x
1
, . . . ,x
k
)
e x
1
, . . . ,x
k
e
æ
e
e e
æ
e
(x) ' {e}(x) e ∈ N
F (y
1
, . . . ,y
m
, x
1
. . . x
n
)
s(y
1
, . . . ,y
m
)
F (y
1
, . . . ,y
m
, x
1
. . . x
n
) ' {s(y
1
, . . . ,y
m
)}(x
1
. . . x
n
).
s
y
1
, . . . ,y
m
, x
1
. . . x
n
y
1
, . . . ,y
m
H(x
1
. . . x
n
) ' F (y
1
, . . . ,y
m
, x
1
. . . x
n
)
x
1
. . . x
n
y
1
, . . . ,y
m
y
1
, . . . ,y
m
s
F
0
(x
1
. . . x
n
, y
1
, . . . ,y
m
) ' F (y
1
, . . . ,y
m
, x
1
. . . x
n
).
F
0
(x
1
. . . x
n
, y
1
, . . . ,y
m
) '
F (I
m+n
n+1
(¯x, ¯y), . . . ,I
m+n
n+m
(¯x, ¯y), I
m+n
1
(¯x, ¯y), . . . ,I
m+n
n
(¯x, ¯y)).
P e F
0
(x
1
. . . x
n
, y
1
, . . . ,y
m
)
y
1
, . . . ,y
m
x
1
. . . x
n
n + 1
. . .
n + 1
y
1
. . .
n + m
. . .
n + m
y
m
P
∗
P
y
1
,...,y
k
y
1
, . . . ,y
m
k
k ¯y = y
1
, . . . ,y
k
G(k, ¯y) =
k P
¯y
, P
¯y
k
0
` P
s(¯y) = µz ( (z) & (z) = ` + y
1
+ ···+ y
m
& ∀i < (z)((z)
i
= G(i, ¯y)).
G(k, ¯y) =
( n + 1), 0 6 k < y
1
( n + 2), y
1
6 k < y
1
+ y
2
. . .
( n + m), y
1
+ ··· + y
m−1
6 k < y
1
+ ··· + y
m
( j + y
1
+ ··· + y
m
),
y
1
+ ··· + y
m
6 k < y
1
+ ···y
m
+ `
k
˙
−(y
1
+ ··· + y
m
) P j
( ),
y
1
+ ··· + y
m
6 k < y
1
+ ···y
m
+ `
k
˙
−(y
1
+ ··· + y
m
) P
0,
Y (¯y) = y
1
+ ··· + y
m
A(k, ¯y) = k
˙
−Y (¯y)
R(k, ¯y) ⇔ Y (¯y) 6 k < Y (¯y) + `
G(k, ¯y)
G(k, ¯y) =
h0, n + 1i, 0 6 k < y
1
h0, n + 2i, y
1
6 y
1
+ y
2
. . .
h0, n + mi, y
1
+ ··· + y
m−1
6 k < y
1
+ ··· + y
m
1, ((e)
A(k,¯y)
)
1
, ((e)
A(k,¯y)
)
2
+ Y (¯y)
®
,
R(k, ¯y) ((e)
A(k,¯y)
)
0
= 1
0, ((e)
A(k,¯y)
)
1
®
,
R(k, ¯y) ((e)
A(k,¯y)
)
0
= 0
0,
G