Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
→
→
(m − 1)
m + 1, . . . , m + m
1
→
···
k
→
···
F
P
∗
F
→
. . .
→
→
j 6= 0
→ j 6= 0 R
0
u
0
, . . . , u
m
1
k
→ →
0(x) = 0, s(x) = x + 1 I
n
m
(x
1
, . . . , x
n
) =
x
m
m, n ∈ N 1 6 m 6 n
0(x) s(x)
→ I
n
m
(x
1
, . . . , x
n
)
→
f(y
1
, . . . , y
m
), g
1
(x
1
, . . . , x
n
), . . . , g
m
(x
1
, . . . , x
n
)
h(x
1
, . . . , x
n
)
h(x
1
, . . . , x
n
) = f(g
1
(x
1
, . . . , x
n
), . . . , g
m
(x
1
, . . . , x
n
)),
z
1
= g
1
(x
1
, . . . , x
n
)
z
m
= g
m
(x
1
, . . . , x
n
)
h(x
1
, . . . , x
n
) = f (z
1
, . . . , z
m
)
h(z, y, ¯x) g(¯x) ¯x = x
1
, . . . , x
n
f
·
f(0, ¯x) = g(¯x)
f(y + 1, ¯x) = h(f(y, ¯x), y, ¯x).
¯x
·
f(0) = a
f(y + 1) = h(f (y ), y),
a f(n, ¯x)
f(0, ¯x), f(1, ¯x), . . . , f(n, ¯x)
f(n, ¯x)
µ
g(z, ¯x)
f(¯x) = y
∀i < y
³
g(i, ¯x) 0
´
&
³
g(y, ¯x) = 0
´
.
µ
f(¯x) ' µy(g(y, ¯x) = 0).
g(0, ¯x), g(1, ¯x), . . .
g(n, ¯x) = 0 n n
f(¯x)
g(i, ¯x)
f(¯x)
g(y, x) y = 0
x
h(x) = µy(g(y, x) =
0) x = 0 g(0)
µy(g(y, x) = 0) y
g(y, x) = 0
f : N
k
→ N
f
1
, . . . , f
n
= f
n
n = 1
f = f
1
f
f
1
, . . . , f
k
= f
k < n f
f
1
, . . . , f
n
= f n f
S R M f
i
i < n f
1
, . . . , f
i
f
i
f
i
i < n
S R M f
f(y
1
, . . . , y
m
), g
1
(x
1
, . . . , x
n
), . . . , g
m
(x
1
, . . . , x
n
)
f(g
1
(x
1
, . . . , x
n
), . . . , g
m
(x
1
, . . . , x
n
))
1
→
n
→
→
¯x = x
g(x) h(z, y, x)
f
·
f(0, x) = g(x)
f(y + 1, x) = h(f (y , x), y, x).
→
→
→
→
g(y, x
1
, . . . , x
k
)
f(x) = µy(g(y, x
1
, . . . , x
k
) = 0) :
→
f(x) = a a
x + y
x × y
x
y
(x) =
½
0, x = 0
1, x 6= 0;
(x) =
½
1, x = 0
0, x 6= 0;
x
˙
−1 =
½
x − 1, x > 0
0, x = 0;
x
˙
−y =
½
x − y, x > y
0, x < y;
|x − y|
f(x) = s . . . s
|{z}
a
(0(x))
x+y x×y
·
0 + x = I
1
1
(x)
(y + 1) + x = I
3
1
(s(y + x), y, x),
·
0 × x = 0(x)
(y + 1) × x = y × x + (0(y) + x).
x
y
·
(0) = 0
(y + 1) = 1.
·
x
˙
−0 = I
1
1
(x)
x
˙
−(y + 1) = I
3
1
((x
˙
−y)
˙
−1, y, x),
|x − y| = (x
˙
−y) + (y
˙
−x).
¤
R ⊆ N
k
χ
R
(¯x)
χ
R
(¯x) =
½
1, ¯x ∈ P
0, ¯x /∈ P.
P ⊆ N
k
f
1
(¯y) f
k
(¯y) Q(¯y)
Q(¯y) ⇔ P (f
1
(¯y), . . . , f
k
(¯y))
χ
Q
(¯y) = χ
P
(f
1
(¯y), . . . , f
k
(¯y)).
¤
P (¯x) Q(¯x)
¬P (¯x) P (¯x) & Q(¯x) P (¯x) ∨ Q(¯x) P (¯x) → Q(¯x)
χ
¬P
= 1
˙
−χ
P
χ
P & Q
= χ
P
· χ
Q
χ
P ∨Q
= χ
P
+ χ
Q
˙
−χ
P
·χ
Q
P (¯x) → Q(¯x) ¬P (¯x)∨Q(¯x)
¤
= 6= < > 6 >
χ
=
(x, y) = |x − y|
=
χ
<
(x, y) = (y
˙
−x) χ
>
(x, y) = (x
˙
−y) x 6 y ⇔
x = y ∨ x < y x > y ⇔ x = y ∨ x > y ¤
g(i, ¯x)
f(n, ¯x) =
P
n
i=0
g(i, ¯x) g(i, ¯x)
f
f
·
f(0, ¯x) = g(0, ¯x)
f(n + 1, x) = f (n, ¯x) + g(s(n), ¯x). ¤
P (i, ¯x)
∃i 6 n P (i, ¯x) ∀i 6 n P (i, ¯x) ∃i < n P (i, ¯x) ∀i <
n P (i, ¯x) n i
χ
∃i6n P (i,¯x)
(i, ¯x) =
Ã
n
X
i=0
χ
P
(i, ¯x)
!
.
∀i6 n P (i, ¯x) ⇔ ¬∃i6 n¬P (i, ¯x).
∃i<n P (i, ¯x) ⇔ ∃i6 n (P (i, ¯x) & i6= n).
∀i<n P (i, ¯x) ⇔ ¬∃i< n¬P (i, ¯x). ¤
R(y, ¯x)
µyR(y, ¯x) µy (|χ
R
(y, ¯x) − 1| = 0)
y R(y, ¯x)
(x, y) x y
h
x
y
i
x y
£
x
0
¤
= x
(x)
(x, y) ⇔ ∃t 6 y(x × t = y),
·
x
y
¸
= µz(z = x ∨ (z + 1) × y > x),
(x) ⇔ (x 6= 0) & (x 6= 1) &∀y 6 x( (x, y) → (y = 1 ∨ y = x)).
¤
p
i
i
i p
0
= 2 p
1
= 3 p
2
= 5
(i, x) p
i
x
(i, 0) = 0
p
i
·
p
0
= 2
p
i+1
= µy( (y) & y > p
i
).
(i, x) = µy(¬ (p
y+1
i
, x) ∨ x = 0).
x = 0 (i, 0) ¤
P
1
(x
1
, . . . , x
n
) P
m
(x
1
, . . . , x
n
)
x
1
, . . . , x
n
i ∈ {1, . . . , m} P
i
(x
1
, . . . , x
n
)
f
1
(x
1
, . . . , x
n
) f
m
(x
1
, . . . , x
n
)
F (¯x)
F (¯x) =
f
1
(¯x), P
1
(¯x)
f
2
(¯x), P
2
(¯x)
···
f
m
(¯x), P
m
(¯x),
F (¯x) = f
1
(¯x)χ
P
1
(¯x) + f
2
(¯x)χ
P
2
(¯x) + ···f
m
(¯x)χ
P
m
(¯x).
¤