1
Chương 2. THUẬT TOÁN PHỔ DỤNG

NỘI DUNG

2.1 Máy Turing phổ dụng
2.2 Vấn đề không tính được; Định lý Goedel
2.3 Tính khó của bài toán

TÀI LIỆU THAM KHẢO

1. Bài giảng về cơ sở tính toán tại địa chỉ (Chương 2)
2. Michael Sipser , Introduction to the Theory of Computation, 2nd edition, Couse
technology 2005 (Chương 3, 4, 5, 9)
3. Nguyễn Văn Ba. Lý thuyết ngôn ngữ và tính toán. NXB ĐHQG Hà nội, 2006 (Bài tập
1, 2 chương 5)

2
2.1. Máy Turing phổ dụng

Mô phỏng máy tính bằng máy Turing

Mô hình hoạt động của máy tính :

- Vùng lưu trữ của máy tính bao gồm một dãy (Có thể xem là vô hạn) chúa các từ nhớ
(word), mỗi từ có một địa chỉ (adress).

- Băng 4: lưu giữ nguyên liệu của máy tính.

- Băng 5: băng dùng chung. 4

Hình 1: Máy Turing mô phỏng máy tính
5
Máy Turing M thực hiện một chỉ thị của máy tính:
- Chép địa chỉ cần tìm vào băng 3
- So sánh với các địa chỉ trên băng 1 để tìm được địa chỉ cần tìm
- Chép nội dung của địa chỉ cần tìm vào băng 3 và di chuyển đến chỗ cần dùng nó.

Máy Turing M mô phỏng chu trình chỉ thị (Instruction Cycle) :
- Tìm trên băng 1 một địa chỉ theo đúng con số chỉ thị trên băng 2 bằng cách: bắt đầu tại $ trên
băng 1 và di chuyển sang phải, so mỗi địa chỉ với nội dung của băng 2.
- Khi đã tìm ra địa chỉ của chỉ thị, M xem xét giá trị của nó: khi từ nhớ là một chỉ thị, một số bit
đầu tiên biểu diễn hành động cần thực hiện và các bít còn lại là địa chỉ cần cho hành động đó.
- Nếu chỉ thị đòi hỏi giá trị của một địa chỉ khác thì địa chỉ đó phải là thành phần của chỉ thị: M
chép địa chỉ đó vào băng ba đánh dấu vị trí của chỉ thị nhờ rãnh thứ hai của băng 1 để quay về chỉ
thị nếu cần. M tìm địa chỉ bộ nhớ trên băng 1 và chép giá trị của nó vào băng 3 (đang chứa địa chỉ
của bộ nhớ đó).
- M thực hiện chỉ thị (hoặc một phần chỉ thị) liên quan đến giá trị này:

1
là trạng thái đầu, q
2
là trạng thái cuối (thừa nhận).
-  gồm s ký hiệu băng X
1
, X
2
, …, X
s
; X
1
là ký hiệu 0, X
2
là ký hiệu 1, X
3
là ký hiệu trắng B, các
ký hiệu băng khác có thể được gán cho các số nguyên còn lại một cách tùy ý.
- Hướng L ký hiệu là D
1
, hướng R là D
2
.
- Hàm chuyển (q
i
, X
j
) = (q
k
, X

7
Ví dụ 1. Cho máy Turing M = ({q
1
, q
2
, q
3
}, {0, 1}, {0, 1, B}, , q
1
, B, {q
2
}), trong đó

(q
1
, 1) = (q
3
, 0, R)
(q
3
, 1) = (q
2
, 0, R)
(q
3
, 0) = (q
1
, 1, R)
(q
3

Xét w
i
bất kỳ. Nếu w
i
không phải là bản mã có nghĩa của một máy Turing thì ta chọn M
i
là máy
Turing chỉ gồm 1 trạng thái và không có chuyển vị. Như vậy, M
i
là máy Turing sẽ dừng ngay lập
tức trên mọi nguyên liệu  L(M
i
) = .
Ngôn ngữ L
d
là ngôn ngữ chéo hóa (Diagonalzation Language)  L
d
= {w
i
w
i
 L(M
i
)}
 L
d
bao gồm tất cả các chuỗi w sao cho máy M với bản mã w không thừa nhận w.
Xét bảng gồm các ô (i, j) nhận giá trị 1 nếu máy M
i
thừa nhận chuỗi w

Nếu w
i
 L
d
 M
i
thừa nhận w
i
. Theo định nghĩa, w
i
 L
d
 Vô lý.
Nếu w
i
 L
d
 M
i
không thừa nhận w
i
. Theo định nghĩa, w
i
 L
d
 Vô lý. 9
4) Ngôn ngữ không kể được đệ qui


10
Ví du. Xây dựng một máy Turing M để thực hiện phép nhân hai số nguyên dương m, n.
- Input : 0
m
10
n
- Output : B0
mn
B
- Hoạt động của M : Trước hết M viết số 1 sau 0
m
10
n
, sau đó chép m lần liên tiếp khối n số
0, mỗi lần chép 1 khối, loại bớt 1 số 0 trong khối 0
m
 10
n
10
mn
. Cuối cùng cần xóa tiền tố
10
n
1  0
mn
còn lại trên băng là giá trị của hàm.
- Thiết kế một chương trình con CHEP :
Hình trạng bắt đầu : #0
m-i
q
2

(q
2
, 0, R)
(q
2
, 1, R)

(q
3
, 0, R)
q
3

(q
3
, 0, L)
(q
1
, 1, L)
(q
1
, 2, R)

q
4


(q
6
, B, R)
q
6

(q
6
, 0, R)
(q
6
, 1, R)

(q
7
, 1, L)
q
7

(q
7
, 0, L)
(q
1
, 1, R)


14
.
Hàm chuyển: 0
1
2
B
q
5

(q
5
, 0, L)
(q
8
, 1, L) q
8

(q
9
, 0, L) (q
10

12

(q
12
, 0, R)
(q
1
, 1, R) q
13

(q
13
, B, R)
(q
14
, B, R)
Tổng hợp:
- Q = {q
0
, q
1
, , q
14
};


13
7) Ngôn ngữ phổ dụng (Universal language) và máy Turing phổ dụng
(Universal Turing Machine)

L
u
là ngôn ngữ phổ dụng  L
u
là tập các chuỗi nhị phân mã hóa cặp (M, w), trong
đó M là máy Turing nào đó với bộ chữ cái nhị phân làm nguyên liệu, w là chuỗi nhị
phân sao cho w  L(M). Như vậy, L
u
là tập các chuỗi nhị phân biểu diễn một máy
Turing M và một nguyên liệu được thừa nhận bởi M.

Máy Turing U là máy Turing phổ dụng  L
u
= L(U).
Như vậy, máy Turing phổ dụng U thừa nhận cả dữ liệu vào và các mô tả quá trình
tính toán (thuật toán/chương trình).

Những máy tính đầu tiên có thể xem như là các phần cứng có thêm chương trình.
Để thay đổi quá trình tính hàm có thể tiến hành bằng cách ngắt kết nối dây dẫn
hoặc là xây dựng máy tính mới. John von Neumanm đã đề xuất sử dụng thuật
toán phổ dụng Turing. Các hàm được tính bằng cách thức mô tả chúng (chương
trình) như là một phần của dữ liệu vào sẽ thuận tiện hơn là thay đổi phần cứng

15
Hình 2: Mô hình máy Turing phổ dụng

16
Hoạt động của U:
(1) Xem xét nguyên liệu để đảm bảo bản mã cho M là một bản mã hợp lệ của một máy Turing nào đó.
Nếu không U sẽ dừng và không thừa nhận.
(2) Khởi gán băng thứ hai với nguyên liệu w ở dạng mã hóa: với mỗi 0 của w đặt 10 lên băng thứ hai,
với mỗi 1 của w đặt 100 tại đó. Ký hiệu trắng trên băng cần mô phỏng của M biểu diễn bởi 1000. Tất
cả các ô nằm ngoài phần được dùng cho w đều giữ ký hiệu trắng của U.
(3) Đặt 0, khởi trạng của M trên băng thứ ba và di chuyển đầu đọc-ghi ở băng hai của U đến ô đầu tiên
cần mô phỏng.
(4) Mô phỏng một bước chuyển của M: U tìm băng thứ nhất của nó một chuyển vị dạng 0
i
10
j
10
k
10
l
10

17
U thừa nhận cặp (M, w)  M thừa nhận w.

Tính không giải được của ngôn ngữ phổ dụng:
Định lý 2. L
u
là ngôn ngữ kể được đệ qui nhưng không đệ qui.

Gọi R là lớp các hàm tính được toàn phần hoặc bộ phận. Xét u  R là hàm phổ
dụng. Hàm u sẽ mô phỏng mọi hàm f  R với thời gian c
2
T và không gian S+c, trong đó
S, T > xlà không gian và thời gian tính f(x), c là độ dài của chương trình.

Như vậy, u đòi hỏi phần đầu m của dữ liệu vào mx là danh sách các lệnh của
máy Turing M và trạng thái khởi tạo của đầu đọc-ghi.
Hàm u(mx) được thực hiện theo chu trình. Mỗi chu trình mô phỏng một bước
của M(x). Sau khi thực hiện bước thứ i của M(x), l
i
là phần băng bên trái, r
i
là phần
băng bên phải (kể từ đầu đọc-ghi) và s
i
là trạng thái của đầu đọc. Cấu hình của băng
của u(mx) sau khi chu trình i là t
i
= l
i
ms

 Các sự kiện ủng hộ cho khẳng định của luận đề Turing-Church:
Mọi mở rộng của máy Turing đều không tăng sức mạnh của máy.
Mọi mô hình hóa hợp lý khác của khái niệm thủ tục hữu hiệu đã được đề xuất cho
đến nay đều tương đương với các máy Turing như:
- Hệ thống Post
- -tính toán
- Dạng chuẩn Markov
- Các hàm đệ qui

19
2.2. Vấn đề không tính được; Định lý Goedel
2.2.1. Các hàm phổ dụng và đầy đủ
 Lựa chọn một dấu ghi đặc biệt và sau khi nó xuất hiện lần thứ k, phân chia xâu x thành
Prefix
k
(x) và Suffix
k
(x). Ký hiệu f
+
(x) là f(Prefix
k
(x)) và f
–
(x) là f( Suffix
k
(x)).
 Hàm u là k-mô phỏng f nếu với p = Prefix
20
2.2.2. Định lý Goedel
Có các hàm không đầy đủ trong số các hàm tính được (đệ qui) toàn phần. Lớp các
hàm tính được là đóng với phép phủ định. Vì vậy, hàm u (và u
2
= (u mod 2)) phổ dụng
trong R có mở rộng tính được không toàn phần.
Chứng minh hình thức rằng, các hệ thống tính được các hàm A(P) bằng cách kiểm
tra nếu P là chứng minh được thừa nhận và kết quả thông báo được xác thực. - s có
nghĩa là s = A(P) với P nào đó. A là đa năng nếu nó cho phép tính được bản dịch s
x

của khẳng định “ u
2
(x) = 0” được chứng tỏ luôn đúng và bác bỏ (- -s) mỗi khi u
2
(x) =
1. A là phù hợp nếu tối đa có một cặp tùy ý s
x
, -s
x
được xác thực và là đầy đủ nếu ít
nhất một trong chúng luôn là xác thực (tương đương khi u(x) phân kỳ). Một hệ hình
thức đầy đủ và phù hợp đa năng không tồn tại, bởi vì nó sẽ đưa ra một mở rộng toàn
phần hiển nhiên u
A
của u
2

Ju. Matijasevich đã đưa ra một tập hợp kể được đệ qui đối với bài toán phương trình
Diophang : Cho một đa thức bậc 4 với hệ số nguyên ; tìm nghiệm nguyên của đa thức.
Phép thu bài toán P
1
về bài toán P
2
là một thuật toán biến đổi các thể hiện của P
1

thành các thể hiện của P
2
và có cùng trả lời đúng hoặc sai.
22
a) Các hàm đệ qui nguyên thủy
Cho { 
k
   k  0} là tập hợp các hàm (toàn phần) mà các đối số (với số lượng k bất kỳ) và
giá trị của hàm đều là các số tự nhiên.
Hàm đệ qui nguyên thủy cơ sở là các hàm sau :
(1) Hàm không 0() : không có đối số và luôn nhận giá trị 0.
(2) Các hàm chiếu 
i
k
(n
1
, …, n
k

Ví dụ. Các hàm đệ qui nguyên thủy:
- Hàm hằng J()= j  J() = (( (0()))) (j lần )
- Hàm cộng plus(n
1
, n
2
) = n
1
+n
2
 plus(n
1
, 0) = 
1
1
(n
1
);
plus(n
1
, n
2
+1) = (
3
3
(n
1
, n
2
, plus(n

k
 {sai, đúng} k  0}
Hàm đặc trưng của tân từ P  
k
là hàm f: 
k
 {0, 1} sao cho
f(X) =





PX
PX
,0
,1

Tân từ P là đệ qui nguyên thủy  hàm đặc trưng f của P là đệ qui nguyên thủy. 24
Ví dụ. Các tân từ đệ qui nguyên thủy:
- Tân từ không: m = 0 chỉ đúng khi m = 0  có hàm đặc trưng zero:
zero(0) = 1; zero(m+1) = 0
- Tân từ nhỏ thua: n < m  có hàm đặc trưng nhothua: nhothua(n,m) = sign(nm)
- Tân từ bằng: n = m  có hàm đặc trưng bang:
bang(n, m) = 1  (sign(mn) + sign(nm))
- Phép tối tiểu hóa giới nội của hàm từ tân từ q(X,i) với cận m: im q(X,i) 
im q(X,i) = số nhỏ nhất i  m sao cho q(X,i) đúng và im q(X,i) = 0 nếu


Hàm f là -đệ qui  f là T-tính được