判定不可能な言語

Turing
7
Turing
A
B
•  f
f
a≠b
•  f
f(a)=b
•  f
A
f(a)≠f(b)
B
a,b∈A
b∈B
a∈A
f
A
B
N={1,2,3,...}
f(n)=2n
A
B
{2,4,6,...}
Turing
A
A
A
Σ
N
Σ
Σ
(
Z
) Σ*
n=0,1,2,...
n
N
Σ
Q
Turing
R
(
) Turing
Turing
)
f
B
N
b
b=f(k)
<M>
Turing
B
(
M
n
B
f(n)
Turing
k
B
Σ
(
Σ
)L
Σ
B
Σ
f
si∈A
L
i
s1,s2,s3,…
1 si∉A
f: L → B
A
0
(
)
Σ
L
L Turing
Turing
Turing
Turing
Turing
ATM
ATM={<M,w> | M
ATM
(
Turing
M
w
H(<M,w>) =
Turing
)M
H
D=“
1. 
2.  H
{
M
M
(
Turing
)
{
M
M
w
w
D
D
H
Mi
<Mj>
<M1> <M2> <M3> <M4>
<D>
{
Turing
(M Turing
H
<M>
<M,<M>>
Turing
<M>
<M>
D D
D(<D>) =
H ATM
Turing
ATM
D(<M>) =
}
ATM
Turing
M1
<D>
<D>
M2
ATM
M3
M4
D
):
H
D
<M1> <M2> <M3> <M4>
<M1> <M2> <M3> <M4>
M1
M1
M2
M2
M3
M3
M4
M4
D
D
<M1> <M2>
<M1> <M2> <M3> <M4>
M1
M1
M2
M2
M3
M4
D
D <D>
D <D>
<D>
ATM
Turing
ATM
Turing
Turing
ATM
ATM
Turing
L
l  L
l  L
L
Turing
ATM
Turing
(
• 
L
L
L
Turing
M
M
L
Turing
• 
L
M2
L Turing
L L
M1
M=“
w
M1
M2
w
)
:
M1 M 2
M
M
2
2
Turing
M
w L
L
L
M
(
)