Bài giảng Lý thuyết tính toán: Chương 4 - PGS.TS. Phan Huy Khánh

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

117
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết tính toán chương 4 giới thiệu về máy Turing với một số nội dung liên quan như: Đị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, một số kỹ thuật xây dựng máy Turing,... Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết tính toán: Chương 4 - PGS.TS. Phan Huy Khánh

Chương 4 Máy Turing  Máy Turing  Định nghĩ nghĩa má máy Turing Lý thuyế thuyết tí thuyết ính toá ttính toán toán  Ngôn ngữ ngữ thừ thừa nhậ nhận đượ được và và ngôn ngữ ngữ xác đị định đượ được  Các hà hàm tí tính đượ được bở bởi mámáy Turing (Theory (Theory of of Computation) Computation)  Các ngôn ngữ ngữ đệ đệ quy vàvà liệ liệt kê đệ đệ quy PGS.TS. Phan Huy Khá Khánh  Luậ Luận đề đề Turing- Turing-Church khanhph@vnn.vn  Kỹ thuậ thuật xây dự dựng mámáy Turing  Mở rộng cá các má máy Turing  Máy turing không đơn đị định Chương 4  Máy Turing vạ vạn năng M áy Turing Máy  Ôtômat tuyế tuyến tí tính giớ giới nộ nội  Văn phạ phạm cảcảm ngữ ngữ cảnh 2/58 2/58 Mở đầ đầu Mô tả tả máy Turing đơn đị định  Ôhh đẩ đẩy xuố xuống không thểthể đoá đoán nhậ nhận NN Máy Turing đơn đị định (Deterministic Turing Machine) gồ gồm : anbncn dù có hai bộbộ nhớ nhớ lớn tù tùy ý  Một băng và vào/ra (IO Tape) :  Để thừ nhận anbncn, phả thừa nhậ phải tì tìm kiế kiếm các lớ lớp ôtômat khá khác, đó đó là các má má y Turing  Một đầ đầu đọ đọc-ghi (Read/Write Head) di chuyể chuyển trên băng  Sự khá khác nhau căn bả bản giữ giữa mámáy Turing  Một tậ tập hợ hợp hữ hữu hạ hạn cá các trạ trạng thá thái trong đó đó có : và ô đẩ đẩy xuố xuống :  Một trạ trạng thá thái đầ đầu  Máy Turing chỉ chỉ có một bộ bộ nhớ nhớ lớn tù tùy ý Alan Turung  Một tậ tập hợ hợp cá cá c trạ trạng thá thái thừ thừa nhậ nhận (cuố (cuối) (1912 (19121954) :  Máy Turing cócó thể thể đọ đọc và và ghi nhà nhà Toá Toán họ học  Một hà hàm chuyể chuyển tiế tiếp  Cách sử sử dụng bộ bộ nhớ nhớ là tuỳ tuỳ ý, ngườ người Anh, không hạhạn chế chế ở nguyên lý danh sásách ngườ ngư đ tiên ờ i đầ ầ u nghiên cứ cứu Y X a b a b b # # ... đẩy xuố xuống (Stack hay LIFO) lý thuyế thuyết ôtômat năm 1936 qk 3/58 3/58 4/58 4/58 Mô tả tả chi tiế tiết Cấu hì hình ban đầ đầu củ của má máy Turing  Băng và vào/ra :  Cấu hì hình ban đầ đầu củ của má máy Turing đượ được mô tả tả như sau :  Là một bộ bộ nhớ nhớ vô hạ hạn đượ được chia thà thành nhiề nhiều ô  vào w  * nằm ở mút trá Câu và trái nhấ nhất củ của băng  Mỗi ô có có thể thể chứ chứa mộ một ký tự tự a nào đó đó (Tape (Tape Alphabet)  Mỗi ô còn lạ lại củ của băng chứ chứa mộ một ký hiệ hiệu đặ đặc biệ biệt,  Băng chỉ chỉ có cận trá trái, cậ cận phả phải quy ướ ước có có thể thể kéo dà dài vô hạ hạn gọi là là các ký hiệ hiệu trố trống (Blank (Blank Symbol)  Hàm chuyể chuyển tiế tiếp gồ gồm cá các tham đố đối :  Đầu đọ đọc-ghi nằ nằm ở ô đầ đầu tiên củ của băng (mú (mút trá trái nhấ nhất)  Trạ Trạng thá thái hiệ hiện hà hành củ của má máy  Máy đang ở trạ trạng thá thái đầ đầu tiên, giả giả sử q0  Ký tự tự đọ đọc đượ được ở vị trí trí dướ dưới đầ đầu đọ đọc  Máy sẵsẵn sà sàng thự thực hiệ hiện bằ bằng cá cách đọ đọc ký hiệ hiệu  Trạ Trạng thá thái tiế tiếp theo củ của má máy ở vị trí trí đầ đầu đọ đọc  Ký tự tự sẽ ghi lên băng tạ tại vị vị trí trí ký tự tự vừa đọ đọc đượ được  Chiề Chiều di chuyể chuyển củ của đầ đầu đọđọc-ghi b a a b a b b # # ... (qua trá trái, phả phải hay đứ đứng yên) q0 5/58 5/58 6/58 6/58 1
Hoạ Hoạt độ động củ của má máy Turing Định nghĩ nghĩa hì hình thứ thức má máy Turing Hoạ Hoạt độ động củ của má máy Turing đượ được mô tả tả như sau : Máy Turing đượ được mô tả tả bởi mộ một bộ bộ bảy :  Máy đọ đọc ký hiệ hiệu nằ nằm ở dướ dưới đầ đầu đọ đọc M = (Q, , , , q0, #, F)  Tuỳ Tuỳ theo trạ trạng thá thái hiệ hiện hà hành, trong đó đó : hàm chuyể chuyển tiế tiếp cho phé phép má máy thự thực hiệ hiện :  Q là là tập hữ hữu hạ hạn cá các trạ trạng thá thái  Ghi đè đè lên ký hiệ hiệu vừ vừa đọ đọc mộ một ký hiệ hiệu khá khác   là bảng chữ chữ ghi lên băng  Di chuyể chuyển đầ đầu đọ đọc-ghi sang phả phải, hoặ hoặ c sang trá trá i mộ một ô     là bảng chữ chữ vào  Thay đổ đổi trạ trạng thá thái  q0  Q là là trạ trạng thá thái đầ đầu  Máy thừ thừa nhậ nhận câu khi đạ đạt tớ tới trạ trạng thá thái thừ thừa nhậ nhận, giả giả sử qj  F  F  Q là là tập hợ hợp cá các trạ trạng thá thái thừ thừa nhậ nhận  #   -  là ký tự tự trố trống Y X X Y X X X # # ...  : hà  hàm chuyể chuyển tiế tiếp qj 7/58 7/58 8/58 8/58 Mô tả tả hàm chuyể chuyển tiế tiếp Cấu hì hình củ của má máy Turing  Hàm chuyể chuyển tiế tiếp :  Cấu hì hình (hay cấ cấu hì hình) củ của má máy Turing  : Q Q  QM M là một phầ phần tử hệ : (q, 1, 2)  Q** tử của quan hệ Trong đó đó : gồm cá các phầ phần tử (q’, x, tử (q, a) = (q’ x, m), đó : m), trong đó  q  Q : trạ trạng thá thái hiệ hiện hà hành củ của má má y q, q’ q’  Q ; a  ; x; m  M = { L, R }  1 : phầ phần câu trên băng phí phía trướ trước vị vị trí trí đầ đầu đọ đọc-ghi L chỉ chỉ đị định dị dịch đầ đầu đọ đọc-ghi sang trá trái (Left)  2 : Phầ Phần câu trên băng từ từ vị trí trí đầ đầu đọ đọc-ghi đế đến hế hết câu (ký tự tự cuố cuối cù cùng khá khác ký tự tự trố trống #) R chỉ chỉ đị định dị dịch đầ đầu đọ đọc-ghi sang phả phải (Right)  Có thể thể viế viết gọ mỗi phầ gọn mỗ phần tử tử của  : 1 2 hoặ hoặc (q, a, x, m, q’ q’) b a a b a b b # # ... hoặ hoặc qa qamxq’ mxq’ q 9/58 9/58 10/58 10/58 Chuyể Chuyển tiế tiếp mộ bước C ├ C’ một bướ Chuyể Chuyển tiế tiếp mộ bước C ├ C’ một bướ  Cho cấ cấu hì hình C = (q, 1, 2 ) và và C’ = (q’ (q’, ’1, ’2)  Cho cấ cấu hì hình C = (q, 1, 2 ) và và C’ = (q’ (q’, ’1, ’2) Giả Giả sử 2 = b b’2 trườ trường hợ hợp 2 = , lấ lấy b = # Giả Giả sử 1 = ’1a 1   2 = b b3 trườ trường hợhợp 2 = , lấlấy b = #  Chuyể Chuyển tiế tiếp mộ bước C ├ C’ đượ một bướ được đị định nghĩ nghĩa như sau :  Chuyể Chuyển tiế tiếp mộ bước C ├ C’ đượ một bướ được đị định nghĩ nghĩa như sau :  Trườ Trường hợ hợp 1 : Nế Nếu  (q, b) = (q’ (q’, b’ b’, R), ta có có :  Trườ Trường hợ hợp 2 : Nế Nếu  (q, b) = (q’ (q’, b’ b’, L), ta có có : (q, 1, b b’2) ├ (q’ (q’, 1b’, ’2) với ’1 = 1b’ (q, ’1a, 2 ) ├ (q’ (q’, ’1, ab’ ab’3) với ’2 = ab’ ab’3 2 1 2 ’2 1 ’1 ’2 ’2 ’1 ’1 3 3 b a b b a b b # ... ├ b a b’ b a b b # ... b b a b a b b # ... ├ b b a b’ a b b # ... q q’ q q’ 11/58 11/58 12/58 12/58 2
Chuyể Chuyển tiế tiếp nhiề nhiều bướ bước Máy Turing đoá đoán nhậ nhận câu củ của ngôn ngữ ngữ  Cho cấ cấu hì hình C = (q, 1, 2 ) và và C’ = (q’ (q’, ’1, ’2)  Máy Turing đoá đoán nhậ nhận câu củ của mộ một ngôn ngữ ngữ như là là các  Tương tự tự trong ôhh, ta nó nói chuyể chuyển tiế tiếp nhiề nhiều bướ bước ôtômat hữ hữu hạ hạn đã xé xét C ├* C’ nễ u:  Cho w   : k  0 và và các cấ cấu hì hình trung gian C0, C1, . . ., Ck sao cho :  Câu w đượ được mộ một má máy Turing M đoá đoán nhậ nhận nễu :  C  C0 (q0, , w) ├* (qj, , , 2) vớ với , , 2  *  C’  Ck  Câu w đượ được mộ một má máy Turing thừ thừa nhậ nhận nễu :  Ci ├ Ci+1 với 0  i  k (q0, , w) ├* (qj, , , 2) vớ với , , 2  * và và qj  F  Một ngôn ngữ ngữ L đượ được thừ thừa nhậ nhận bở bởi mộ một má máy Turing M, L = L(M), nễu : L(M) = { w   (q (q0, , w) ├* (qj, , , 2) vớ với qj  F } 13/58 13/58 14/58 14/58 V í dụ Biể Biểu diễ diễn đồ đồ thị thị a b X Y #  Cho má máy Turing M  (Q, , , , q0, B, F) vớ với : q0 (q1, X, R)   (q3, Y, R)  q1 (q1, a, R) (q2, Y, L)  (q1, Y, R)   Q   q0, q1, q2, q3, q4  q2 (q1, a, L)  (q0, X, R) (q2, Y, L)  q3    (q3, Y, R) (q4, #, R)    { a, b, X, Y, # },   { a, b } F  { q4} q4      Vượ Vượt qua Vượt qua phả phải phải   đượ được cho bở bởi bả bảng dướ dưới đây Đ ánh dấ Đánh ấu con ddấu con aa (dấ (dấu " "" chỉ chỉ ra rằ rằng hà hàm chuyể chuyển tiế tiếp không đượ được đị định nghĩ nghĩa) trá trái nhấ trái nh ất nhất a b X Y # X/X, R Y/Y, R Y/Y, R q0 (q1, X, R)   (q3, Y, R)  a/X, R b/Y, L q0 q0 q1 q1 q2 q2 q1 (q1, a, R) (q2, Y, L)  (q1, Y, R)  a/a, L q2 (q1, a, L)  (q0, X, R) (q2, Y, L)  Y/Y, R a/a, R q3    (q3, Y, R) (q4, #, R) #/#, R Y/Y, R q3 q3 q4 q4 q4      15/58 15/58 16/58 16/58 Máy Turing đoá nhận câu a2b2 đoán nhậ Máy Turing đoá nhận câu a3b3 đoán nhậ  Các chuyể chuyển tiế tiếp đoá đoán nhậ nhận câu aabb lầ lần lượ lượt như sau :  dãy cá các chuyể chuyển tiế tiếp từ từ câu và và o aaabbb đượ được cho như sau :  q0aabb# q0XaYb# q0XXYY#  q0aaabbb# q2XaaYbb# q2XXXYYY#  q1Xabb# q1XXYb# q3XXYY#  q1Xaabbb# q0XaaYbb# q0XXXYYY#  q1Xabb# q1XXYb# q3XXYY##  q1Xaabbb# ......... q3XXXYYY#  q2XaYb# q2XXYY# q4XXYY##  q1Xaabbb# q1XXXYYb# q3XXXYYY#  q2XaYb# q2XXYY# thừ thừa nhậ nhận  q2XaaYbb# q2XXXYYY# q3XXXYYY#  q2XaaYbb# q2XXXYYY# q4XXXYYY##  thừa nhận ! 17/58 17/58 18/58 18/58 3
V í dụ Định nghĩ nghĩa  Máy Turing thừ thừa nhậ nhận ngôn ngữ ngữ chí chính quy aa* + b(a+b)*  Máy Turing đoá đoán nhậ nhận mộ một câu w là thự thực hiệ hiện (xử (xử lý) một dãy cự cực đạ đại cá các cấ cấu hì hình : a|a, R (q0, , w) = C0 ├ C1 ... ├ Ck = (qk, k, k) ├ ... #|#, L nghĩ nghĩa là là sao cho : q0 q1  Dãy tự tự kết thú thúc tạ tại mộ một cấ cấu hì hình có có chứ chứa trạ trạng thá thái kế kết thú thúc và thừ thừa nhậ nhận câu w q4 y  y, R y  y, L hoặ hoặc y  y, R a  a, R a  a, L   , L  Dãy tự tự kết thú thúc tạ tại mộ một cấ cấu hì hình không chứ chứa trạ trạng thá thái kế kết thú thúc mà mà từ đó đó, không còn cấcấu hì hình nà nào có có thể thể chuyể chuyển đế đến : y  y, R a  x, R b  y, L máy bị bị hóc q3 q0 q1 q2 hoặ hoặc x  x, R  Dãy cấu hình là là vô hạ hạn, má máy không bao giờ giờ dừng 19/58 19/58 20/58 20/58 Tính xá xác đị định đượ được (Deterministic) Hình thứ thức hó hóa tí tính xá xác đị định đượ được  Một ngôn ngữ ngữ L đượ được xá xác đị định bở bở i mộ một má máy Turing M nễ u :  Tính xá xác đị định đượ được củ của má máy Turing có có thể thể hiể hiểu như sau :  M thừ thừa nhậ nhận L  Với mọ mọi phầ phần tửtử (q, a)  QG, tồ tồn tạ tại nhiề nhiều nhấ nhất mộ một quy tắ tắc  M không có có các xử xử lý vô hạ hạn (q, a)  (q’ (q’, a’ a’, m), viế viết gọ gọn qama’ qama’q’, vớ với m  M={L, R}  Nhậ Nhận xé xét :  Hàm bộ bộ phậ phận Q QG  QGM có có thể thể tách thà thành ba hà hàm :  Tồn tạ tại thuậ thuật toá toán cho phé phép mámáy Turing đoá đoán nhậ nhận mộ một ngôn  Hàm “ký tự tự mới” nc : QG  G ngữ ngữ, hay kiể kiểm tra tí tính xá xác đị định đượ được hay nc(q, a) = a’ a’  Đối vớ với cá các ôtômá ôtômát hữhữu hạ hạn đơn địđịnh, điề điều đó đó hiể hiển nhiên  Hàm “di chuyể chuyển đầ đầu đọ đọc” mh : QG  M  Đối vớ với mộ một ôtômá ôtômát hữhữu hạ hạn không đơn đị định, hay mh(q, a) =m không phả phải luôn luôn tồ tồn tạ tại thuậ thuật toá toán,  Hàm “trạ trạng thá thái mớ mới” ns : QG  Q vì : hay ns(q, a) = q’ q’ Tại mỗ mỗi giai đoạ đoạn đoá đoán nhậ nhận, không thể thể chỉ chỉ ra chuyể chuyển tiế tiếp nào tiế tiếp theo sẽ sẽ đượ được chọ chọn mộ một cá cách tườ tường minh 21/58 21/58 22/58 22/58 Máy Turing tí tính hà hàm Notation of Function  Máy Turing có có thể thể tính hà hàm theo cá cách hiể hiểu như sau : A function f(w) has:  Tham đố đối củ của hà hàm là là câu và vào w  nằm trên băng w  Domain: D Result Region: S  Giá Giá trị trị trả trả về của hà hàm là là câu  đượ được ghi trên băng sau khi má máy Turing kế kết thú thúc việ việc xử xử lý (đọc hế hết w) f (w ) wD f (w)  S  Máy Turing tí tính mộ một hà hàm f :    nếu :  Với mộ một câu và vào w w bất kỳ kỳ, má máy luôn luôn dừ dừng trong mộ một cấu hì hình mà mà f(w) có có mặt ở trên băng  Hàm f đgl tí tính đượ được bở bởi mộ một má máy Turing nế nếu tồ tồn tạ tại mộ một A function may have many parameters: máy Turing títính đượ được nó nó Example: Addition function f(x, y) = x + y 23/58 23/58 24/58 24/58 4
Data representation Definition: Integer Domain A function f is computable if there is a Turing Machine M such that: Decimal: 5 Binary: 101 Initial configuration Final configuration  w   f (w)  Unary: 11111 q0 initial state q f final state We prefer unary representation: easier to manipulate with TMs For all w D Domain 25/58 25/58 26/58 26/58 In other words: Example A function f is computable if The function f ( x, y )  x  y is computable there is a Turing Machine M such that: x, y are integers q0 w  ├─ q f f ( w) Turing Machine: Initial Final Input string: x0 y unary Configuration Configuration For all w D Domain Output string: xy 0 unary 27/58 27/58 28/58 28/58 Input representation Computing Function x y x y Start Start  1 1  1 0 1  1   1 1  1 0 1  1  q0 initial state initial state q0 x y The 0 is the delimiter that Finish  1 1  1 1 0  separates the two numbers q f final state 29/58 29/58 30/58 30/58 5
Computing Function Turing machine for function f ( x, y )  x  y The 0 helps when we use the result for other operations 1  1, R 1  1, R 1  1, L x y q0 0  1, R q1   , L q2 1 0, L q3 Finish  1 1  1 1 0    , R q f final state 31/58 31/58 q4 32/58 32/58 Execution Example (1) Execution Example (2) x  11 (2) Time 0  1 1 0 1 1  y  11 (2) q0 1  1, R 1  1, R 1  1, L Time 0 Final Result x y x y  1 1 0 1 1   1 1 1 1 0  q0 0  1, R q1   , L q2 1 0, L q3 q0 q4   , R 33/58 33/58 q4 34/58 34/58 Execution Example (3) Execution Example (4) Time 1  1 1 0 1 1  Time 2  1 1 0 1 1  q0 q0 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 35/58 35/58 q4 36/58 36/58 6
Execution Example (5) Execution Example (6) Time 3  1 1 1 1 1  Time 4  1 1 1 1 1  q1 q1 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 37/58 37/58 q4 38/58 38/58 Execution Example (7) Execution Example (8) Time 5  1 1 1 1 1  Time 6  1 1 1 1 1  q1 q2 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 39/58 39/58 q4 40/58 40/58 Execution Example (9) Execution Example (10) Time 7  1 1 1 1 0  Time 8  1 1 1 1 0  q3 q3 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 41/58 41/58 q4 42/58 42/58 7
Execution Example (11) Execution Example (12) Time 9  1 1 1 1 0  Time 10  1 1 1 1 0  q3 q3 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 43/58 43/58 q4 44/58 44/58 Execution Example (13) Execution Example (14) Time 11  1 1 1 1 0  Time 12  1 1 1 1 0  q3 q4 1  1, R 1  1, R 1  1, L 1  1, R 1  1, R 1  1, L q0 0  1, R q1   , L q2 1 0, L q3 q0 0  1, R q1   , L q2 1 0, L q3   , R   , R q4 45/58 45/58 HALT & accept q4 46/58 46/58 Another Example: f(x) = 2x (1) Another Example: f(x) = 2x (2) The function f ( x)  2 x is computable x x is integer Start  1 1  1  Turing Machine: q0 initial state Input string: x unary 2x Output string: xx unary Finish  1 1  1 1 1  q f final state 47/58 47/58 48/58 48/58 8
TM Pseudocode for f(x) = 2x Example TM for f(x) = 2x Start Finish • Replace every 1 with $  1 1   1 1 1 1  q0 q3 • Repeat: 1  $, R 1  1, L 1  1, R • Find rightmost $, replace it with 1 • Go to right end, insert 1 q0   , L q1 $  1, R q2 Until no more $ remain   , R   1, L q3 49/58 49/58 50/58 50/58 TM compute succ(n) Another Example T = ; S = { 0, 1, # } ; Q = {q1, q2, q3} P = { q1, 1  1, R, q1, The function is 1 if xy q2, 0  1, L, q3, q1, 0  0, R, q1, computable f ( x, y )  q2, 1  0 L, q2, q1, #  #, L, q2, 0 if x y q2, #  1, L, q3 } 1|0, L Turing Machine for 1|1, R 0|1, L Input: x0 y #|#, R q1 q2 q3 Output: 1 or 0 #|1, L 0|0, R 51/58 51/58 52/58 52/58 Turing Machine Pseudocode: Các ngôn ngữ ngữ đệ đệ quy và và liệ liệt kê đệ đệ quy • Repeat  Các ngôn ngữ ngữ xác đị định đượ được bở bởi mộ một má máy Turing đượ được gọ gọi là đệ quy (Recusive) Match a 1 from x with a 1 from y  Các ngôn ngữ ngữ đượ được thừ thừa nhậ nhận bở bởi mộ một má máy Turing gọ gọi là là liệ liệt kê đệ đệ quy (Recursively Enumerable) Until all of x or y is matched  Từ đó đó ta có có các đị định nghĩ nghĩa sau :  Một ngôn ngữ ngữ là đệ đệ quy nếnếu nó nó đượ được xá xác đị định bởi mộ một má máy Turing • If a 1 from x is not matched  Một ngôn ngữ ngữ là liệ liệt kê đệ đệ quy nế nếu nó nó đượ được thừ thừa nhậ nhận erase tape, write 1 ( x  y) bởi mộ một má máy Turing else erase tape, write 0 ( x  y) 53/58 53/58 54/58 54/58 9
Luậ Luận đề đề Turing- Turing-Church Nhậ Nhận xé xét luậ luận đề đề Turing- Turing-Church Luậ  Luậ Luận đề đề Turing- Turing-Church đó đóng vai trò quan trọ trọng trong Luận đề đề Turing- Turing-Church phá phát biể biểu như sau : lý thuyế thuyết tí tính toá toán (Computability)  Các ngôn ngữ đượ được nhận biết bởi một thuật toá là các ngôn ngữ xác đị toán là định đượ được bởi một  Luậ Luận đề đề đưa ra lậ lập luậ luận rằ rằng mộ một số số ngôn ngữ ngữ không thể thể máy Turing đượ được đoá đoán nhậ nhận bởbởi mộ một thuậ thuật toá toán : thự thực chấ chất là là hình thứ thức hóa khá khái niệ niệm tí tính toá toán Ngườ Ngườ i ta có có thể thể phá phát biể biểu luậ luận đề đề Turing -  Luậ Luận đề đề Turing- Turing-Church không phảphải là là một đị định lý, Church theo nghĩ nghĩa củ của phé phép tí tính hà hàm : Alonzo Church nên không thể thể chứ chứng minh đượ được  Các hà hàm títính đượ được bởi một thuật toá toán là là các (1903- (1903-1995) : nhà nhà  Luậ Luận đề đề Turing- Turing-Church áp dụ dụng mô hìhình lý thuyế thuyết là là máy hàm títính đợ đợc bởi một má máy Turing Toá Toán họ học ngườ người Mỹ Mỹ Turing đượ được đị định nghĩ nghĩa chặ chặt chẽ chẽ để để mô hì hình hoá hoá quan niệ niệm đã nghiên cứ cứu phé phép tính hà hàm về thuậ thuật toá toán là là khá khái niệ niệm không đượ được xá xác đị định rõ rà ràng (Functional  Dễ dàng mô phỏ phỏng sự sự hoạ hoạt độ động củ của mộ một má máy Turing nhờ nhờ : Calculus) và và tính tính đượ được  Một bú bút chì chì và tờ giấ giấy (Computability)  Một chương trì trình chạ chạy trên mộ một má máy tí tính cụ cụ thể thể 55/58 55/58 56/58 56/58 Xây dự dựng má máy Turing Các má máy Turing vạ vạn năng  Một số số kỹ thuậ thuật xây dự dựng má máy Turing  Một vấ vấn đề đề thú thú v ị là liệ liệu có có thể thể có một má máy Turing  Ghi nhớ nhớ ở bộ điề điều khiể khiển hữ hữu hạ hạn mô phỏ phỏng đượ được bấ bất kỳkỳ máy Turing nà nào ?  Mở rộng băng và vào vô hạ hạn về về cả hai phí phía  Một cá cách tườ tường minh, ta muố muốn cung cấcấp cho mộ một má máy  Máy Turing có có nhiề nhiều băng Turing M sự sự mô tả tả của mộ một má má y Turing M’ M’ bất kỳ kỳ nào đó đó sao cho vớ với mộ một câu và và o w nà o đó đó, má máy Turing M’ M’ có thể thể  Máy Turing có có bộ nhớ nhớ truy cậ cập trự trực tiế tiếp mô phỏ phỏng sự sự đoá đoán nhậ nhận củ của M trên w    Một má máy Turing như vậ vậ y sẽ sẽ là một sự sự nhạ nhại lạ lạ i cá các má máy Turing khá khác, và và đượ được gọ gọi là là máy Turing vạ vạn năng (Universal Turing Machine). 57/58 57/58 58/58 58/58 10