Bài giảng Lý thuyết tính toán - Chương 4: Máy Turing

:
(q0, , w) ├* (qj, , 2) với , 2  * và qj  F
 Một ngôn ngữ L được thừa nhận bởi một máy Turing M,
L = L(M), nễu :
L(M) = { w   (q0, , w) ├* (qj, , 2) với qj  F }
15/58
Ví dụ
 Cho máy Turing M  (Q, , , , q0, B, F) với :
 Q   q0, q1, q2, q3, q4 
   { a, b, X, Y, # },   { a, b } F  { q4}
  được cho bởi bảng dưới đây
(dấu "" chỉ ra rằng hàm chuyển tiếp không được định nghĩa)
q4
(q4, #, R)(q3, Y, R)q3
(q2, Y, L)(q0, X, R)(q1, a, L)q2
(q1, Y, R)(q2, Y, L)(q1, a, R)q1
(q3, Y, R)(q1, X, R)q0
#YXba
16/58
Đánh dấu con a
trái nhất
tr i t
Biểu diễn đồ thị
q4
(q4, #, R)(q3, Y, R)q3
(q2, Y, L)(q0, X, R)(q1, a, L)q2
(q1, Y, R)(q2, Y, L)(q1, a, R)q1
(q3, Y, R)(q1, X, R)q0
#YXba
a/X, R
q1q0
q4
Y/Y, R
q2
b/Y, L
Y/Y, R
a/a, R
a/a, L
X/X, R
Y/Y, R
Y/Y, R
#/#, R
q3
Vượt qua phảit i
17/58
Máy Turing đoán nhận câu a2b2
 Các chuyển tiếp đoán nhận câu aabb lần lượt như sau :
 q0aabb# q0XaYb# q0XXYY#
 q1Xabb# q1XXYb# q3XXYY#
 q1Xabb# q1XXYb# q3XXYY##
 q2XaYb# q2XXYY# q4XXYY##
 q2XaYb# q2XXYY# thừa nhận
18/58
Máy Turing đoán nhận câu a3b3
 dãy các chuyển tiếp từ câu vào aaabbb được cho như sau :
 q0aaabbb# q2XaaYbb# q2XXXYYY#
 q1Xaabbb# q0XaaYbb# q0XXXYYY#
 q1Xaabbb# . . . . . . . . . q3XXXYYY#
 q1Xaabbb# q1XXXYYb# q3XXXYYY#
 q2XaaYbb# q2XXXYYY# q3XXXYYY#
 q2XaaYbb# q2XXXYYY# q4XXXYYY##
 thừa nhận !
419/58
Ví dụ
 Máy Turing thừa nhận ngôn ngữ chính quy aa* + b(a+b)*
q1q0
a|a, R
#|#, L
0q 1q 2q3q
Rxa ,
Raa ,
Ryy ,
Lyb ,
Laa ,
Lyy ,
Rxx ,
Ryy ,
Ryy ,
4q
L,
20/58
Định nghĩa
 Máy Turing đoán nhận một câu w là thực hiện (xử lý)
một dãy cực đại các cấu hình :
(q0, , w) = C0 ├ C1 ... ├ Ck = (qk, k, k) ├ ... 
nghĩa là sao cho :
 Dãy tự kết thúc tại một cấu hình có chứa trạng thái kết thúc
và thừa nhận câu w
hoặc
 Dãy tự kết thúc tại một cấu hình không chứa trạng thái kết 
thúc mà từ đó, không còn cấu hình nào có thể chuyển đến : 
máy bị hóc
hoặc
 Dãy cấu hình là vô hạn, máy không bao giờ dừng
21/58
Tính xác định được (Deterministic)
 Một ngôn ngữ L được xác định bởi một máy Turing M nễu :
 M thừa nhận L
 M không có các xử lý vô hạn
 Nhận xét :
 Tồn tại thuật toán cho phép máy Turing đoán nhận một ngôn 
ngữ, hay kiểm tra tính xác định được
 Đối với các ôtômát hữu hạn đơn định, điều đó hiển nhiên
 Đối với một ôtômát hữu hạn không đơn định,
không phải luôn luôn tồn tại thuật toán,
vì :
Tại mỗi giai đoạn đoán nhận, không thể chỉ ra chuyển tiếp 
nào tiếp theo sẽ được chọn một cách tường minh 
22/58
Hình thức hóa tính xác định được 
 Tính xác định được của máy Turing có thể hiểu như sau : 
 Với mọi phần tử (q, a)  QG, tồn tại nhiều nhất một quy tắc 
(q, a)  (q’, a’, m), viết gọn qama’q’, với m  M={L, R}
 Hàm bộ phận QG  QGM có thể tách thành ba hàm :
 Hàm “ký tự mới” nc : QG  G
hay nc(q, a) = a’
 Hàm “di chuyển đầu đọc” mh : QG  M
hay mh(q, a) =m 
 Hàm “trạng thái mới” ns : QG  Q
hay ns(q, a) = q’
23/58
Máy Turing tính hàm
 Máy Turing có thể tính hàm theo cách hiểu như sau :
 Tham đối của hàm là câu vào w nằm trên băng
 Giá trị trả về của hàm là câu  được ghi trên băng
sau khi máy Turing kết thúc việc xử lý (đọc hết w)
 Máy Turing tính một hàm f :    nếu :
 Với một câu vào w bất kỳ, máy luôn luôn dừng trong một 
cấu hình mà f(w) có mặt ở trên băng
 Hàm f đgl tính được bởi một máy Turing nếu tồn tại một 
máy Turing tính được nó
24/58
Domain: D Result Region: S
A function f(w) has:
Dw  Swf )(
)(wf
Notation of Function
A function may have many parameters:
Example: Addition function
f(x, y) = x + y
525/58
Integer Domain
Unary:
Binary:
Decimal:
11111
101
5
We prefer unary representation:
easier to manipulate with TMs
Data representation
26/58
Definition:
A function is computable if
there is a Turing Machine such that: 
f
M
Initial configuration Final configuration
Dw Domain

0q
w 
fq
)(wf
final stateinitial state
For all
27/58
Initial 
Configuration
Final
Configuration
A function is computable if
there is a Turing Machine such that: 
f
M
In other words:
Dw DomainFor all
)(0 wfqwq f├─
28/58
Example
The function yxyxf ),( is computable
Turing Machine:
Input string: yx0 unary
Output string: 0xy unary
yx, are integers
29/58
 0
0q
1 1 1 1
x y
1 
Start
initial state
The 0 is the delimiter that 
separates the two numbers
Input representation
30/58
 0
fq
1 1
yx 
 11Finish
final state
 0
0q
1 1 1 1
x y
1 Start
initial state
Computing Function
631/58
 0
fq
1 1
yx 
 11Finish
final state
The 0 helps when we use
the result for other operations
Computing Function
32/58
Turing machine for function
yxyxf ),(
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
33/58
Execution Example (1)
 0
0q
1 1 1 1
Time 0
x y
Final Result
 0
4q
1 1 1 1
yx 
11x (2)
11y (2)
34/58
 0
0q
1 1Time 0 1 1
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (2)
35/58
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11

0q
01 11 1Time 1
Execution Example (3)
36/58
 0
0q
1 1 1 1Time 2
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (4)
737/58

1q
1 11 11Time 3
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (5)
38/58

1q
1 1 1 11Time 4
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (6)
39/58

1q
1 11 11Time 5
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (7)
40/58

2q
1 1 1 11Time 6
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (8)
41/58

3q
1 11 01Time 7
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (9)
42/58

3q
1 1 1 01Time 8
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (10)
843/58

3q
1 11 01Time 9
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (11)
44/58

3q
1 1 1 01Time 10
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (12)
45/58

3q
1 11 01Time 11
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
Execution Example (13)
46/58

4q
1 1 1 01Time 12
0q 1q 2q 3qL, L,01
L,11
R,
R,10 
R,11
4q
R,11
HALT & accept
Execution Example (14)
47/58
Another Example: f(x) = 2x (1)
The function xxf 2)(  is computable
Turing Machine:
Input string: x unary
Output string: xx unary
x is integer
48/58
 1
fq
1 1
x2
 11Finish
final state

0q
1 1
x
1Start
initial state
Another Example: f(x) = 2x (2)
949/58
TM Pseudocode for f(x) = 2x
• Replace every 1 with $
• Repeat:
• Find rightmost $, replace it with 1
• Go to right end, insert 1
Until no more $ remain
50/58
Example TM for f(x) = 2x
0q 1q 2q
3q
R,1$ 
L,1
L,
R$,1 L,11 R,11
R,

0q
1 1
Start

3q
1 11 1
Finish
51/58
T = ; S = { 0, 1, # } ; Q = {q1, q2, q3}
P = { q1, 1  1, R, q1,
q2, 0  1, L, q3,
q1, 0  0, R, q1,
q2, 1  0 L, q2,
q1, #  #, L, q2,
q2, #  1, L, q3 }
TM compute succ(n)
1q 3q
0|0, R
2q
1|1, R
1|0, L
#|1, L
#|#, R
0|1, L
52/58
Another Example
The function is 
computable ),( yxf
0
1 yx 
yx 
if
if
Turing Machine for
Input: yx0
Output: 1 0or
53/58
Turing Machine Pseudocode:
Match a 1 from with a 1 from x y
• Repeat
Until all of or is matchedx y
• If a 1 from is not matched
erase tape, write 1
else
erase tape, write 0
x
)( yx 
)( yx 
54/58
Các ngôn ngữ đệ quy và liệt kê đệ quy
 Các ngôn ngữ xác định được bởi một máy Turing được gọi 
là đệ quy (Recusive)
 Các ngôn ngữ được thừa nhận bởi một máy Turing gọi là
liệt kê đệ quy (Recursively Enumerable)
 Từ đó ta có các định nghĩa sau :
 Một ngôn ngữ là đệ quy nếu nó được xác định
bởi một máy Turing
 Một ngôn ngữ là liệt kê đệ quy nếu nó được thừa nhận
bởi một máy Turing
10
55/58
Luận đề Turing-Church
Luận đề Turing-Church phát biểu như sau :
 Các ngôn ngữ được nhận biết bởi một thuật 
toán là các ngôn ngữ xác định được bởi một 
máy Turing
Người ta có thể phát biểu luận đề Turing -
Church theo nghĩa của phép tính hàm :
 Các hàm tính được bởi một thuật toán là các 
hàm tính đợc bởi một máy Turing
Alonzo Church
(1903-1995) : nhà
Toán học người Mỹ 
đã nghiên cứu phép 
tính hàm 
(Functional 
Calculus) và tính 
tính được 
(Computability)
56/58
Nhận xét luận đề Turing-Church
 Luận đề Turing-Church đóng vai trò quan trọng trong
lý thuyết tính toán (Computability)
 Luận đề đưa ra lập luận rằng một số ngôn ngữ không thể 
được đoán nhận bởi một thuật toán : thực chất là hình thức 
hóa khái niệm tính toán
 Luận đề Turing-Church không phải là một định lý,
nên không thể chứng minh được
 Luận đề Turing-Church áp dụng mô hình lý thuyết là máy 
Turing được định nghĩa chặt chẽ để mô hình hoá quan niệm 
về thuật toán là khái niệm không được xác định rõ ràng
 Dễ dàng mô phỏng sự hoạt động của một máy Turing nhờ :
 Một bút chì và tờ giấy 
 Một chương trình chạy trên một máy tính cụ thể
57/58
Xây dựng máy Turing 
 Một số kỹ thuật xây dựng máy Turing
 Ghi nhớ ở bộ điều khiển hữu hạn
 Mở rộng băng vào vô hạn về cả hai phía
 Máy Turing có nhiều băng
 Máy Turing có bộ nhớ truy cập trực tiếp
58/58
Các máy Turing vạn năng
 Một vấn đề thú vị là liệu có thể có một máy Turing
mô phỏng được bất kỳ máy Turing nào ?
 Một cách tường minh, ta muốn cung cấp cho một máy 
Turing M sự mô tả của một máy Turing M’ bất kỳ nào đó
sao cho với một câu vào w nào đó, máy Turing M’ có thể
mô phỏng sự đoán nhận của M trên w  
 Một máy Turing như vậy sẽ là một sự nhại lại các máy 
Turing khác, và được gọi là máy Turing vạn năng 
(Universal Turing Machine).