Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
h
z
(y) z, y
æ
x
(y) g(z)
æ
g(z)
(y) ' h
z
(y) n
æ
n
= æ
g(n)
= h
n
h
n
æ
n
N
p(x) = h
n
(x) = æ
n
(x)
x
ψ
p(x)
= pθ
x
p
−1
p
−1
ψ
p(x)
p = θ
x
p
ψ
p(x)
p = pθ
x
x y
ψ(p(x), p(y)) ' p(θ(x, y))
h
z
(y)
(x, y)
M
t
t
M
0
= ∅
t+1 x
M
t
y
M
t
(x, y) M
t+1
= M
t
∪ {(x, y)}
t + 1
y
M
t
x
M
t
M
t+1
= M
t
∪ {(x, y)} q(x)
q(x) = y ⇔ (x, y) ∈ M =
S
t∈N
M
t
q(x)
(x, y)
y q(x) q
h
z
z {(x, y) | h
z
(x) = y}
M
0
= ∅
t + 1
h
z
x
M
t
w = h
z
(x)
M
t
y ∈ N
ψ
w
(y) ' æ
z
θ
x
κ
z
(y).
q(z, x)
∀y ( ψ
q(z,x)
(y) ' æ
z
θ
x
κ
z
(y) ),
w
∀y ( ψ
q(z,x)
(y) ' ψ
w
(y) )
w
M
t
h
z
(x) = w
t + 1
h
z
θ
x
(y) ' κ
z
ψ
h
z
(x)
æ
z
(y)
u = h
z
(x) x
x
h
z
(x)
¤
ψ
x
(y)
θ
x
(y) θ
x
(y)
θ
x
(y) ψ
x
(y)
p
θ
p(x)
(p(y)) ' pψ
x
(y).
ψ
x
(y) θ
x
(y)
f(x, y)
g(x)
p
−1
f(p(x), p(y)) ' ψ
g(x)
(y).
f(p(x), p(y)) ' pψ
g(x)
(y) ' θ
pg(x)
(py).
x
0
= p(x) y
0
= p(y)
f(x
0
, y
0
) ' θ
pgp
−1
(y
0
).
pgp
−1
θ
x
(y)
{pθ
p
−1
(x)
(p
−1
(y)) | p N}.
S ⊆ N
S = ∅ S = range (f)
f : N → N
A
a ∈ A
f(x) =
½
x, x ∈ A
a, x /∈ A.
A = range (f) ¤
S ⊆ N
S
R ⊆ N
2
∀x (x ∈ S ⇔ ∃t R(x, t));
R ⊆ N
k+1
∀x (x ∈ S ⇔ ∃t
1
. . . ∃t
k
R(x, t
1
, . . . , t
k
));
S = dom (f)
S = range (f)
⇒ S = ∅
∀x (x ∈ S ⇔ ∃t(x + t + 1 = 0)) S 6= ∅
f : N → N S = range (f)
x ∈ S ⇔ ∃t (x = f (t))
⇒
⇒ R(x, t
1
, . . . , t
k
)
f(x) = µt R(x, (t)
1
, . . . , (t)
k
) f
f(x) ↓⇔ ∃t
1
. . . ∃t
k
R(x, t) S = dom (f)
⇒ S = dom (g) g
f(x) = x ·(0(g(x)) + 1) f
range (f) = S
⇒ S = ∅
S 6= ∅ e
e ∈ N
T (e, x, t) f(x) ' U(µt (T (e, x, t)))
t
e x x
T (e, x, t) t
a
0
∈ S
g(t) =
½
U((t)
1
), T (e, (t)
0
, (t)
1
)
a
0
,
g ¤
S = {hx, y, zi | æ
x
(y) = z}
v ∈ S ⇔ (v) & (v) = 2 & ∃t (T
1
((v)
0
, (v)
1
, t) & U(t) = (v)
2
),
v ∈ S ⇔ ∃t ( (v) & (v) = 2 & (T
1
((v)
0
, (v)
1
, t) & U(t) = (v)
2
)),
W
n
= dom (æ
n
) n ∈
N
π
n
= range (æ
n
) n ∈ N
W
n
ν
{hx, yi | x ∈
ν(y) }
(A
n
)
n∈N
ν(n) = A
n
x ∈ ν(y) ∃t R(x, y, t)
R ν
r ∈ {hx, yi | x ∈ ν(y)} ⇔ (r) & (r) = 2 & ∃t R((r)
0
, (r)
1
, t),
ν(n)
x ∈ W
y
⇔ ∃t T
1
(y, x, t).
ν
S = {hx, yi | x ∈
ν(y)} g(t, x)
g(x, t) =
½
0, t ∈ ν(x)
g(x, t)
S
ht, xi 0
æ
h g(x, t) 'æ
h(x)
(t)
t ∈ ν(x) ⇔ g(x, t) ↓⇔ æ
h(x)
(t) ↓⇔ t ∈ W
h(x)
.
ν(x) = W
h(x)
ν 6 W ¤
u(x, y) v(x, y) x, y ∈ N W
u(x,y)
=
W
x
∪ W
y
W
v(x,y)
= W
x
∩ W
y
ν(z) = W
(z)
0
∪ W
(z)
1
n ∈ ν(z) ⇔ n ∈ W
(z)
0
∨ n ∈ W
(z)
1
⇔
⇔ ∃t T ((z)
0
, n, t) ∨ ∃t T ((z)
1
, n, t) ⇔
⇔ ∃t (T ((z)
0
, n, t) ∨ T ((z)
1
, n, t)).
ν(z) = W
h(z)
h
W
x
∪ W
y
= W
(hx,yi)
0
∪ W
(hx,yi)
1
= ν(hx, yi) = W
h(hx,yi)
.
ν(z) = W
(z)
0
∩W
(z)
1
n ∈ ν(z) ⇔ n ∈ W
(z)
0
& n ∈ W
(z)
1
⇔
⇔ ∃t T ((z)
0
, n, t) & ∃t T ((z)
1
, n, t) ⇔
⇔ ∃t∃t
0
(T ((z)
0
, n, (t)
0
) & T ((z)
1
, n, (t
0
)
1
)).
¤
K
x ∈ K ⇔ {x}(x) ↓⇔ ∃t T
1
(x, x, t)
A ⊆ N N \ A
A
A
x
x ∈ A
A = range (f) N \ A = range (g)
h(x) = µt(x = f(t) ∨ x = g(t))
x ∈ A ⇔ x = f(h(x))
f : N
k
→ N
Γ(f) = {hx
1
, . . . , x
k
, yi | f(x
1
, . . . , x
k
) = y}
f : N
k
→
N
f
e ∈ N
f(x
1
, . . . , x
k
) ' U(µt (T
k
(e, x
1
, . . . , x
k
, t))).
hx
1
, . . . , x
k
, yi ∈ Γ(f) ⇔ f(x) = y
⇔ ∃t[y = U(t) & T
k
(e, x
1
, . . . , x
k
, t) & ∀t
0
< t¬T
k
(e, x
1
, . . . , x
k
, t
0
)].
Γ(f)
Γ(f) f : N
k
→ N
Γ(f) = ∅ f = ∅ f
Γ(f) 6= ∅
g Γ(f) = range (g) f
f(x
1
, . . . , x
k
) = (µt((g(t))
0
= x
1
& . . . & (g(t))
k−1
= x
k
))
k
.
f ¤
A
1
A
k
f
1
(x) f
k
(x)
g
g(x) =
f
1
(x), x ∈ A
1
f
2
(x), x ∈ A
2
. . .
f
k
(x), x ∈ A
k
,
, ,
g(x) = y ⇔ (y = f
1
(x) & x ∈ A
1
) ∨ . . . (y = f
k
(x) & x ∈ A
k
).
{hx, yi | y = f
k
(x)} x ∈ A
k
(∃t
1
R
1
(x, y, t
1
) & ∃t
0
1
Q
1
(x)) ∨ . . . (∃t
k
R
1
(x, y, t
k
) & ∃t
0
k
Q
k
(x)),
R
i
(x, y, t
i
) Q
i
(x) i = 1, . . . , k
∃t
1
∃t
0
1
. . . ∃t
k
∃t
0
k
(R
1
(x, y, t
1
) & Q
1
(x)) ∨ . . . (R
1
(x, y, t
k
) & Q
k
(x)).
g
g ¤
