1. Cho máy Turing M = (Σ, Q, Γ, δ, q
0
, B, F), trong đó Σ = {0, 1}, Q = {q
0
, q
1
, q
2
, q
3
, q
4
},
Γ = { 0, 1, B}, F = {q
4
} và δ được cho bởi bảng sau
0 1 B
→q
0
(q
0
, 0, R) (q
1
, 1, L)
q
1
(q
1
, 0, L) (q
1
, 1, L) (q

δ(q
0
, 0) = (q
0
, 0, R): Gặp 0, thay 0 bởi 0, chuyển q
0
và dịch phải.
δ(q
0
, 1) : Dừng và không thừa nhận.
δ(q
0
, B) = (q
1
, 1, L): Gặp B, thay B bởi 1, chuyển q
8
và dịch trái.
δ(q
1
, 0) = (q
1
, 0, L): Gặp 0, thay 0 bởi 0, chuyển q
1
và dịch trái.
δ(q
1
, 1) = (q
1
, 1, L): Gặp 1, thay 1 bởi 1, chuyển q
1

3
và dịch phải.
δ(q
3
, 1) = (q
3
, 1, R): Gặp 1, thay 1 bởi 1, chuyển q
3
và dịch phải.
δ(q
3
, B) = (q
3
, 1, R): Gặp B, thay B bởi 0, chuyển q
4
và dịch phải.
δ(q
4
, 0) : Dừng và thừa nhận.
δ(q
4
, 1) : Dừng và thừa nhận.
δ(q
4
, B) = (q
1
, 0, L): Gặp B, thay B bởi 0, chuyển q
1
và dịch trái.
2

00 ⇒ BB0q
1
100 ⇒ BBq
1
0100 ⇒ Bq
1
B0100 ⇒ BBq
2
0100
⇒BBBq
3
100 ⇒ BBB1q
3
00 ⇒ BBB10q
3
0 ⇒ BBB100q
3
B ⇒ BBB1000q
4
B ⇒ BBB100q
1
00 ⇒
BBB10q
1
000 ⇒ BBB1q
1
0000 ⇒ BBBq
1
10000 ⇒ BBq
1

3
2. Cho máy Turing M = (Σ, Q, Γ, δ, q
0
, B, F), trong đó Σ = {x, y, z}, Q = {q
0
, q
1
, q
2
}, Γ = {x, y,
z, B}, F = {q
2
} và δ được cho bởi bảng sau
x y z B
→q
0
(q
0
, x, R) (q
0
, y, R) (q
1
, x, R) (q
0
, B, R)
q
1
(q
0
, x, R) (q

6
}, Γ = {1, 2, 3, B}, F = {q
6
} và δ được cho bởi bảng sau
1 2 3 B
→q
0
(q
1
, B, R) (q
0
, B, R)
q
1
(q
1
, 1, R) (q
2
, B, R) (q
1
, B, R)
q
2
(q
2
, 2, R) (q
3
, B, R) (q
2
, B, R)

5
4. Cho máy Turing ngẫu nhiên RM chỉ có 1 băng input và băng ngẫu nhiên. Mỗi ký hiệu trên
băng có dạng (XY), trong đó X là ký hiệu trên băng input, Y là ký hiệu trên băng ngẫu nhiên.
Mỗi hướng di chuyển có dạng (DE), trong đó D là hướng di chuyển của đầu đọc-ghi trên băng
input, E là hướng di chuyển của đầu đọc-ghi trên băng ngẫu nhiên. Biết rằng, đầu đọc-ghi có thể
di chuyển sang phải (R), sang trái (L) hoặc đứng yên (S). Bảng hàm chuyển δ:
00 01 10 11 B0 B1
→ q
0
q
1
00RS q
3
01SR q
2
10RS q
3
11SR
q
1
q
1
00RS q
4
B0SS
q
2
q
2
10RS q

0
, 00) = (q
1
, 00, R,S): Gặp 00, thay 00 bởi 00, chuyển q
1
và dịch phải trên băng Input và
đứng yên trên băng ngẫu nhiên
δ(q
0
, 01) = (q
3
, 01, S, R): Gặp 01, thay 01 bởi 01, chuyển q
3
và đứng yên băng Input và dịch
phải trên băng ngẫu nhiên
δ(q
0
, 10) = (q
2
, 10, R,S): Gặp 10, thay 10 bởi 10, chuyển q
2
và dịch phải trên băng Input và
đứng yên trên băng ngẫu nhiên
δ(q
0
, 11) = (q
3
, 11, S, R): Gặp 11, thay 11 bởi 11, chuyển q
3
và đứng yên băng Input và dịch

4
và đứng yên trên băng Input
và đứng yên trên băng ngẫu nhiên
7
δ(q
3
, 00) = (q
1
, 00, R, R): Gặp 00, thay 00 bởi 00, chuyển q
1
và dịch phải trên băng Input và
dịch phải trên băng ngẫu nhiên
δ(q
3
, 11) = (q
3
, 11, R, R): Gặp 11, thay 11 bởi 11, chuyển q
3
và dịch phải trên băng Input và
dịch phải trên băng ngẫu nhiên
δ(q
3
, B0) = (q
4
, B0, S, S): Gặp B0, thay B0 bởi B0, chuyển q
4
và đứng yên trên băng Input
và đứng yên trên băng ngẫu nhiên
δ(q
3

3
, 01), δ(q
3
, 10): Dừng và không thừa nhận
δ(q
4
, 00), δ(q
4
, 01), δ(q
4
, 10), δ(q
4
, 11), δ(q
4
, B0), δ(q
4
, B1): Dừng và thừa nhận
b) Mô tả quá trình thực hiện của M trên các xâu
(i) Xét w = 11111 và rw = 00101: q
0
11111|q
0
00101 ⇒ 1q
2
1111|q
0
00000 ⇒ 11q
2
111|q
2

2
1001|1q
2
0101 ⇒
11q
2
001|1q
2
0101: Dừng và RM không thừa nhận w.
c) Xác suất để w được thừa nhận bởi RM :
(i) w = 1111111 thì tổng xác suất thừa nhận w là
7
2
2
1
2
1
−
+
= 2
-1
+ 2
-(7+1)
=
256
129
(ii) w = 1001100 có tổng xác suất thừa nhận w bằng 2
-(7+1)
=
256

Bảng hàm chuyển như sau:
10
0 1 x B
→q
0
(q
1
, B, R) (q
4
, B, R) (q
0
, x, R) (q
5
, B, L)
q
1
(q
1
, 0, R) (q
2
, B, R) (q
1
, x, R)
q
2
(q
2
, 0, R) (q
2
, 1, R) (q

, q
3
, q
4
, q
5
}, Γ = {0,
1, B, x}, F = {q
5
} và δ được cho bởi bảng trên.
11
6. Thiết kế máy Turing thừa nhận các xâu nhị phân W có số lượng kí tự 0 bằng số lượng kí tự 1.
Giải
Máy Turing M thừa nhận xâu nhị phân w sẽ hoạt động như sau :
q
0
là trạng thái ban đầu, đầu đọc ghi ở ô đầu tiên của input.
Bước 1: Nếu gặp 0 thì thay thế 0 bởi B, dịch phải và chuyển bước 2; Nếu gặp 1 thì thay thế 1 bởi
B, dịch phải và chuyển bước 3; Nếu gặp B thì thay thế B bởi B, dừng và thừa nhận w; nếu gặp x
thì giữ nguyên và dịch phải;
Bước 2: Nếu gặp 0 hoặc x thì giữ nguyên và dịch phải; Nếu gặp 1 thì thay thế 1 bởi x, dịch trái
và chuyển bước 4; Nếu gặp B thì dừng và không thừa nhận;
Bước 3: Nếu gặp 1 hoặc x thì giữ nguyên và dịch phải; Nếu gặp 0 thì thay thế 0 bởi x, dịch trái
và chuyển bước 4; Nếu gặp B thì dừng và không thừa nhận;
Bước 4: Nếu gặp 0, 1, x thì giữ nguyên và dịch trái; Nếu gặp B thì giữ nguyên, dịch phải và
chuyển bước 1;
12
Bảng hàm chuyển:
0 1 x B
→q

(q
3
, 0, L) (q
3
, 1, L) (q
3
, x, L) (q
0
, B, R)
*q
4
13
7. Thiết kế máy Turing kiểm tra một xâu x với các kí tự thuộc tập hợp {a, b, c} có phải là xâu đối
xứng hay không? Nếu x đối xứng thì giá trị trên băng là 1, ngược lại, giá trị trên băng là 0.
Giải
Máy Turing M kiểm tra tính đối xứng của xâu x sẽ hoạt động như sau :
q
0
là trạng thái ban đầu, đầu đọc ghi ở ô đầu tiên của input.
Bước 1 : Thay thế kí tự đầu tiên của x là B, dịch phải. Nếu kí tự đầu tiên là 0 thì chuyển bước 2 ;
Nếu kí tự đầu tiên là 1 thì chuyển bước 3; ngược lại chuyển bước 4.
Bước 2 : Tìm ký tự cuối cùng của x. Nếu không tìm được thì thay thế B bởi 1, dịch trái và dừng.
Nếu tìm được và = 0 thì chuyển bước 5 ; ≠ 0 thì chuyển bước 6.
Bước 3 : Tìm ký tự cuối cùng của x. Nếu không tìm được thì thay thế B bởi 1, dịch trái và dừng.
Nếu tìm được và = 1 thì chuyển bước 5; ≠ 1 thì chuyển bước 6.
Bước 4: Tìm ký tự cuối cùng của x. Nếu không tìm được thì thay thế B bởi 1, dịch trái và dừng.
Nếu tìm được và = 2 thì chuyển bước 5; ≠ 1 thì chuyển bước 6.
Bước 5: Tìm ký tự đầu tiên của x. Nếu tìm được thì chuyển bước 1. Nếu không tìm được thì
thay thế B bởi 1, dịch trái và dừng.
Bước 6: Thay thế kí tự vừa tìm bởi 0, dịch trái và chuyển bước 7 ;

, 0, R) (q
2
, 1, R) (q
2
, 2, R) (q
5
, B, L)
q
3
(q
3
, 0, R) (q
3
, 1, R) (q
3
, 2, R) (q
6
, B, L)
q
4
(q
7
, B, L) (q
8
, 0, L) (q
8
, 0, L) (q
9
, 1, R)
q

0
, B, R)
q
8
(q
8
, B, L) (q
8
, B, L) (q
8
, B, L) (q
9
, B, R)
*
q
9
⇒ M = (Σ, Q, Γ, δ, q1, B, F), trong đó Σ = {0, 1, 2}, Q = {q
0
, q
1
, q
2
, q
3
, q
4
, q
5
, q
6

(q
0
, B, R) (q
1
, B, R) (q
2
, 1, L)
q
1
(q
1
, B, R) (q
0
, B, R) (q
2
, 0, L)
*
q
2
Như vậy, xây dựng được máy Turing M = (Σ, Q, Γ, δ, q
0
, B, F), trong đó Σ = {0, 1}, Q =
{q
0
, q
1
, q
2
}, Γ = {0, 1, B}, F = {q
2

21
21
11
Output : f(x) =
yB
aa
21
1
+
Máy Turing M thực hiện hàm cộng sẽ hoạt động như sau :
Bước 1: Số 1 bên trái nhất sẽ được thay thế bởi B và dịch phải.
Bước 2: Tìm x
2
thay thế x
2
bởi 1, dịch phải gặp B thay thế B bởi x
2
, dịch phải gặp y thay thế y
bởi B, dịch phải găp B thay thế B bởi y dịch trái và chuyển sang bước 3.
Bước 3: Tìm 1 bên trái nhất trước x
1
. Nếu tìm được chuyển bước 1. Nếu không tìm được thì
chuyển bước 4.
Bước 4: Thay thế x
1
bởi B; thay thế x
2
bởi y, thay thế y bởi B và dừng.
17
Bảng hàm chuyển:

2
(q
2
, 1, L) (q
2
, x
1
, L) (q
2
, x
2
, L) (q
0
, B, R)
q
3
(q
3
, 1, R) (q
3
, y, R) (q
4
, B, L) (q
0
, B, R)
*q
4
Như vậy, xây dựng được máy Turing M = (Σ, Q, Γ, δ, q
0
, B, F), trong đó Σ = {1}, Q = {q

y
Giải
Input : w = 1
m
x
1
1
n
x
2
y
Output : Nếu m ≤ n ⇒ TRU(w) = 0y. Nếu m > n ⇒ TRU(w) = 1
m-n
y
Máy Turing M thực hiện hàm TRU(m, n) sẽ hoạt động như sau :
Bước 1: Số 1 bên trái nhất sẽ được thay thế bởi B và dịch phải.
Bước 2: Nếu tìm được số 1 đầu tiên trước x
2
thì nó sẽ được thay thế bởi B, dịch trái và
chuyển sang bước 3. Nếu không tìm được thì gặp y, thay y bởi 1 và dịch phải. Gặp B thì thay B
bởi y, dịch trái và chuyển bước 4.
Bước 3: Tìm 1 bên trái nhất trước x
1
. Nếu tìm được chuyển bước 1. Nếu không tìm được thì
chuyển bước 5.
Bước 4: Chuyển tất cả 1 trước x
1
sang bên trái y và chuyển sang bước 6.
Bước 5: Thay thế x
1

1
, R) (q
2
, x
2
, L)
q
2
(q
3
, B, L) (q
4
, x
1
, L)
q
3
(q
3
, 1, L) (q
3
, x
1
, L) (q
0
, B, R)
q
4
(q
4

, R) (q
6
, x
2
, R) (q
6
, 1, R) (q
4
, y, L)
q
7
(q
9
, 1, L) (q
7
, B, R)
q
8
(q
8
, B, R) (q
8
, B, R) (q
8
, 0, R) (q
9
, y, L)
*q
9
Như vậy, máy Turing M = (Σ, Q, Γ, δ, q

11. a) Thiết kế máy Turing M tính giá trị hàm nhân f(x) trên tập các số nguyên dương như sau:
f(x) = f(a
1
, a
2
) = a
1
* a
2
, trong đó input x =
Byxx
aa
21
21
11
, còn output là giá trị của f(x) =
y
aa
21
*
1
.
b) Tính giá trị f(2, 3).
c) Đánh giá độ phức tạp tính toán của M.
Giải
a) Máy Turing M tính hàm f(x) = f(a
1
, a
2
) = a

yBxBx
aaa
2
*
1
2
2
1
11
. Cuối cùng cần xóa tiền tố
2
2
1
1 xx
a
⇒
yB
aa
2
*
1
1
còn lại trên
băng là giá trị của hàm.
Hàm chuyển :
21
1 2 x
1
x
2

, x
2
, R) (q
4
, y, L) (q
3
, 1, R)
q
4
(q
4
, 1, L) (q
5
, 2, R) (q
4
, x
2
, L)
q
5
(q
6
, 2, R) (q
7
, x
2
, L)
q
6
(q

8
, 1, R) (q
7
, y, R)
q
9
(q
9
, 1, L) (q
9
, 1, L) (q
9
, x
1
, L) (q
10
, B, R)
q
10
(q
11
, B, R) (q
12
, B, R)
q
11
(q
11
, 1, R) (q
5

, , q
14
}, Γ = {1, 2, x
1
, x
2
, y, B}, F = {q
14
} và δ được cho bởi bảng trên.
b) Tính giá trị f(2, 3) : x = 11x
1
111x
2
By ⇒ … ⇒ 111111y.
Vậy f(2, 3) = 6.
c) Đánh giá độ phức tạp tính toán của M :
Đặt n = max(a
1
, a
2
). Có T(n) ≤ 2(2n+5)(2n + 3)
2
⇒ T(n) = O(n
3
)
L(n) ≤ 2n + 5 + n
2
⇒ L(n) = O(n
2
).

, u
2
, …, u
n
là các số nhị phân.
b) Tính giá trị của MA(0110).
c) Đánh giá độ phức tạp tính toán của M.
Giải
a) Máy Turing M tính giá trị của hàm MA(x), trong đó input x = u
1
u
2
…u
n
uBy, output là giá trị
của hàm MA(x) = Cod(u
1
)Cod(u
2
)…Cod(u
n
)y, còn u
1
, u
2
, …, u
n
là các số nhị phân hoạt động như
sau:
q

4
, x, R)
q
3
(q
3
, 1, R) (q
5
, 0, R)
q
4
(q
4
, 0, R) (q
5
, 1, R)
q
5
(q
6
, y, L)
q
6
(q
6
, 0, L) (q
6
, 1, L) (q
6
, x, L) (q

, 1, R) (q
9
, x, R) (q
9
, 1, R) (q
5
, 0, R)
*q
10
Như vậy, xây dựng được máy Turing M = (Σ, Q, Γ, δ, q
0
, B, F), trong đó Σ = {0, 1}, Q = {q
0
, q
1
,
q
2
, q
3
, q
4
, q
5
, q
6,
q
7
, q
8