Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
S
ν N
(S, ν)
ν η
ν
= {(x, y) | νx = νy}
ν
• η
ν
•
η
ν
x, y νx = νy
•
N
2
\ η
ν
x, y νx 6= νy
• ν
S
S
z ∈ Z
(z) =
½
h0, |z|i, z > 0
h1, |z|i, z < 0
2 × 2 Z
µ·
a b
c d
¸¶
= h (a), (b), (c), (d)i.
ν
ν(x) =
x, x
·
1 0
0 1
¸
,
(S, ν)
S
0
⊆ S
(S, ν)
{x | ν(x) ∈ S
0
}
2×2 ν
S
0
⊆ S
n
S
0
⊆
S
i∈N
S
i
n
S
0
⊆ N
ν(x) = x
f(¯x) ↓ f(¯x)
f(¯x) ↑ f(¯x)
K = {x ∈ N | {x}(x) ↓}
f(x) =
½
0, {x}(x) ↑
,
f(x) ' µy({x}(x) ↑
& y = 0) a ∈ N f(x) ' {a}(x)
{a}(x) ↓⇔ f(x) ↓⇔ {x}(x) ↑ .
x = a {a}(a) ↓⇔ {a}(a) ↑ . ¤
{hx, yi ∈ N | {x}(y) ↓}
{x ∈ N | {x}(x) ↓} ¤
ν
1
S ν
0
S
0
⊆ S
ν
0
ν
1
f ν
0
= ν
1
f ν
0
6 ν
1
ν
0
6 ν
1
ν
1
6 ν
0
ν
0
ν
1
ν
0
≡ ν
1
ν
0
ν
1
ν
1
ν
0
≡
S
ν
0
ν
1
S
0
⊆ S
S
0
(
S, ν
0
)
(S, ν
1
)
ν
S f
f(0) = 0
f(k + 1) = min{z | νz /∈ {νf(0), . . . , νf(k)}}.
f S
ν
x y ν(x) ν(y)
f(x)
ν
∗
(x) = νf(x) ν
∗
S
S
ν
∗
(k + 1) = νf(k + 1) /∈ {ν
∗
(0), . . . , ν
∗
(k)}
ν
∗
(k + 1) ν
∗
(0), . . . , ν
∗
(k)
ν
S s ∈ S m(s) = min{i | ν(i) = s}
M = {m(s) | s ∈ S} = {a
0
< a
1
< a
2
< . . .}.
x /∈ M x
0
< x νx
0
= νx
z < a
k+1
z = a
i
i < k + 1
f(j) = a
j
j ∈ N
m(ν(0)) = 0 a
0
= 0
f(j) = a
j
j = 0, . . . , k f(k +1)
a
k+1
z < a
k+1
M νz
νa
i
i < k + 1
νz ∈ {νa
0
, . . . , νa
k
}
{νf(0), . . . , νf(k)} f(k + 1)
µz(νz /∈ {νf(0), . . . , νf(k)})
a
k+1
f(k + 1) f(k + 1) = a
j+1
ν
∗
= νf ν
∗
6 ν ν 6 ν
∗
ν = ν
∗
g g g(x) = µt(νf(t) =
ν(x)) ν
∗
≡ ν ν ¤
h(t, ¯x)
n(¯x)
æ
h(n(¯x),¯x)
= æ
n(¯x)
.
¯x h(t)
n
æ
h(n)
= æ
n
.
{t}(y, ¯x, z)
t y ¯x z
s(t, y, ¯x)
{t}(y, ¯x, z) ' {s(t, y, ¯x)}(z).
a
0
∈ N
æ
h(s(y,y,¯x),¯x)
(z) ' {a
0
}(y, ¯x, z) ' {s(a
0
, y, ¯x)}(z) ' æ
s(a
0
,y,¯x)
(z).
y = a
0
æ
h(s(a
0
,a
0
,¯x),¯x)
(z) ' æ
s(a
0
,a
0
,¯x)
(z),
n(¯x) = s(a
0
, a
0
, ¯x)
¯x
n(¯x) = s(a
0
, a
0
, ¯x) n = s(a
0
, a
0
) ¤
h(t)
n
h(n)
æ
h(n)
= æ
n
X
{x | æ
x
∈ X}
X
{x | æ
x
∈ X} X
a b æ
a
∈ X æ
b
/∈ X
f
f(x) =
½
b, æ
x
∈ X
a, æ
x
/∈ X.
n ∈ N æ
f(n)
=æ
n
æ
n
∈ X æ
n
= æ
f(n)
= æ
b
/∈ X
æ
n
/∈ X æ
n
= æ
f(n)
= æ
a
∈
X æ
n
/∈ X
{x | æ
x
∈ X} ¤
n æ
n
ϕ(n, x)
ϕ
ψ
n
(x)
n x f(n, x)
g(n) ψ
g(n)
(x) '
f(n, x)
ϕ(x, y) ' æ
x
(y)
N
N
ψ
n
(x) θ
n
(x)
p
n, x ∈ N
ψ
p(n)
(p(x)) ' p(θ
n
(x)).
ψ
n
(x) θ
n
(x)
p
{(n, x, θ
n
(x)) | n, x ∈ N}
{(n, x, ψ
n
(x)) | n, x ∈ N}.
ψ θ
p
ψ
n
(x) θ
n
(x)
p
ψ
p(x)
(p(y)) ' p(θ
x
(y)),
x y
ψ
x
(y) f(x, y, z)
g(x, y) ψ
g(x,y)
(z) ' f(x, y, z)
f
∗
(u, z) ' f((u)
0
, (u)
1
, z).
g
∗
(u) ψ
g
∗
(u)
(z) '
f
∗
(u, z) u = hx, yi
f(x, y, z) ' f((hx, yi)
0
, (hx, yi)
1
, z) ' f
∗
(hx, yi, z) ' ψ
g
∗
(hx,yi)
(z).
g(x, y) = g
∗
(hx, yi)
g
∗
ψ
x
(y)
h(x, t)
x, y, t ∈ N ψ
x
(y) ' ψ
h(x,t)
(y)
f(x, t, y) ' ψ
x
(y) +
0 ·t h(x, t) ψ
x
(y) ' ψ
x
(y) +
0 · t ' ψ
h(x,t)
(y)
æ
x
i æ
x
=æ
i
x
κ
m
(y)
m y m
0
∈ N æ
m
0
(x) N
κ
m
0
(y) ' æ
−1
m
0
(y)
κ
m
(y) = µx ( |æ
m
(x) − y| = 0).
z
h
z
x
ψ
h
z
(x)
= æ
z
θ
x
κ
z
κ
z
ϕ
h
z
(x)
æ
z
= θ
x