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

1Lý thuyết tính toán (Theory of Computation) i PGS.TS. Phan Huy Khánh [email protected] Chương 4 Máy Turing 2/58 Chương 4 Máy Turing  Máy Turing  Định nghĩa máy Turing  Ngôn ngữ thừa nhận được và ngôn ngữ xác định được  Các hàm tính được bởi máy Turing  Các ngôn ngữ đệ quy và liệt kê đệ quy  Luận đề Turing-Church  Kỹ thuật xây dựng máy Turing  Mở rộng các máy Turing  Máy turing không đơn định  Máy Turing vạn năng  Ôtômat tuyến tính giới nội  Văn phạm cảm ngữ cảnh 3/58 Mở đầu  Ôhh đẩy xuống không thể đoán nhận NN anbncn dù có hai bộ nhớ lớn tùy ý  Để thừa nhận anbncn, phải tìm kiếm các lớp ôtômat khác, đó là các máy Turing  Sự khác nhau căn bản giữa máy Turing và ô đẩy xuống :  Máy Turing chỉ có một bộ nhớ lớn tùy ý  Máy Turing có thể đọc và ghi  Cách sử dụng bộ nhớ là tuỳ ý, không hạn chế ở nguyên lý danh sách đẩy xuống (Stack hay LIFO) Alan Turung (19121954) : nhà Toán học người Anh, người đầu tiên nghiên cứu lý thuyết ôtômat năm 1936 4/58 Mô tả máy Turing đơn định Máy Turing đơn định (Deterministic Turing Machine) gồm :  Một băng vào/ra (IO Tape) :  Một đầu đọc-ghi (Read/Write Head) di chuyển trên băng  Một tập hợp hữu hạn các trạng thái trong đó có :  Một trạng thái đầu  Một tập hợp các trạng thái thừa nhận (cuối)  Một hàm chuyển tiếp qk X a b a b bY # # . . . 5/58 Mô tả chi tiết  Băng vào/ra :  Là một bộ nhớ vô hạn được chia thành nhiều ô  Mỗi ô có thể chứa một ký tự a nào đó (Tape Alphabet)  Băng chỉ có cận trái, cận phải quy ước có thể kéo dài vô hạn  Hàm chuyển tiếp gồm các tham đối :  Trạng thái hiện hành của máy  Ký tự đọc được ở vị trí dưới đầu đọc  Trạng thái tiếp theo của máy  Ký tự sẽ ghi lên băng tại vị trí ký tự vừa đọc được  Chiều di chuyển của đầu đọc-ghi (qua trái, phải hay đứng yên) 6/58 Cấu hình ban đầu của máy Turing  Cấu hình ban đầu của máy Turing được mô tả như sau :  Câu vào w  * nằm ở mút trái nhất của băng  Mỗi ô còn lại của băng chứa một ký hiệu đặc biệt, gọi là các ký hiệu trống (Blank Symbol)  Đầu đọc-ghi nằm ở ô đầu tiên của băng (mút trái nhất)  Máy đang ở trạng thái đầu tiên, giả sử q0  Máy sẵn sàng thực hiện bằng cách đọc ký hiệu ở vị trí đầu đọc q0 a a b a b bb # # . . . 27/58 Hoạt động của máy Turing Hoạt động của máy Turing được mô tả như sau :  Máy đọc ký hiệu nằm ở dưới đầu đọc  Tuỳ theo trạng thái hiện hành, hàm chuyển tiếp cho phép máy thực hiện :  Ghi đè lên ký hiệu vừa đọc một ký hiệu khác  Di chuyển đầu đọc-ghi sang phải, hoặc sang trái một ô  Thay đổi trạng thái  Máy thừa nhận câu khi đạt tới trạng thái thừa nhận, giả sử qj  F qj X X Y X X XY # # . . . 8/58 Định nghĩa hình thức máy Turing Máy Turing được mô tả bởi một bộ bảy : M = (Q, , , , q0, #, F) trong đó :  Q là tập hữu hạn các trạng thái   là bảng chữ ghi lên băng     là bảng chữ vào  q0  Q là trạng thái đầu  F  Q là tập hợp các trạng thái thừa nhận  #   -  là ký tự trống   : hàm chuyển tiếp 9/58 Mô tả hàm chuyển tiếp  Hàm chuyển tiếp :  : Q  QM gồm các phần tử (q, a) = (q’, x, m), trong đó : q, q’  Q ; a   ; x   ; m  M = { L, R } L chỉ định dịch đầu đọc-ghi sang trái (Left) R chỉ định dịch đầu đọc-ghi sang phải (Right)  Có thể viết gọn mỗi phần tử của  : hoặc (q, a, x, m, q’) hoặc qamxq’ 10/58 Cấu hình của máy Turing  Cấu hình (hay cấu hình) của máy Turing là một phần tử của quan hệ : (q, 1, 2)  Q** Trong đó :  q  Q : trạng thái hiện hành của máy  1 : phần câu trên băng phía trước vị trí đầu đọc-ghi  2 : Phần câu trên băng từ vị trí đầu đọc-ghi đến hết câu (ký tự cuối cùng khác ký tự trống #) q a a b a b bb # # . . . 1 2 11/58 Chuyển tiếp một bước C ├ C’  Cho cấu hình C = (q, 1, 2) và C’ = (q’, ’1, ’2) Giả sử 2 = b’2 trường hợp 2 = , lấy b = #  Chuyển tiếp một bước C ├ C’ được định nghĩa như sau :  Trường hợp 1 : Nếu  (q, b) = (q’, b’, R), ta có : (q, 1, b’2) ├ (q’, 1b’, ’2) với ’1 = 1b’ q a b b a b bb # ... 1 2 q’ a b’ b a b bb # ... ’2’2 ’1 ├ 12/58 Chuyển tiếp một bước C ├ C’  Cho cấu hình C = (q, 1, 2) và C’ = (q’, ’1, ’2) Giả sử 1 = ’1a 1   2 = b3 trường hợp 2 = , lấy b = #  Chuyển tiếp một bước C ├ C’ được định nghĩa như sau :  Trường hợp 2 : Nếu  (q, b) = (q’, b’, L), ta có : (q, ’1a, 2) ├ (q’, ’1, ab’3) với ’2 = ab’3 q b a b a b bb # ... ’1 1 q’ b a b’ a b bb # ... ’2 ’1 ├ 2 3 3 313/58 Chuyển tiếp nhiều bước  Cho cấu hình C = (q, 1, 2) và C’ = (q’, ’1, ’2)  Tương tự trong ôhh, ta nói chuyển tiếp nhiều bước C ├* C’ nễu: k  0 và các cấu hình trung gian C0, C1, . . ., Ck sao cho :  C  C0  C’  Ck  Ci ├ Ci+1 với 0  i  k 14/58 Máy Turing đoán nhận câu của ngôn ngữ  Máy Turing đoán nhận câu của một ngôn ngữ như là các ôtômat hữu hạn đã xét  Cho w   :  Câu w được một máy Turing M đoán nhận nễu : (q0, , w) ├* (qj, , 2) với , 2  *  Câu w được một máy Turing thừa nhận nễu : (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).