!
!
!
!
Turing
Information
Science
7
2
C
xi=xj
x1, x2,…, xn.
i≠j
i, j {1,...,n}
Yes.
C
31, 3, 18, 31, 5
No
No
C
C
:
E
!
Turing
M
(i, j)=(1, 2),...,(1, n),(2, 3),...,(2, n),...,(n-1, n)
xi
xj
!
E={ #x1...#xn | n≥0, xi∈{0,1}*, i≠j xi≠xj }
!
xi
q0
xj
#
#
q
$ # 3 1 # 4 # 1 8 # 3 1 # 5
C
$ # 3 1 # 3 # 1 8 # 3 1 # 5
C
E
Turing
M=“
M
w
!
1. w (#(0+1)+)*
2. #
1
1
2
# #
#
2
3. #
4.
# #
# #
#
2
2
#
# #
# #
$ # 3 1 # 3 # 1 8 # 3 1 # 5
G.
G
Yes
4
1
No.
4
1
5
3
2
3
Yes
A={ <G> | G
<G>
}
!
G
!
G
!
4
G=(V, E)
V={1, 2, 3, 4}
E={(1,2),(2,3),(3,1),(1,4)}
<G>=
! G
1
3
2
( 1, 2, 3, 4) ( ( 1, 2) , ( 2, 3) , ( 3, 1) , ( 1, 4) )
2
No
4
4
1
1
3
A
3
2
2
Turing
M=“
1. w
2. G
3.
!
4. G
w
:
G
!
<G>
10
Turing
!
(
1
)
!
!
10
T
!
F
µ
µ:F×
!
!
F
n
×F
F n
F
A
µ
x1, …, xn A
µ(x1, …, xn)
T
A
L1, L2
T
A
L1
L2
T
7.1
7.1
1.
2.
3.
4.
5.
∩
!
L1, L2
!
M1, M2
L 1, L 2
2-DTM M
!
M=“
L1 L2 = {w| w=xy
L* = {w| w Ln
A
x L1, y L2
n≥0
1. T’
2
2. T’
3
3.
}
}
!
L1 ∩ L2
T0
w
M1
M2
T’
:
M1
M1
M2
M2
”
L1 ∩ L2
1-DTM
A
T
T
7.1
()c
7.1
!
L1, L2
!
M 1, M 2
L 1, L 2
2-DTM M
!
L1
M=“
1-DTM
L2
T0
w
1. T’
M1
2. T’
M2
3.
L1
!
!
L1
!
M1
M=“
:
M1
2
M2
”
3
M1
1. T’
M2
M1
T’
:
M1
M1
L1c
!
L2
T
7.1
()*
7.1
!
L1, L2
!
M 1, M 2
L 1, L 2
2-NTM M
1-DTM
L1 L2
M=“
T0
w
1.
2
T’
2.
M2
L1 L2
!
L1
!
M1
T’
L1
1-DTM
M=“
T0
w
:
m
(0≤m≤|w|)
M1
1.
M1
M2
L1c
2-DTM M
!
w
T’
!
L1c
T0
w
T
!
1-DTM
2-DTM M
!
T’
L1
2. T’
1
!
:
T0
T0
T’
”
T’
L1*
M1
M1
m
M1
(m>0)
T
Turing
7.2 Turing
1.
2.
3.
4.
T
7.1
T
%
T
7.2
∩
7.2
7.1
(
)
7.1
!
L1, L2
!
M 1, M 2
Turing
L 1, L 2
2-DTM M
!
M=“
1. T’
2
2. T’
3
3.
!
7.2
%
L1 ∩ L2
T0
w
M1
M2
1-DTM
!
L1, L2
!
M1, M2
M=“
M1
M1
1. T’
M2
M2
2. T’
Turing
M1
M2
3.
!
L1
L1
L2
1-DTM
L2
T0
w
:
”
L1 ∩ L2
L 1, L 2
2-DTM M
!
T’
Turing
T’
:
M1
2
M2
”
3
Turing
M1
M2
T
T
7.2
!
L1, L2
Turing
!
M 1, M 2
L 1, L 2
3-DTM M
!
M=“
L1
L1
7.1
1-DTM
7.2
L2
T0
w
1. T1, T2
M 1, M 2
!
!
!
T1, T2
:
M1, M2
L2
M 1, M 2
”
Turing
M1
M2
Turing
© Copyright 2024 ExpyDoc
