›
›

Giáo trình Lý thuyết tính toán - Phan Huy Khánh

pdf 108 trang huongle 3770
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết tính toán - Phan Huy Khánh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ly_thuyet_tinh_toan_phan_huy_khanh.pdf

Nội dung text: Giáo trình Lý thuyết tính toán - Phan Huy Khánh

  1. ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH LÝ THUYẾT TÍNH TOÁN PGS.TS. PHAN HUY KHÁNH ĐÀ NẴNG 1999
  2. MỤC LỤC CHƯƠNG 1 NHẬP MÔN LÝ THUYẾT TÍNH TOÁN 1 I. CÁC ĐỐI TƯỢNG ĐƯỢC XỬ LÝ TRONG TIN HỌC 1 II. CÁC MÁY (MACHINES) 2 II.1. Khía cạnh chức năng (functional look) 2 II.2. Khía cạnh cấu trúc (structural look) 3 III. MÔ HÌNH TÍNH TOÁN 4 IV. ĐỊNH NGHĨA BÀI TOÁN 5 CHƯƠNG 2 MÔ HÌNH CÁC MÁY RAM 9 I. CÁC MÁY RAM 9 II. MÔ PHỎNG MỘT MÁY BỞI MỘT MÁY KHÁC 16 III. MỘT MÔ HÌNH THÔ SƠ KIỂU RAM 19 III.1. Mô phỏng các phép toán trên chuỗi ký tự bởi các phép toán trên các số nguyên 19 III.2. Thu gọn tập hợp các lệnh ngắt 20 III.3. Thu gọn tập hợp các lệnh số học 20 IV. MÁY RAM VẠN NĂNG 22 CHƯƠNG 3 MÔ HÌNH CÁC MÁY TURING 25 I. MÔ TẢ VÀ HOẠT ĐỘNG CỦA MÁY TURING 25 I.1. Mô tả máy Turing 25 I.2. Hoạt động của máy Turing 26 I.3. Cấu hình xuất phát của máy Turing 29 I.4. Máy Turing đơn định 29 II. CAC HÀM T-TÍNH ĐƯỢC 30 III. LỚP CÁC HÀM T-TÍNH ĐƯỢC 32 III.1. Một số hàm sơ cấp 32 III.1.1. Các hàm hằng (constant functions) 32 III.1.2. Các hàm chiếu (projection functions) 33 III.2. Các hàm kế tiếp (successor functions) 33 III.3. Các hàm kế trước (predecessor functions) 34 III.4. Sự hợp thành (composition) 34 III.3.1. Các máy được tiêu chuẩn hóa 35 III.3.2. Các máy Turing được chuẩn hóa 36 III.3.3. Tổ hợp các máy Turing 36 III.5. Lập trình trên ngôn ngữ bậc cao máy Turing 37 III.4.1. Cấu trúc if then else và cấu trúc rẽ nhiều nhánh 37 III.4.2. Cấu trúc while 38 III.6. Quản lý bộ nhớ 39 III.5.1. Máy Turing chuyển một ô qua phải 39 PGS.TS. PHAN HUY KHÁNH biên soạn 1
  3. 2 Lý thuyết tính toán III.5.2. Máy Turing chỉ sử dụng phần băng bên phải kể từ vị trí đầu tiên của đầu đọc-ghi 39 III.7. Một số máy Turing thông dụng 40 III.6.1. Sao chép 40 III.6.2. Kiểm tra bằng nhau 41 III.6.3. Liệt kê các câu, các cặp câu và dãy các câu 41 III.6.4. Các hàm chiếu ngược (antiprojection function) 42 III.6.5. Các hàm giao hoán 42 III.7. Các hàm T-tính được phức tạp hơn 42 III.8. Nhận xét 43 IV. CÁC BIẾN THẾ KHÁC CỦA MÔ HÌNH MÁY TURING 46 IV.1. Mô phỏng một máy Turing bởi một máy khác 46 IV.2. Các biến thể của máy Turing 48 IV.2.1. Máy Turing có k băng 48 IV.2.2. Các máy off−line và các máy có băng ra 49 IV.2.3. Các máy Turing không đơn định 49 IV.2.4. Thu gọn một bảng chữ còn ba ký tự 50 IV.2.5. Rút gọn một bảng chữ còn hai ký tự 52 IV.3. Các máy Turing có băng vô hạn một phía 52 V. MÁY TURING VẠN NĂNG 53 VI. TỒN TẠI CÁC HÀM KHÔNG LÀ T−TÍNH ĐƯỢC 55 CHƯƠNG 4 LUẬN ĐỀ CHURCH 59 I. TƯƠNG ĐƯƠNG GIỮA CÁC MÔ HÌNH MÁY TURING VÀ MÁY RAM 59 I.1. Mọi hàm T-tính được cũng là R−tính được 59 I.2. Mọi hàm R−tính được cũng là T−tính được 60 I.2.1. Tăng nội dung thanh ghi n lên 1 60 I.2.2. Giảm 1 nội dung thanh ghi n 60 I.2.3. Đưa nội dung thanh ghi n về 0 60 I.2.4. Nhảy theo nội dung thanh ghi n 61 I.2.5. Hoán vị nội dung hai thanh ghi n và m 61 I.3. Sự khác nhau giữa máy Turing và máy RAM 61 II. MÔ HÌNH CÁC HÀM ĐỆ QUY 62 II.1. Các hàm đệ quy nguyên thủy (primitive recursive functions) 62 II.1.1. Xây dựng các hàm sơ cấp 62 II.1.2. Sơ đồ hợp thành tổng quát 62 II.1.3. Sơ đồ đệ quy đơn (simple recurrence) 63 II.1.4. Sơ đồ đệ quy đồng thời 63 II.1.5. Các hàm được định nghĩa bởi case 65 II.2. Các hàm đệ quy 67 II.2.1. Sơ đồ tối thiểu 67 II.2.2. Các hàm đệ quy trừu tượng (abstract recursive functions) 68 II.2.3. Một số ví dụ 68 II.3. Các hàm đệ quy đều T−tính được 70 II.3.1. Sơ đồ hợp thành tổng quát 70 II.3.2. Sơ đồ đệ quy đơn 70 II.3.3. Sơ đồ tối thiểu 71
  4. Nhập môn lý thuyết tính toán 3 II.4. Mọi hàm T−tính được là đệ quy bộ phận 71 III. LUẬN ĐỀ CHURCH 73 CHƯƠNG 5 CÁC BÀI TOÁN KHÔNG QUYẾT ĐỊNH ĐƯỢC 77 I. CÁC NGÔN NGỮ LIỆT KÊ ĐỆ QUY VÀ CÁC NGÔN NGỮ ĐỆ QUY 77 II. CÁC BÀI TOÁN KHÔNG QUYẾT ĐịNH ĐƯỢC 82 III. THUẬT TOÁN RÚT GỌN MỘT BÀI TOÁN VỀ BÀI TOÁN KHÁC 83 CHƯƠNG 6 ĐỘ PHỨC TẠP TÍNH TOÁN 93 I. ĐỘ PHỨC TẠP VỀ THỜI GIAN VÀ VỀ BỘ NHỚ 84 II. CÁC LỚP CỦA ĐỘ PHỨC TẠP 84 II.1. Hiện tượng nén 84 II.2. Các họ P, NP và P−bộ nhớ (P−space) 84 III. RÚT GỌN ĐA THỨC VÀ CÁC BÀI TOÁN NP−ĐẦY ĐỦ 84 III.1. Khái niệm 84 III.2. Các bài toán cổ điển 84 III.3. Ví dụ về rút gọn kiểu đa thức 84
  5. CHƯƠNG 1 Nhập môn lý thuyết tính toán (Introduction to the theory of computation) It’s not bad being the small fish. I. Các đối tượng được xử lý trong Tin học Trong Tin học, các đối tượng (objects) được xử lý thông thường là những phần tử thuộc vào những tập hợp vô hạn đếm được. Những phần tử này luôn luôn được biểu diễn (represented) dưới một dạng nào đó. Chẳng hạn trong ngôn ngữ tự nhiên, số nguyên 1999 được biểu diễn trong hệ đếm cơ số 10 (hệ thập phân) gồm một dãy bốn chữ số thập phân thuộc bảng chữ số {0, 1, , 9}. Việc xử lý (thực hiện các phép toán số học thông thường) đối với các số nguyên được tiến hành trên cách biểu diễn cơ số 10 này. Ví dụ : Phép cộng hai số 1999 + 1 = 2000. Người ta giả thiết rằng các đối tượng được xử lý là những câu (word, hay sentence) được xây dựng trên một bảng chữ (alphabet) hữu hạn, được xem như là sự biểu diễn của đối tượng trong một bản chất khác. Định nghĩa 1.1 : Một bảng chữ S là một tập hợp hữu hạn các chữ (letters), hay là các ký tự (symbols, hay characters). Số lượng các ký tự, còn gọi là bản số (cardinality) hay lực lượng của S, được ký hiệu ||S||, hay |S|, nếu không sợ nhầm lẫn. Một câu, hay một từ, trên bảng chữ S đã cho là một dãy hữu hạn các ký tự của bảng chữ S được viết liên tiếp nhau. Độ dài (length) của một câu (trên bảng chữ S đã cho) là số lượng các ký tự có mặt trong câu. Câu rỗng (empty word), được ký hiệu là e (ω hoặc e, hoặc l), là câu có độ dài không, tức không chứa ký tự nào. Ghép (concatenation) của hai câu là đặt kế tiếp hai câu đã cho (trên cùng dòng) để nhận được một câu mới. Bằng cách ghép liên tục như vậy cho mọi ký tự, mọi câu của S, ta nhận được một tập hợp chứa mọi câu có thể trên S, ký hiệu S*. Người ta nói S*là một cấu trúc đồng đẳng (nonoide), mà phần tử trung hòa (neutral element) chính là câu rỗng. Cho trước một bảng chữ S, người ta định nghĩa một quan hệ có thứ tự toàn phần (total order) trên S* như sau : cho một thứ tự tùy ý trên các ký tự của S, PGS.TS. PHAN HUY KHÁNH biên soạn 1
  6. 2 Lý thuyết tính toán người ta sắp xếp các câu theo một thứ tự phân cấp (hierechical order), đầu tiên là theo độ dài câu, sau đó theo thứ tự từ vựng (lexicography), hay thứ tự ABC. Ví dụ : Cho S = {a, b, c}, với giả thiết thứ tự phân cấp của các ký tự là a < b < c, ta có thể đánh số các câu của S* (kể cả câu rỗng e) bắt đầu từ 1 trở đi như sau : e 1 a 2 b 3 c 4 aa 5 ab 6 ac 7 ba 8 bb 9 bc 10 ca 11 cb 12 cc 13 aaa 14 aab 15 aac 16 . . . Hình 1.1. Thứ tự phân cấp trong S* II. Các máy (machines) II.1. Khía cạnh chức năng (functional look) Một máy (machine) được biểu diễn một cách hệ thống như sau : Dữ liệu vào Dữ liệu ra Máy Hình 1.2. Khía cạnh chức năng của một máy Ở lối vào, người ta cung cấp một hoặc nhiều dữ liệu (data) cho máy, thì lối ra, người ta nhận được kết quả (result). Giả thiết rằng các dữ liệu vào có dạng là dãy các ký tự, là một câu trên một bảng chữ nào đó đã cho (vào từ bàn phím chẳng hạn). Kết quả là một phần tử của một tập hợp xác định trước (predefini). Người ta phân biệt các kiểu máy (machine type) tùy theo bản chất của tập hợp kết quả này như sau : 1. Nếu tập hợp chỉ có hai phần tử { không, có } hay {0, 1}, máy sẽ chia dữ liệu vào thành ba phần tùy theo kết quả :  Tập hợp các câu trên bảng chữ vào sau khi được xử lý sẽ cho ra một kết quả là có (đúng, true), hoặc không (sai, false).  Tập hợp các câu mà máy đưa ra một kết quả khác.  Tập hợp các câu trên bảng chữ vào mà máy không cho kết quả nào.
  7. Nhập môn lý thuyết tính toán 3 Các tập hợp này tạo thành các ngôn ngữ (language). Hai tập hợp đầu là bù nhau nếu với mọi dữ liệu vào, máy đều cho một kết quả. Người ta gọi đó là máy đoán nhận (recognition machine) câu. 2. Nếu kết quả là một dãy hữu hạn các ký tự, ta nhận được một câu trên một bảng chữ G nào đó. Cho S là bảng chữ vào, máy xác định một hàm f từ S* vào G*, ta viết : f : S* → G* nghĩa là với một câu vào w ∈ S*, f(w) ∈ G*. Người ta nói máy thực hiện hàm f. Nếu với mọi câu vào w ∈ S*, máy đều cho một kết quả f(w) ∈ G*, thì f được gọi là hàm toàn phần (partial function). Người ta gọi đó là máy tính toán (computation machine) hay máy tính. Chú ý rằng kiểu máy thứ nhất (máy đoán nhận) mà chúng ta vừa phân biệt thực ra chỉ là một trường hợp đặc biệt của kiểu máy thứ hai (máy tính). 3. Nếu kết quả là một dãy vô hạn các ký tự và bảng chữ đang sử dụng chỉ có tối thiểu hai ký tự, trong đó có một dấu phân cách (separator) #, thì người ta nhận được kết quả là một dãy liên tiếp các câu phân cách nhau bởi dấu #, tạo thành một ngôn ngữ. Người ta gọi ngôn ngữ này là liệt kê được (enumerated) bởi máy. II.2. Khía cạnh cấu trúc (structural look) Ở đây, ta chỉ quan tâm đến các máy được mô tả đầy đủ về chức năng hoạt động của chúng. Những máy này có thê :  Thực hiện các phép toán sơ cấp (elementary operation) trong một khoảng thời gian hữu hạn. Mỗi phép toán, giả thiết không chia cắt nhỏ hơn được, được chọn trong một tập hợp hữu hạn các phép toán là một phần mô tả cấu trúc máy.  Lần lượt thực hiện các phép toán sơ cấp theo một thứ tự xác định trước, tạo thành một chương trình (program), là một phần mô tả cấu trúc máy. Một dãy các phép toán sơ cấp được máy thực hiện liên tiếp được gọi là một tính toán (computation) của máy.
  8. 4 Lý thuyết tính toán III. Mô hình tính toán Thay vì phải thay đổi lại máy tính mỗi lần thay đổi bài toán cần giải, người ta định nghĩa các lớp máy có cùng nguyên lý hoạt động và chúng chỉ khác nhau ở chương trình. Người ta gọi mô hình tính toán (model), ký hiệu T, là sự mô tả tất cả các phép toán sơ cấp có thể được thực hiện trên những đối tượng nào, cách tác động lên mỗi một trong chúng như thế nào, và mô tả cách thức chương trình được thực hiện (execution) trên máy. Một trường hợp riêng (instance) của mô hình là một máy biệt lập nào đó, gọi tắt là máy, hoạt động theo cách mô hình tính toán đã chỉ ra. Máy này được định nghĩa bởi dữ liệu vào của chương trình : Mô hình + Chương trình = Máy Một khi một mô hình tính toán T được định nghĩa, được gọi là một T−máy, vấn đề đặt ra là làm sao để có thể biết : − lớp ngôn ngữ đoán nhận được (recognized), được gọi là T−nhận biết được, hoặc − lớp các hàm tính được (computable), được gọi là T−tính được, hoặc − lớp các ngôn ngữ liệt kê được (enumerable) được gọi là T −liệt kê được, bởi một máy nào đó của mô hình này ? Hai mô hình tính toán được đưa ra so sánh với nhau : một mô hình T1 được nói là mạnh hơn so với một mô hình T2 nếu : − mọi ngôn ngữ T2−nhận biết được cũng là T1−nhận biết được, hoặc − mọi hàm T2-tính được cũng là T1−tính được, hoặc − mọi ngôn ngữ T2-liệt kê được cũng là T1-liệt kê được. Hai mô hình được gọi là tương đương (equivalent) nếu mỗi mô hình mạnh hơn mô hình kia và ngược lại. Hai mô hình là không thể so sánh với nhau được nếu không tồn tại mô hình nào ít ra đủ mạnh hơn mô hình kia.
  9. Nhập môn lý thuyết tính toán 5 IV. Định nghĩa bài toán Trong Tin học lý thuyết, định nghĩa về bài toán (problem) có vai trò đặc biệt quan trọng, khác với khái niệm thông thường về bài toán được dùng trong lĩnh vực Toán học hoặc hiểu theo nghĩa thông dụng. Định nghĩa 1.2 : Một bài toán là : − Sự mô tả cách biểu diễn (hữu hạn) các phần tử của một tập hợp hữu hạn hay vô hạn đếm được. − Một phát biểu liên quan đến các phần tử của tập hợp này, có thể là đúng, hoặc có thể là sai tùy theo phần tử được chọn. Sau đây là một số ví dụ : Bài toán 1 : Dữ liệu: Một số nguyên viết trong hệ 10. Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 2 : Dữ liệu : Một số nguyên viết trong hệ 10. Câu hỏi : Có phải số nguyên này được viết dưới dạng tổng của 4 số bình phương ? Bài toán 3 : Dữ liệu : Một số nguyên viết dưới dạng tích của các số hạng trong hệ 10. Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 4 : Dữ liệu : Một đồ thị hữu hạn được biểu diễn bởi một danh sách gồm các đỉnh và các cung, trong đó mỗi đỉnh được biểu diễn bởi một số nguyên trong hệ 10. Câu hỏi : Có tồn tại một đường đi Hamilton (đi qua hết tất cả các đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần) trong đồ thị đã cho không ? Bài toán 5 : Dữ liệu : Một biểu thức chính quy (regular expression) được xây dựng trên một bảng chữ S (là một biểu thức nhận được từ các câu w∈S* bởi các phép hoặc, phép ghép tiếp, phép * và lấy bù). Câu hỏi : Có phải biểu thức đã cho biểu diễn (hay chỉ định) một ngôn ngữ trống (empty language) hay không ? Bài toán 6 : Dữ liệu : Một dãy hữu hạn các cặp câu (u1, v1), (u2, v2) , (uk, vk). Câu hỏi : Tồn tại hay không một dãy chỉ số i1 , i2 , in sao cho thoả mãn u u u = v v v ? i1 i2 in i1 i2 in
  10. 6 Lý thuyết tính toán Việc biểu diễn tường minh các dữ liệu là một thành phần của bài toán. Điều này đóng vai trò đặc biệt quan trọng khi người ta quan tâm đến độ phức tạp (complexity) của một bài toán. Mỗi dữ liệu sẽ tạo thành một trường hợp cá biệt của bài toán, được biểu diễn bởi một câu trên một bảng chữ hữu hạn đã cho. Với mỗi bài toán P được hợp thành từ một biểu diễn các phần tử của một tập hợp và từ một phát biểu liên quan đến các phần tử này, người ta thường kết hợp bài toán P với một ngôn ngữ, gọi là ngôn ngữ đặc trưng (characteristic language) của bài toán, được hợp thành từ tập hợp các câu biểu diễn một phần tử của tập hợp để từ đó, kết quả của bài toán là câu trả lời đúng. Người ta ký hiệu LP là ngôn ngữ đặc trưng của bài toán P. Cho trước một bài toán P, bài toán ngược lại CP là bài toán nhận được từ P bằng cách giữ nguyên cách biểu diễn các dữ liệu nhưng riêng câu hỏi thì đặt ngược lại. Ví dụ, bài toán ngược với bài toán 1 sẽ là : Bài toán 1’ : Dữ liệu : Cho một số nguyên viết trong hệ 10. Câu hỏi : Số nguyên này không phải là một số nguyên tố ? Từ đó, lời giải một bài toán đưa đến sự nhận biết của một ngôn ngữ : ngôn ngữ kết hợp với bài toán này. Người ta đưa ra định nghĩa hình thức sau đây : Định nghĩa 1.2 : Một máy giải (solve) một bài toán P nếu và chỉ nếu với mọi câu f biểu diễn một phần tử của tập hợp liên quan đến bài toán này, máy cho phép xác định, trong một khoảng thời gian hữu hạn, nếu câu này thuộc về L hay L . P CP Người ta phân lớp các bài toán tùy theo độ khó (difficulty) để đưa ra câu trả lời từ dữ liệu vào đã cho. Một bài toán là tầm thường (trivial) nếu L = ∅ hoặc nếu L = ∅. P CP Thật vậy, trong trường hợp này, không cần thiết biết dữ liệu đưa vào để đưa ra câu trả lời. Chú ý rằng, những gì là tầm thường, đó là việc đưa ra câu trả lời, nhưng có thể rất khó để chứng minh rằng bài toán là tầm thường theo nghĩa này. Ví dụ, bài toán 2 là tầm thường. Các bài toán 1 và 3 có cùng câu hỏi, nhưng bài toán 3 giải quyết rất dễ dàng : chỉ cần đọc qua dữ liệu vào, người ta có thể đưa ra kết quả, tuy nhiên trong bài toán 1 thì cần phải xử lý dữ liệu vào. Bài toán 4 phức tạp hơn : người ta chưa biết phương pháp nào hoạt động một cách đơn định (deterministic) tiêu tốn một lượng thời gian đa thức (polynomial times) để giải quyết vấn đề đặt ra. Đối với bài toán 5 thì tính phức tạp còn lớn hơn nữa : người ta biết rằng mọi phương pháp đều hoạt động theo thời gian tối thiểu là lũy thừa. Cuối cùng bài toán 6 không thể giải được theo nghĩa đã đưa ra. Bài toán này được gọi là bài toán tương ứng Post (Post’s correspondence problem).
  11. Nhập môn lý thuyết tính toán 7 Bài tập 1) Chứng minh rằng một tập hợp E là hữu hạn hay vô hạn đếm được nếu tồn tại một đơn ánh từ E vào N. Tương tự, nếu tồn tại một toàn ánh (surjection) từ Ν vào E. 2) Chứng minh rằng tích Đê-cac của hai tập hợp vô hạn đếm được cũng là một tập hợp vô hạn đếm được. 3) Chứng minh các tập hợp sau đây là vô hạn đếm được : N×N, Q, tập hợp Ν* gồm các dãy số nguyên, S*, S*×G*, S*×N, tập hợp (S*)* gồm các dãy các câu. Thể hiện các song ánh (bijection) giữa N và mỗi một tập hợp vừa nêu. 4) Cho S là một bảng chữ kích thước (bản số) n. Với mọi câu w∈S*, ký hiệu |w| là độ dài của w và m(w) là số thứ tự của w trong thứ tự phân cấp đã cho. Hãy tìm cách tính m(w) khi biết w. 5) Chứng minh rằng NN không phải là vô hạn đếm được. Tập hợp các chương trình Pascal có phải là vô hạn đếm được hay không ? Tập hợp các hàm f: N → N tính được nhờ một chương trình Psacal có là vô hạn đếm được hay không ? Từ đó suy ra rằng tồn tại các hàm từ N vào N không là vô hạn đếm được nhờ một chương trình Pascal. 6) Viết một chương trình để liệt kê : − các cặp số nguyên − các dãy hữu hạn các số nguyên − các câu trên một bảng chữ hữu hạn (chẳng hạn S={a, b, c}) − các cặp câu − các dãy hữu hạn các câu.
  12. CHƯƠNG 2 Mô hình các máy RAM « I like the dreams of the future better than the history of the past » Jefferson I. Các máy RAM Máy RAM là một mô hình tính toán rất gần với máy tính điện tử và ngôn ngữ assembler. Máy RAM có các thành phần đặc trưng chung như sau :  Một băng vào, hay dải vào (input tape) được chia thành nhiều ô (square hay pigeonhole) liên tiếp nhau, mỗi ô chứa một số nguyên hoặc một ký tự. Một đầu đọc (read head) đọc lần lượt nội dung từng ô trên băng vào, đọc từ trái qua phải.  Một băng ra (output tape) cũng chia ra thành nhiều ô liên tiếp nhau và một đầu ghi (write head) có thể ghi mỗi lần lên một ô và tiến từ trái qua phải. Người ta nói rằng đầu đọc (hoặc ghi) được đặt trên (tại) một ô và di chuyển qua phải mỗi lần một ô. Trước tiên, ta xem rằng mỗi ô chứa một số nguyên có thể lớn tuỳ ý. Băng vào và băng ra của máy RAM được gọi là các cơ quan vào/ra. Máy RAM còn có các thành phần bên trong như sau :  Các thanh ghi (registers) là các phần tử nhớ được đánh số thứ tự, số lượng các thanh ghi có thể lớn tuỳ ý. Mỗi thanh ghi có thể lưu giữ một số nguyên. Các thanh ghi lần lượt được đặt tên là R0, R1, R2, , Rn Chỉ số i, i = 0, 1, 2, , được gọi là địa chỉ (address) của mỗi thanh ghi (hay của bộ nhớ). Riêng R0 là một thanh ghi đặc biệt, được gọi là thanh tổng (ACC − accumulator) hay thanh tích luỹ.  Một tập hợp các đơn vị nhớ được đánh số chứa chương trình của máy RAM dưới dạng một dãy các lệnh sơ cấp (primary instructions) không bị thay đổi trong quá trình chạy (thực hiện). Mỗi lệnh được lưu trữ trong một đơn vị nhớ, được đánh số tương ứng với số thứ tự hay nhãn của lệnh (label).  Một đơn vị nhớ chứa số thứ tự của lệnh đang được thực hiện, được gọi là thanh đếm lệnh (OC − Ordinal Counter). Lúc đầu nội dung là của OC là 1. Trong kiểu máy này, người ta truy cập trực tiếp đến mỗi thanh ghi bởi địa chỉ của thanh ghi đó. Chính lý do này mà kiểu máy này được đặt tên là Random Access Memory (viết tắt RAM). PGS.TS. PHAN HUY KHÁNH biên soạn 9
  13. 10 Lý thuyết tính toán x1 x2 . . . xn Băng vào 1 R0 Thanh tổng Chương trình 2 R1 . . . . . . . . . . . . Các thanh ghi j Ri . . . . . . . . . . . . p R i n Thanh đếm lệnh y1 y2 y3 . . . Băng ra Hình 2.1 Sơ đồ một máy RAM Mỗi chương trình của máy RAM gồm một dãy lệnh sơ cấp, mỗi lệnh được tạo thành từ 2 thành phần : mã lệnh (operation code) và toán hạng (operand) : Mã lệnh Toán hạng Các lệnh được phân thành nhóm theo chức năng của phần mã lệnh như sau : Nhóm lệnh gán : LOAD Operand STORE Operand Nhóm lệnh số học : INCR Operand DECR Operand AD Operand SUB Operand MULT Operand DIV Operand Nhóm lệnh nhảy (hay lệnh ngắt, cũng còn gọi là lệnh chuyển điều khiển) : JUMP Label JGTZ Label JZERO Label HALT Nhóm lệnh vào − ra : READ Operand WRITE Operand
  14. Mô hình các máy RAM 11 Theo nguyên tắc địa chỉ, phần toán hạng là địa chỉ (address) của toán hạng tham gia phép toán chỉ định bởi phần mã lệnh. Toán hạng có thể là một trong ba kiểu sau : Kiểu địa chỉ Ý nghĩa Số nguyên n Chỉ nội dung của thanh ghi thứ n (Rn). A: n (A = Absolute) toán hạng chính là số nguyên n đó. I: n (I = Indirection) toán hạng là nội dung của thanh ghi có số thứ tự là nội dung của thanh ghi Rn. Đây là kiểu lệnh gián tiếp. Nếu lệnh là một lệnh nhảy thì địa chỉ chính là số thứ tự của lệnh trong chương trình. Các lệnh trên đây của máy RAM điển hình cho các lệnh của ngôn ngữ assembler. Tuy nhiên ở đây vắng mặt các lệnh xử lý ký tự và các lệnh logic nhằm đơn giản cách trình bày. Thứ tự thực hiện các lệnh của chương trình là tuần tự (on sequence), bắt đầu từ lệnh đầu tiên (có nhãn 1). Ngoại lệ duy nhất là khi gặp lệnh nhảy (hay chuyển điều khiển) thì lệnh tiếp theo được thực hiện có nhãn chỉ định bởi lệnh nhảy này. Nguyên tắc thực hiện như sau : OC luôn luôn chứa nhãn của lệnh sẽ được thực hiện, lúc đầu nội dung OC là 1. Sau khi thực hiện lệnh, nội dung OC được tự động tăng thêm 1 (increment) nếu như lệnh vừa thực hiện không là lệnh nhảy. Nếu như lệnh vừa thực hiện là lệnh nhảy thì nội dung của OC lấy nhãn là phần địa chỉ của lệnh nhảy này. Sau đây sử dụng một số quy ước để giải thích cách thực hiện lệnh. ← dấu gán ; quy ước số nguyên i nằm bên trái dấu gán chỉ thanh ghi thứ i là Ri, số nguyên i nằm bên phải dấu gán chỉ giá trị chính là số nguyên i đó. Chỉ nội dung của thanh ghi Ri. > Chỉ nội dung của thanh ghi có số thứ tự được chứa trong thanh ghi Ri đối với kiểu lệnh gián tiếp. ACC Chỉ thanh ghi R0. CO Chỉ thanh đếm lệnh. Nội dung của CO. Sau đây là bảng các lệnh RAM và ý nghĩa sử dụng của chúng.
  15. 12 Lý thuyết tính toán Lệnh Ý nghĩa LOAD n ACC ← LOAD A: n ACC ← giá trị n LOAD I: n ACC ← > STORE n n ← STORE I: n ← INCR n n ← + 1 DECR n n ← - 1 ADD n ACC ← + SUB n ACC ← − MULT n ACC ← × DIV n ACC ← / JUMP n CO ← n JGTZ n CO ← n nếu ≥ 0 JZERO n CO ← n nếu = 0 C ả hai trường hợp trên, nếu không thỏa mãn, CO ← + 1 HALT Dừng máy READ n n ← số nguyên trong ô dưới đầu đọc của băng, đầ u đọc dịch một ô qua phải WRITE n Nội dung được ghi vào ô dưới đầu ghi, đầ u ghi dịch qua phải một ô. Ví dụ 2.1 : Chương trình RAM sau đây đánh giá trị n! READ 0 đọc một giá nguyên n vào ACC JZERO 10 nếu n = 0, nhảy đến nhãn 10, nếu không, thực hiện lệnh tiếp theo STORE 1 R1 ← 4: STORE 2 R2 ← DECR 1 R1 ← − 1 LOAD 1 ACC ← JZERO 12 nếu = 0 nhảy đến 12 * MULT 2 ACC ← JUMP 4 CO ← 4 10: LOAD A: 1 ACC ← 1 STORE 2 R2 ← 12 : WRITE 2 ghi ra HALT Dừng máy
  16. Mô hình các máy RAM 13 Ví dụ 2.2 : Chương trình RAM tính nn READ 1 R1 ← số nguyên trên ô của băng vào LOAD 1 ACC ← JGTZ 6 nếu ≥ 0, nhảy đều 6 WRITE A:0 in ra 0 JUMP 22 về lệnh dừng 6 : LOAD 1 ACC ← STORE 2 R2 ← LOAD 1 ACC ← DECR 0 ACC ← − 1 STORE 3 R3 ← 11 : LOAD 3 ACC ← JGTZ 14 nếu ≥ 0, nhảy đến 14 JUMP 21 nhảy đến 21 nếu * MULT 1 ACC ← STORE 2 R2 ← LOAD 3 ACC ← − 1 STORE 3 R3 ← JUMP 11 nhảy đến 11 21: WRITE 2 in ra nội dung 22: HALT dừng Ta có thể viết đoạn trình Pascal minh họa trình RAM như sau : begin read (R1) if R1 0 do begin R2:= R2*R1 ; R3:= R3–1 end ; write (R2) end end ; Ta thấy một trình RAM xác định một ánh xạ từ tập các băng vào lên tập các băng ra. Đây là ánh xạ bộ phận (partial map) vì một số ánh xạ có thể không xác định trên một số băng vào, nghĩa là chương trình ứng với băng vào đó không dừng. Ta có thể giải thích ánh xạ này ở dưới hai dạng : dạng hàm và dạng ngôn ngữ.
  17. 14 Lý thuyết tính toán Dạng hàm f : S* → S* Giả sử chương trình P luôn đọc được từ băng vào n số nguyên x1, x2, , xn và ghi lên băng ra không quá một số nguyên y ở ô đầu tiên, khi đó ta nói P tính hàm f (x1, x2, , xn) = y. Dạng ngôn ngữ L ⊆ S* Giả sử trên băng vào có câu w = a1a2 an với ai ở ô thứ i, i = 1 n, còn ô thứ n+1 chứa # là ký tự kết thúc dãy. Ta nói w được thừa nhận bởi chương trình RAM nếu nó đọc được hết w, kể cả ký tự #, sau đó viết lên ô đầu tiên của băng ra một ký tự kết quả và dừng. Ta nói máy RAM thừa nhận một ngôn ngữ L đã cho nếu thừa nhận mọi câu w∈L. Nếu w∉L thì máy RAM có thể không đọc hết w, ghi ký tự kết thúc lên băng ra, hoặc bị hóc (crash), hoặc không bao giờ dừng. Sự khác nhau cơ bản giữa mô hình máy RAM vừa mô tả ở trên và các máy tinh điện tử hiện nay là ở chỗ : 1) Ta đã giả thiết có thể sử dụng một số lớn tùy ý các thanh ghi, tuy nhiên trong thực tế điều này rất khó thực hiện. Tương tự, ta đã giả thiết có thể đặt một số nguyên lớn tùy ý vào một thanh ghi nào đó, hoặc vào một ô nào đó trên băng vào, hoặc trên băng ra. Nhưng điều này cũng rất khó thực hiện trong thực tiễn. 2) Ta đã giả thiết rằng chương trình có sẵn trong bộ nhớ RAM chỉ có thể đọc (không thể bị thay đổi khi chạy chương trình), khác với các bộ nhớ kiểu thanh ghi. Điều này cũng không xảy ra với các máy tính thông dụng. Sự khác nhau chi tiết như sau : 3) Các lệnh sơ cấp được chọn hạn chế hơn so với các ngôn ngữ assembler Tuy nhiên, người ta có thể nói rằng vẫn không làm mất tính tổng quát nếu giảm đáng kể tập hợp các lệnh sơ cấp. 4) Các dữ liệu đưa vào không phải dưới dạng các số nguyên được đọc toàn bộ một lần trong một ô, mà dưới dạng một dãy ký tự (một dãy các chữ số), tương tự như vậy đối với các kết quả ra. Ta hãy xem làm cách nào để giải quyết vấn đề do 4) đặt ra : Trong các máy tính, các số nguyên thường được biểu diễn theo hai cách phân biệt là biểu diễn thập phân, hoặc biểu diễn nhị phân. Cách biểu diễn nhị phân có lợi thế hơn vì chỉ sử dụng hai chữ số. Máy tính sẽ chuyển đổi chuỗi ký tự biểu diễn số nguyên thành biểu diễn nhị phân để đặt trong các thanh ghi, sau đó chuyển đổi kết quả đang ở dạng biểu diễn nhị phân của số nguyên thành chuỗi ký tự trên băng ra. Điểm 1) trên đây có nghĩa : trong mọi trường hợp, kích thước của bài toán cần giải là đủ bé để bộ nhớ máy tính có thể chứa hết ở dạng nhị phân trong các đơn vị nhớ, hay từ nhớ (memory word). Chú ý rằng nếu chỉ làm việc với cách biểu diễn số nguyên bởi chuỗi các chữ số thì không còn giả thiết số lớn tùy ý nữa.
  18. Mô hình các máy RAM 15 Cuối cùng, sự khác nhau ở điếm (2) đưa đến việc xây dựng một mô hình tương tự mô hình RAM, nhưng chương trình được đặt trong các thanh ghi (và do vậy có thể bị thay đổi), được gọi là mô hình các máy RASP (Random Access with Stored Program). Sự khác nhau cơ bản với các máy RAM là vùng nhớ lưu giữ chương trình của RASP hoàn toàn không khác gì so với các vùng nhớ khác. Máy RASP Để thuận tiện cách trình bày, ta quy ước rằng mỗi lệnh RASP chiếm chỗ hai thanh ghi liên tiếp nhau : thanh ghi đầu chứa trường toán hạng, thanh ghi thứ hai chứa trường địa chỉ của lệnh. x1 x2 . . . xn Băng vào R0 Thanh tổng R1 R2 Chương trình Rp i Thanh đếm lệnh . . . Các thanh ghi khác y1 y2 y3 . . . Băng ra Hình 2.2 Sơ đồ một máy RASP Trong máy RASP, thanh tổng luôn luôn là R0, thanh ghi R1 dùng để lưu giữ trung gian nội dung của thanh tổng. Các thanh ghi từ 2 p (với p là một số nguyên lẻ) chứa chương trình của máy RASP, và các thanh ghi tiếp theo, từ p + 1 trở đi, là các thanh ghi còn trống. Sự khác nhau cớ bản với mô hình máy RAM là có thể thay đổi một thanh ghi chứa chương trình, và do vậy, có thể thay đổi chương trình.
  19. 16 Lý thuyết tính toán II. Mô phỏng một máy bởi một máy khác Từ đây trở đi, người ta thường phải mô phỏng một máy bởi một máy khác : máy mô phỏng sẽ bắt chước hay nhại lại (mime) mỗi một lệnh của máy được mô phỏng, bằng cách thực hiện nhiều lệnh (nói chung) để đi đến cùng một kết quả. Khi có một máy RAM M có chương trình P chạy và sử dụng đến thanh ghi 0 và các thanh ghi từ 1 đến p (giá trị của p thay đổi tùy theo dữ liệu), người ta nói rằng một máy RAM M’ có chương trình P’ mô phỏng chức năng của máy RAM M nếu :  Tồn tại một ánh xạ I từ N vào N mà biến 0 thành 0.  Mỗi lệnh của P được thay thế bởi một lệnh của P’ sao cho, mỗi lần thực hiện chương trình P (nghĩa là với mọi dữ liệu), nội dung mỗi thanh ghi I (r) của M’ sau khi thực hiện dãy các lệnh của P’ là giống như nội dung của thanh ghi R của M sau khi thực hiện các lệnh tương ứng của P. Ví dụ 2.3 : Dịch chuyển các địa chỉ thanh ghi. Xuất phát từ một máy RAM có chương trình P khi chạy sử dụng thanh ghi 0 và các thanh ghi từ 1 đến p, ta có thể xây dựng một máy RAM khác có chương trình Pk mô phỏng trình P với ánh xạ I xác định bởi : I (0) = 0 I (r) = k + r với r > 0. Việc mô phỏng máy RAM sẽ trở nên tầm thường nếu không xử lý các lệnh gián tiếp. Đối với kiểu lệnh này, vấn đề là thay đổi địa chỉ các thanh ghi sử dụng đến, bằng cách thêm giá trị k (nhờ lệnh ADD A:k) vào nội dung của thanh ghi liên quan (đặt sau I) để thực hiện kiểu gián tiếp. Các máy RASP cũng có thể được mô phỏng và có thể xử lý kiểu lệnh gián tiếp. Dịch chuyển các địa chỉ thanh ghi của RASP Những gì mà một máy RAM làm được thì một máy RASP cũng có thể được làm được. Thật vậy, nếu chương trình của RASP được lưu giữ trong các thanh ghi từ 2 đến p, chỉ cần thực hiện một sự biến đổi của p lên tất cả các số của thanh ghi sử dụng bởi máy RAM tương ứng. Tuy nhiên trong mô hình của RASP, kiểu lệnh gián tiếp được xử lý như sau : Giả sử một chương trình P của máy RASP được lưu giữ từ thanh ghi số 2 đến p và khi chạy sử dụng đến các thanh ghi từ p + 1 đến q. Ta sẽ xây dựng một chương trình mới mô phỏng P được lưu giữ trong các thanh ghi từ 2 đến p’. Khi chạy, chương trình sử dụng đến các thanh ghi từ p’ + 1 đến q + p’ − p, bằng cách thay thế mỗi lệnh kiểu gián tiếp bởi 6 lệnh không là kiểu gián tiếp, sao cho kết quả của 6 lệnh này là tương tự trên mỗi thanh ghi số p’ + i với kết quả của lệnh được mô phỏng trên mỗi thanh ghi số p + i.
  20. Mô hình các máy RAM 17 Một cách cụ thể hơn, p’ − p có giá trị 2 × (6 − 1) × s = 10s với s là tổng số lệnh kiểu gián tiếp của chương trình. Giả sử ta cần mô phỏng một trong các lệnh MULT I: n của chương trình RASP cần mô phỏng, được lưu giữ trên các thanh ghi 30 và 31 của máy xuất phát. Để mô phỏng, ta cần tạo ra nhóm 6 lệnh chiếm 12 liên tiếp, giả sử từ thanh ghi số 50 đến 61, với giả thiết chương trình có trên hai lệnh kiểu gián tiếp. Lệnh đầu tiên của nhóm 6 lệnh này là lưu giữ nội dung của thanh tổng vào thanh ghi R1 : 50 STORE 51 1 R1 ← Lệnh thứ hai nạp vào thanh tổng nội dung của thanh ghi n + p’ − p (tương ứng với thanh ghi n trong chương trình xuất phát) : 52 LOAD 53 n + p’- p ACC ← + (p’ − p) Lệnh thứ ba tăng nội dung của thanh tổng lên p’ − p để lúc này thanh tổng chứa địa chỉ của thanh ghi chứa giá trị cần nhân : 54 ADD A: 55 p’- p ACC ← + (p’ − p) Lệnh thứ tư gán trực tiếp lệnh thứ sáu bằng cách thay đổi trường địa chỉ của lệnh này (việc thực hiện chương trình làm thay đổi bản thân chương trình đó) : 56 STORE 57 61 R61 ← Lệnh thứ năm khôi phục nội dung lúc đầu của thanh tổng : 58 LOAD 59 1 ACC ← Cuối cùng, thực hiện phép nhân : 60 MULT 61 x ACC ← * Ở đây, lúc bắt đầu thực hiện chương trình, x là một giá trị nào đó, và mỗi lần thực hiện, nếu thanh ghi n của máy xuất phát chứa số nguyên a, thì x sẽ có giá trị là a + p’ - p tại thời điểm thực hiện lệnh đặt trong các thanh ghi 60 và 61. Như vậy, khi mô phỏng trình P thành P’ đặt trong các thanh ghi RASP, P’ đã bị thay đổi khi thực hiện nó.
  21. 18 Lý thuyết tính toán Ví dụ 2.4 : Dịch chuyển một trình RASP có một lệnh dạng gián tiếp : ⎪⎧1 + a nãúu a ≤ b Tính in ⎨ ⎩⎪1 + b nãúu a > b Chương trình RASP xuất phát P : sau khi dịch chuyển thành P’ : 2 READ READ R27 ← a 3 27 37 4 READ READ R27 ← b 5 28 38 6 LOAD A: LOAD A: ACC ← 7 27 37 8 STORE STORE R ← 9 26 26 36 Phần này là 10 LOAD LOAD dịch chuyển của P ACC ← 11 28 38 với ánh xạ : 12 SUB SUB I(r) = r+p’-p = r+10 ACC ← - 13 27 37 14 JGTZ JGTZ OC ← 18, if > 0 15 18 18 16 INCR INCR R26 ← + 1 17 26 36 18 LOAD A: LOAD A: ACC ← 1 19 1 1 20 ADD I: STORE ACC ← + > R1 ← 21 26 1 22 WRITE LOAD In ra ACC ← 23 0 36 24 HALT ADD A: ACC ← + Dừng p 25 0 10 10 P+1 26 27 / 28 Nội dung 27, hoặc 28 STORE R31 ← : số 27 a Chứa giá trị a 31 x q 28 b Chứa giá trị b LOAD ACC ← 29 1 30 ADD ACC← + Nội dung thay đổi : số x 31 0 → x 32 WRITE 33 0 34 HALT P’ 35 0 P’+1 36 37 / 38 Nội dung 37, hoặc 38 37 a Chứa giá trị a q +P’-p 38 b Chứa giá trị b Hình 2.3. Trình P’ bị thay đổi khi thực hiện
  22. Mô hình các máy RAM 19 III. Một mô hình thô sơ kiểu RAM Trong phần này, ta sẽ chỉ ra rằng có thể thu gọn về một tập hợp lệnh sơ cấp rất nhỏ. Đặc biệt, ta sẽ chỉ ra rằng có thể xử lý ký tự và xử lý các số nguyên. Trước hết, ta quay lại cách biểu diễn các số nguyên. Trong máy tính, có hai cách biểu diễn : biểu diễn nhị phân cho phép lưu trữ một số nguyên trong một thanh ghi làm tiết kiệm chỗ và tính toán nhanh chóng nhưng có nhược điểm là độ lớn của số nguyên phụ thuộc vào kích thước thực tế của thanh ghi (hữu hạn). Cách biểu diễn thứ hai là sử dụng một dãy chữ số trên bảng chữ {0 9}. Thực tế, ngay cả khi người ta có thể biểu diễn trong một thanh ghi nhiều ký tự (thường không quá 4), thì để biểu diễn một số nguyên cũng đòi hỏi có nhiều thanh ghi. Mặc dù dải số nguyên có thể biểu diễn được là khá lớn, nhưng do số lượng các thanh ghi trong máy tính hiện nay bị hạn chế nên cách biểu diễn này cũng chưa phải tối ưu. III.1. Mô phỏng các phép toán trên chuỗi ký tự bởi các phép toán trên các số nguyên Mỗi ký tự được mã hóa bởi một dãy các chữ số nhị phân {0, 1} (chẳng hạn 8 chữ số cho một ký tự). Một chuỗi bit như vậy có thể dùng để biểu diễn các số nguyên nhờ thực hiện các phép toán trên các số nguyên. Chẳng hạn, ghép 198 và 7, dẫn đến phép nhân số nguyên biểu diễn chuỗi 198 với 28 rồi cộng thêm số nguyên biểu diễn chuỗi 7 vào tích số nhận được : 198 7 ~ 198 × 28 + 7 Hình 2.4 Ghép hai số nguyên Ngược lại, các phép toán số học có thể được thực hiện trên biểu diễn các số nguyên bởi các chuỗi ký tự, đó là các phép tính sơ cấp. Chú ý rằng khi người ta tiến hành các phép toán trên các số nguyên theo cách biểu diễn nhị phân, người ta đã xử lý trên các câu của bảng chữ {0, 1}, và phép toán được thực thi trên các ký tự.
  23. 20 Lý thuyết tính toán III.2. Thu gọn tập hợp các lệnh ngắt Ta có thể chuyển đổi các lệnh ngắt JUMP n về hai kiểu lệnh là nhảy nếu gặp 0 (zero) JZERO và lệnh dừng máy HALP. Lệnh JUMP n sẽ sử dụng thanh ghi R1 làm trung gian để lưu giữ nội dung của thanh tổng, bằng cách thêm vào trước mỗi lệnh đã gắn nhãn các lệnh sau : STORE 1 R1 ← LOAD 1 ← R1 sau đó thay thế lệnh nhảy bởi : STORE 1 R1 ← LOAD A: 0 ← 0 JZERO n’ goto n’, if = 0 Trong đó n’ là nhãn của lệnh STORE 1 đặt trước ngay lệnh có nhãn n trong máy xuất phát. Bài tập : Một cách tương tự, xây dựng lại lệnh JGTZ (nhảy nếu kết quả dương). III.3. Thu gọn tập hợp các lệnh số học Có thể chuyển đổi các lệnh số học (cộng, trừ, nhân, chia) về hai kiểu lệnh là INCR (tăng 1) và DECR (giảm 1). Chẳng hạn, lệnh nhân MULT n sẽ được chuyển đổi bằng cách thêm lần nội dung của thanh tổng. Sử dụng các thanh ghi từ 1 đến 3 làm trung gian, ta có thể thay lệnh nhân bởi các lệnh sau : STORE 1 LOAD n STORE 2 LOAD A: 0 STORE 3 return: LOAD 2 JZERO lab DECR 2 LOAD 1 ADD 1 STORE 3 JUMP return lab: LOAD 3 Một cách tương tự, lệnh ADD n tăng thêm 1 (INCR) đúng lần nội dung của thanh tổng nhờ các lệnh STORE, LOAD, JGTZ, DECR
  24. Mô hình các máy RAM 21 Từ đó, người ta có thể thu hẹp về một mô hình tính toán, gọi là mô hình RAM thô sơ, chỉ có tập hợp các lệnh tối thiểu sau : Lệnh Ý nghĩa I Tăng thêm 1 nội dung của thanh ghi n D Giảm bớt 1 nội dung của thanh ghi n Z Đặt nội dung của thanh ghi n về 0 S Hoán đổi nội dung các thanh ghi n và m J (i, j) Nếu nội dung của thanh ghi n là 0, nhảy đến lệnh có nhãn i, nếu không nhảy đến lệnh có nhãn j HALT Dừng máy Với tập hợp các lệnh trên, chương trình cũng là một dãy lệnh có mang nhãn. Nếu chỉ định nội dung của thanh ghi n, thì > chỉ định nội dung của thanh ghi có số thứ tự là . Ví dụ 2.5 : 1: J (5, 2) 2: I 3: D 4: J (1, 1) 5: HALT Nếu các thanh ghi 1 và 2 chứa lần lượt các số nguyên n và p, thì máy dừng lại khi hai thanh ghi này chứa lần lượt n + p và 0.
  25. 22 Lý thuyết tính toán IV. Máy RAM vạn năng Trong phần này, chúng ta sẽ chỉ ra cách xây dựng một máy kiểu RAM có thể mô phỏng bất kỳ máy RASP nào không sử dụng kiểu gián tiếp. Nguyên lý mô phỏng như sau : lúc đầu, người ta đọc chương trình của máy RASP, chương trình này được lưu giữ trong các thanh ghi từ 4 đến p của máy RAM. Thanh ghi R1 dùng làm địa chỉ gián tiếp ; thanh ghi R2 dùng để mô phỏng thanh đếm lệnh của RASP. Thanh ghi R3 dùng để mô phỏng thanh tổng của RASP. Sau đó, thực hiện một vòng lặp trên các phép toán được mô tả dưới đây, mỗi lần lặp là một lần mô phỏng một lệnh của RASP. Giả thiết rằng thanh ghi R2 chứa địa chỉ của thanh ghi đầu tiên trong hai thanh ghi chứa lệnh cần mô phỏng (bắt đầu từ 4). Vòng lặp như sau : Loop: − Nội dung của thanh ghi của R2 được gán cho thanh tổng : LOAD I: 2 − Phân tích mã phép toán của lệnh này và tùy theo mã đã phân tích mà nhảy đến dãy lệnh tương ứng với nó. Ví dụ, nếu x là mã của phép chia DIV và y là nhãn của dãy phép toán mô phỏng DIV, nếu z là mã của phép nhảy dương JGTZ và t là nhãn của dãy phép toán mô phỏng JGTZ : . . . SUB A: x JZERO y ADD A: x SUB A: z JZERO t ADD A: z . . . Sau đó, từ nhãn y, thực hiện mô phỏng phép toán chia DIV : − Tăng nội dung R2 lên 1 để R2 chứa địa chỉ của thanh ghi chứa toán hạng : INCR 2 − Gán địa chỉ này cho thanh ghi R1 : LOAD I: 2 STORE 1 − Mô phỏng phép toán giữa nội dung thanh tổng của RASP và toán hạng này bởi : LOAD 3 DIV I: 1 STORE 3
  26. Mô hình các máy RAM 23 − Tăng nội dung thanh ghi R2 lên 1 để R2 chứa địa chỉ của thanh ghi đầu tiên trong hai thanh ghi chứa lệnh tiếp theo cần mô phỏng : INCR 2 − Quay lại từ đầu vòng lặp bởi lệnh nhảy : JUMP loop Tương tự, từ nhãn t, thực hiện mô phỏng phép toán nhảy dương JGTZ : − Kiểm tra nội dung thanh tổng của RASP, nếu dương thì nhảy : LOAD 3 JGTZ lab − Nếu kết quả âm, tăng nội dung của R2 lên 2 để R2 chứa địa chỉ của thanh ghi đầu tiên trong hai thanh ghi chứa lệnh tiếp theo cần mô phỏng và quay lại đầu vòng lặp : INCR 2 INCR 2 JUMP loop − Nếu kết quả dương, từ nhãn lab, tăng nội dung thanh ghi R2 lên 1 để R2 chứa địa chỉ của thanh ghi chứa toán hạng : lab: INCR 2 − Gán địa chỉ này cho thanh ghi R1 : LOAD I: 2 STORE 1 − Lấy địa chỉ của lệnh nhảy điều kiện : LOAD I: 1 − Thay đổi sao cho thanh ghi R2 mô phỏng thanh đếm lệnh OC của RASP, và quay lại đầu vòng lặp : STORE 2 JUMP loop Như vậy mỗi phép toán sơ cấp của RASP được mô phỏng bởi một dãy các lệnh lặp của máy RAM. Máy RAM vừa mô phỏng có dữ liệu là chương trình P của một máy RASP bất kỳ, theo sau là một dữ liệu D cho chương trình P. Máy RAM có kết quả là kết quả của P trên dữ liệu D. Máy RAM mô phỏng hoạt động của mọi máy RASP. Một cách tương tự, người ta có thể xây dựng một máy RAM mô phỏng hoạt động của tất cả máy RAM. Một máy RAM dựa trên mô hình tính toán mô phỏng hoạt động của tất cả các phần tử của mô hình như vừa xét được gọi là một máy RAM vạn năng (universal).
  27. 24 Lý thuyết tính toán Bài tập 1. Viết chương trình của một máy RAM tính nn với số nguyên n cho trước. 2. Viết chương trình của một máy RASP tính giá trị bình quân nguyên của dãy n số nguyên cho trước, với n lẻ. 3. Viết chương trình của một máy RASP không sử dụng kiểu gián tiếp để tính giống bài 2. 4. Viết chương trình của một máy RAM thô sơ tính : a. Phần dư của phép chia m cho n, với m và n cho trước. b. Số nguyên tố thứ n, với n cho trước 5. Chứng tỏ rằng có thể rút lệnh hoán đổi : S trong máy RAM thô sơ. 6. Hãy tìm cách mô phỏng các phép toán logic sơ cấp trong một máy RAM, trong một máy RASP và trong một máy RAM thô sơ. 7. Hãy cho biết tập hợp các phép toán sơ cấp để xử lý ký tự. Hãy tìm cách mô phỏng chúng trong một máy RAM, trong một máy RASP và trong một máy RAM thô sơ. 8. Viết chương trình của một máy RAM vạn năng.
  28. CHƯƠNG 3 Mô hình các máy Turing « If the human brain was so simple that we could understand it, then we would be so simple that we could not » (L. Watson) Mô hình các máy Turing (Turing machines model) là một trong trong những mô hình được sử dụng rất rộng rãi trong lý thuyết tính toán. Trong chương này, chúng ta sẽ tập trung mô tả hình thức các máy Turing, chức năng đoán nhận ngôn ngữ và tính hàm của chúng. Từ đó chúng ta sẽ nghiên cứu các tính chất của lớp các hàm T−tính được. Phần cuối chương trình bày các biến thể khác của mô hình các máy Turing và các máy Turing không đơn định. I. Mô tả và hoạt động của máy Turing I.1. Mô tả máy Turing Một máy Turing gồm :  Một băng vô hạn cả hai phía trái và phải được chia thành các ô liên tiếp nhau. Mỗi ô chứa một thông tin hữu hạn (finite information) nào đó được biểu diễn bởi một chữ cái (letter) hay ký tự. Tập hợp các chữ cái (hay ký tự) này tạo ra bảng chữ của máy Turing, đưọc định nghĩa đồng thời với máy Turing.  Một đầu đọc−ghi để đọc hay ghi (làm thay đổi) nội dung từng ô của băng, và mỗi lần chỉ di chuyển, qua phải hoặc qua trái, một vị trí tương ứng với một ô. Như vậy, tại mỗi thời điểm, chỉ duy nhất một ô được đọc, hoặc được ghi mà thôi.  Một bộ nhớ phụ hữu hạn có thể tiếp cận tại mọi thời điểm, có thể biết được nội dung và thay đổi được. Tất cả các nội dung có thể của bộ nhớ phụ này được liệt kê hết lúc định nghĩa máy Turing, được chỉ định bởi một số thứ tự, gọi là trạng thái của máy Turing.  Một chương trình là một tập hợp hữu hạn các quy tắc chỉ ra sự thay đổi các thông tin trên băng và nội dung của bộ nhớ phụ. Một cách hình thức, máy Turing được định nghĩa từ các thành phần sau đây : PGS. TS. PHAN HUY KHÁNH biên soạn 25
  29. 26 Lý thuyết tính toán  Một bảng chữ S có tối thiểu hai ký tự, một trong chúng là một ký tự trắng, ký hiệu # (hoặc B). Trên băng của máy Turing, mỗi ô chứa một ký tự của bảng chữ này.  Một tập hợp hữu hạn các trạng thái Q. Mỗi trạng thái là một tên chỉ định thông tin của bộ nhớ phụ hữu hạn.  Một chương trình P là một tập hợp con của Q×S´S´M´Q, trong đó, M = {L, R} là tập hợp các chuyển động có thể của đầu đọc−ghi, tương ứng với việc chuyển đầu đọc qua trái (Left) một ô, hoặc qua phải (Right) một ô. Mỗi phần tử (q, x, y, m, p) của P là một quy tắc, được viết như sau : q, x → y, m, p với x và y ∈ S, q và p ∈ Q, m ∈ M, trong đó :  Cặp (q, x) là vế trái của quy tắc, cho biết điều kiện để áp dụng quy tắc.  Bộ ba (y, m, p) là vế phải của quy tắc, cho biết các thay đổi khác nhau khi áp dụng quy tắc, theo một thể thức sẽ trình bày dưới đây. Người ta thường biểu diễn một quy tắc của P dưới dạng sơ đồ như sau : x | y, m q p Hình 3.1. Biểu diễn dạng sơ đồ một quy tắc của máy Turing Như vậy, một máy Turing là một bộ ba T = được đặc tả một cách hữu hạn. Trước khi giải thích họat động của một máy Turing, ta có nhận xét rằng tồn tại nhiều cách định nghĩa máy Turing. Mặc dù những định nghĩa này không làm ảnh hưởng đến hiệu lực của mô hình, nhưng đều có các nhược điểm. Mô hình được chọn định nghĩa ở đây cũng có những điều bất tiện. Đó là cách mô tả các ô của băng vô hạn. Ở đây ta đã quy ước rằng các máy Turing luôn luôn có vô hạn các ô chứa ký tự trắng # về phía bên trái và về phía bên phải, chỉ có một phần của băng gồm một số hữu hạn ô (nhưng không bị giới hạn) là hữu ích, gọi là phần hữu ích (usable part). Dãy ký tự chứa trong phần hữu ích này là một câu f trên bảng chữ S, nằm giữa hai ký tự #. Người ta viết f#f. Chú ý rằng một số tài liệu xem ký tự trắng không thuộc bảng chữ S, # ∉ S. I.2. Hoạt động của máy Turing Người ta gọi c là cấu hình (configuration) của một máy Turing T = là một bộ ba : c = (f, q, xg) ∈ S* ´ Q ´ SS* sao cho câu fxg tạo thành phần hữu ích của băng vô hạn. Trạng thái q chỉ định nội dung của bộ nhớ phụ. Đầu đọc−ghi được đặt trên ô chứa ký tự x.
  30. Mô hình các máy RAM 27 Một máy Turing và một cấu hình của máy cho phép mô tả đầy đủ hệ thống. Cho máy Turing T = , và c = (f, q, xg) là một cấu hình nào đó, ta nói rằng tồn tại một chuyển tiếp (transition) hay dịch chuyển từ cấu hình c thành cấu hình c’ = (f’, q’, g’), ký hiệu : c Ã− c’ nếu và chỉ nếu : − (q, x) là vế trái của quy tắc (q, x → y, m, q’) của P và : − nếu m = R thì f’ = fy và g’ = g − nếu m = L thì f = f’z và g’ = zyg, với z là ký tự trên băng. Trong cả hai trường hợp, chuyển tiếp làm thay đổi nội dung của ô nằm dưới đầu đọc−ghi, và dịch đầu đọc−ghi qua trái hoặc qua phải tuỳ theo giá trị chỉ hướng của m (L hoặc R). Cuối cùng chuyển tiếp làm thay đổi nội dung của bộ nhớ phụ, chuyển từ trạng thái q thành trạng thái q’. ←−− Phần hữu ích −−→ . . . # # # f x g # # # . . . q Hình 3.2. Máy Turing trong cấu hình c = (f, q, xg) Cho máy Turing T = , và c là một cấu hình, ta nói rằng tồn tại một phép tính hợp lệ (valid computation) có độ dài n ≥ 0 dẫn từ cấu hình c đến cấu hình c’, ký hiệu c Ã−n c’, nếu và chỉ nếu : − tồn tại một dãy các cấu hình c0, c1, , cn sao cho c = c0, c’ = cn − với mỗi i ∈ {0 n-1}, tồn tại một chuyển tiếp giữa ci và ci+1 : ci Ã− ci+1 Ta ký hiệu cÃ−* c’ là phép tính hợp lệ dẫn từ cấu hình c đến cấu hình c’ có độ dài không biết chắc chắn (quan hệ Ã−* là đóng đối với các phép phản xạ và bắc cầu của quan hệ Ã−). Chú ý rằng người ta không xét các phép tính không hợp lệ. Ví dụ 3.1 : Cho máy Turing T = với S = {1, #}, Q = {q1, q2, q3, q4} và P = { q1, 1 → 1, R, q2, q2, 1 → 1, R, q1, q1, # → #, L, q3,
  31. 28 Lý thuyết tính toán q3, 1 → 1, L, q3, q3, 1 → 1, R, q3, q3, 1 → #, R, q1 } Xét cấu hình c = (e, q1, 111), ta có thể có các chuyển tiếp sau : c = (e, q1, 111) Ã− (11, q1, 1) Ã- (111, q2, #) Từ cấu hình cuối cùng, không tồn tại quy tắc nào trong P có vế trái là (q2, #) nên không thể tiếp tục được nữa. Bây giờ xét cấu hình c’ = (e, q1, 1111), ta có các chuyển tiếp sau : c’ = (e, q1, 1111) Ã− (e, q1, 111) Ã− (11, q1, 11) Ã− (111, q2, 1) Ã− (1111, q1, #) Ã− (111, q3, 1) Ã− (11, q3, 1) Ã− (11, q3, 11) Ã− (1, q3, 111) Ã− (e, q3, 1111) = (#, q3, 1111) Ã− (e, q3, # 1111) Ã− (#, q1, 1111) = (e, q1, 1111) Cấu hình cuối cùng nhận được chính là cấu hình xuất phát c’. Như vậy quá trình tính toán có thể lặp lại vô hạn. Chú ý rằng phép tính trên không là phép tính duy nhất có thể, từ cấu hình (111, q3, 1) chẳng hạn, người ta có thể thực hiện chuyển tiếp : (111, q3, 1) Ã− (1111, q3, #) Chúng ta sẽ quay lại xét hiện tượng này. Như vậy, trong một số cấu hình, khi không còn tồn tại một chuyển tiếp nào có thể, người ta nói rằng máy Turing dừng (halt) tại những cấu hình đó. Một phép tính hợp lệ dẫn đến một cấu hình như vậy sẽ không thể kéo dài. Người ta có thể nói về phép tính hợp lệ tối đa trong trường hợp này. Ký hiệu : c Ã− c’ T là sự kiện tồn tại một phép tính hợp lệ giữa các cấu hình c và c’ và không một chuyển tiếp nào có thể kể từ cấu hình c’. Ngược lại, xuất phát từ một số cấu hình, tồn tại các phép tính hợp lệ không bao giờ dừng. Từ đó người ta có thể chia tập hợp các câu f ∈ S* thành hai phần :
  32. Mô hình các máy RAM 29  Tập hợp các câu f sao cho xuất phát từ cấu hình (e, q1, f), máy Turing có ít nhất một phép tính hợp lệ dừng, gọi là L(T).  Tập hợp các câu f sao cho từ cấu hình (e, q1, f), máy Turing không có một phép tính hợp lệ nào dừng. I.3. Cấu hình xuất phát của máy Turing Bây giờ, ta cần xem xét những yếu tố bất tiện của mô hình máy Turing. Ta dễ nhận thấy rằng không thể biết đâu là điểm bắt đầu và đâu là điểm kết thúc của dữ liệu trên băng. Bởi vì phần hữu ích không phân biệt được với phần còn lại trên băng. Để khắc phục điều bất tiện này, người ta đưa vào các quy ước đối với các cấu hình xuất phát như sau :  Lúc đầu, phần hữu ích phải khác rỗng để loại trừ các khả năng liệt của các máy Turing.  Lúc đầu, phần hữu ích không chứa hai ký tự # liên tiếp nhau và dễ dàng xác định được vị trí bắt đầu và vị trí kết thúc để phân biệt với phần còn lại trên băng.  Lúc đầu, đầu đọc−ghi được đặt trong phần hữu ích để chỉ định phần này. Mặt khác, người ta cũng quy ước thêm như sau :  Trạng thái xuất phát phải luôn luôn là q1, gọi là trạng thái đầu (initial).  Đầu đọc−ghi đặt tại ký tự khác # và sát bên trái nhất của phần hữu ích. Một câu f ∈ S* được gọi là được thừa nhận (accepted) bởi máy Turing nếu, xuất phát từ cấu hình ban đầu (e, q1, f), máy Turing đã thực hiện một phép tính hợp lệ và dừng. Ngôn ngữ L(T) gồm tập hợp các câu được thừa nhận, được gọi là ngôn ngữ được thừa nhận (accepted language) bởi máy Turing. Trong ví dụ trên, ngôn ngữ được thừa nhận là các câu chứa một số lẻ số 1 : L(T) = { f ∈ S * | f gồm một số lẻ chữ số 1 }. I.4. Máy Turing đơn định Điểm bất tiện thứ hai trong mô hình máy Turing là có thể thực hiện nhiều phép tính khác nhau tại mỗi thời điểm. Nếu với mọi cặp (q, x) ∈ Q ´ S, tồn tại nhiều nhất một quy tắc của máy Turing có (q, x) là phần bên trái, khi đó từ một cấu hình đã cho c, tồn tại duy nhất một phép tính hợp lệ có thể. Người ta gọi máy Turing như vậy là đơn định (deterministic). Ta dễ nhận thấy tính đơn giản của các máy Turing đơn định với quan niệm như sau : một câu f ∈ S* không được thừa nhận ngay khi phép tính hợp lệ xuất phát từ (e, q1, f) không dừng. Trong trường hợp này, chương trình P của máy Turing : P ⊆ Q ´ S ´ S ´ M ´ Q
  33. 30 Lý thuyết tính toán là một hàm bộ phận (partial function) của Q ´ S vào S ´ M ´ Q, dễ dàng được phân tách thành ba hàm bộ phận khác nhau có cùng miền xác định (domain) trong Q ´ S :  hàm ký tự mới nc : Q ´ S → S  hàm dịch chuyển đầu đọc−ghi mh : Q ´ S → M  hàm trạng thái mới ns : Q ´ S → Q Ba hàm này được định nghĩa như sau : nc (q, x) = y mh (q, x) = m ns (q, x) = q’ nếu và chỉ nếu (q, x, y, m, q’) là một quy tắc của P. Các máy Turing được sử dụng theo nhiều cách khác nhau. Ví dụ vừa được trình bày trên đây mô tả cách thức máy Turing nhận biết các ngôn ngữ. Dưới đây, ta sẽ tiếp tục trình bày cách máy Turing tính toán các hàm. II. Các hàm T−tính được Giả sử ta chỉ xét các máy Turing đơn định. Cho T = là một máy Turing. Ta nói T xác định một hàm bộ phận fT * * từ S → S như sau : miền xác định của hàm fT là ngôn ngữ được thừa nhận bởi T, và với mỗi câu f ∈ S*, ta có một phép tính hợp lệ tối đa : (e, q , f) Ã− c’ = (g, q, h) 1 T với fT được xác định bởi : fT(f) = gh gh được gọi là kết quả của phép tính của T đối với câu vào f. Người ta cũng nói náy Turing T thực hiện (tính) hàm fT. Ví dụ 3.2 : Cho T1 = với S = {0, 1, #}, Q = {q1, q2, q3} và 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 }
  34. Mô hình các máy RAM 31 Bây giờ xét các cấu hình c1 = (e, q1, 10100) và c2 = (e, q1, 100111). Tồn tại phép tính tối đa dẫn c1 và c2 đến các cấu hình (1010, q3, 1) và (10, q3, 1000) tương ứng như sau : c = { e, q , 10100} Ã− (1010, q , 1) 1 1 T 3 c = { e, q , 100111} Ã− (10, q , 1000) 2 1 T 3 Dễ dàng nhận thấy rằng, xuất phát từ một cấu hình c = (e, q1, f), tồn tại một phép tính tối đa dẫn c đến cấu hình (g, q3, h) sao cho, nếu f là biểu diễn nhị phân của số nguyên n, thì câu gh là biểu diễn nhị phân của số nguyên n + 1. Người ta nói máy Turing T1 đã thực hiện hàm tính số nguyên kế tiếp (successor) trên một biểu diễn nhị phân của số nguyên. Ví dụ 3.3 : Cho T2 = với S = {1, #}, Q = {q1, q2, q3, q4} và P = { q1, 1 → #, R, q2, q2, 1 → # R, q3, q3, 1 → 1, R, q3, q3, # → 1, L, q4 } Nếu qui ước biểu diễn đơn nguyên (unary) của một số nguyên bởi viết liên tiếp n+1 chữ số 1 (số nguyên 0 được biểu diễn bởi một chữ số 1) và các cặp số nguyên biểu diễn theo quy ước này được đặt cách nhau một ký tự trắng #, khi đó, dễ dàng nhận thấy rằng máy Turing T2 thực hiện hàm tính tổng hai số nguyên cho kết quả là một biểu diễn đơn nguyên. Chẳng hạn : (ε, q , 11 # 111) Ã− (##1111, q , 111) 1 T 4 Định nghĩa 3.1 : Một hàm bộ phận φ từ S* → S* được gọi là tính được bởi máy Turing (Turing −computable), viết tắt T−tính được, nếu tồn tại một máy Turing đơn định tính được hàm này. Rõ ràng, với mỗi hàm T−tính được, sẽ có vô số các máy Turing tính nó. Chú ý rằng quan điểm tính được trong lý thuyết tính toán được nêu ra ở đây liên quan chặt chẽ đến sự nhận biết (cognition) : *  Một mặt, với mọi ngôn ngữ L ⊂ S , sẽ có một hàm đặc trưng (characteristic function) δL tương ứng được định nghĩa bởi : δL(f) = 1 nếu f ∈ L δL (f) = 0 nếu không (f ∉ L)
  35. 32 Lý thuyết tính toán Người ta cũng kết hợp L với một hàm đặc trưng cục bộ (partial characteristic function) δ‘L được định nghĩa bởi : δ‘L(f) = 1 nếu f ∈ L δ‘L(f) không xác định nếu không (f ∉ L) * *  Mặt khác, với mọi hàm φ : S → S , φ được kết hợp với một ngôn ngữ Gφ , trên S ∪ {#} chẳng hạn, gọi là đồ thị của hàm, được xác định bởi : G = { f # φ(f) | f ∈ Dom(φ) } φ Sau đây ta sẽ chỉ ra rằng, lớp các hàm T−tính được là rất lớn, trước khi chỉ ra rằng tồn tại các hàm không là T−tính được. III. Lớp các hàm T−tính được Trong mục này, ta sẽ xét một số hàm T-tính được rất sơ cấp (elementary functions), để từ đó, ta xây dựng các hàm phức tạp hơn nhờ phép hợp thành. Ta cũng tìm cách mở rộng khả năng hoạt động của các máy Turing. III.1. Một số hàm sơ cấp Ta xây dựng máy Turing để tính toán một số hàm rất sơ cấp từ G* vào G*, n hay (G*) vào G*, trong đó, G là một bảng chữ không chứa ký tự trắng #, và các bộ−n (n−tuple) gồm các phần tử được ngăn cách nhau bởi một ký tự trắng #. Đó là các hàm hằng, hàm chiếu, hàm kế tiếp và hàm kế trước. III.1.1. Các hàm hằng (constant functions) Xét hàm hằng : n * n * Bin_Fiv G : (G ) → G * sao cho mọi dữ liệu vào là một bộ−n câu của G , dạng f1#f2# #fn, hàm hằng luôn trả về một câu nào đó của G*. Ví dụ 3.4 : Giả sử G = {0, 1} và n = 2, với mọi dữ liệu vào là một cặp câu dạng f#g, 2 * Bin_Fiv G luôn trả về một câu, chẳng hạn 101∈G (101 là biểu diễn nhị phân của số 5). 2 Xây dựng máy Turing thực hiện hàm hằng Bin_Fiv G như sau : T = với S = G ∪ {#}, Q = {q1, q2, q3, q4, q5} và P = { q1, 1 → $, R, q1, q1, # → #, R, q2, q1, 0 → #, R, q1,
  36. Mô hình các máy RAM 33 q2, 0 → #, R, q2, q2, 1 → #, R, q2, q2, # → 1, L, q3, q3, # → 0, L, q4, q4, # → 1, L, q5 } Ta có : c = (e, q , #01 #10) Ã−* ( #, q , # 101 #). 1 T 5 Hàm hằng rất dễ triển khai và có thể xây dựng bất kỳ hàm hằng nào. III.1.2. Các hàm chiếu (projection functions) Xét hàm chiếu : n Projn, iG : (G*) → G* sao cho với mọi bộ−n các câu của G*, hàm chiếu trả về câu thứ i của dãy này. Ví dụ 3.5 : Giả sử G = {0, 1}, n = 4 và i = 2, xây dựng máy Turing thực hiện hàm chiếu 4, 2 Proj G để trả về kết quả là câu thứ hai trong dữ liệu vào là dãy bốn câu như sau : T = với S = G ∪ {#}, Q = q1, q2, q3, q4, q5} và P = { q1, 1 → #, R, q1, q1, 0 → # R, q1, q1, # → #, R, q2, q2, 1 → 1, R, q2, q2, 0 → 0, R, q2, q2, # → #, R, q3, q3, 1 → #, R, q3, q3, 0 → #, R, q3, q3, # → #, R, q4, q4, 1 → #, R, q4, q4, 0 → #, R, q4 q4, # → #, L, q5 } Ta có c = (e, q , 10#01#100#101#) Ã−* (#, q , #10#) 1 T 5 Ta nhận thấy rằng hàm chiếu cũng rất dễ triển khai như hàm hằng và có thể xây dựng bất kỳ kiểu hàm chiếu nào. III.2. Các hàm kế tiếp (successor functions) Xét hàm kế tiếp :
  37. 34 Lý thuyết tính toán * * SuccG : G → G * sao cho với mọi câu f∈G , hàm SuccG trả về câu kế tiếp của f theo thứ tự đã cho. Ví dụ 3.6 : Giả sử G = {0, 1, 2} với thứ tự 0 với S = G ∪ {#}, Q = { q1, q2, q3} và P = { q1, 0 → 0, R, q1, q1, 1 → 1, R, q1, q1, 2 → 2, R, q1 q1, # → #, L, q2, q2, 0 → 1, R, q3, q2, 1 → 2, R, q3, q2, 2 → 0, L, q2, q2, # → 1, R, q3 } Ta có c = (e, q , # 22 #)Ã−* (#1, q , 00#) 1 T 3 Ta nhận thấy rằng có thể dễ dàng xây dựng các kiểu hàm kế tiếp cho mọi bảng chữ và cho mọi kiểu thứ tự của các ký tự trong bảng chữ. III.3. Các hàm kế trước (predecessor functions) Tương tự hàm kế tiếp, ta có thể dễ dàng xây dựng hàm kế trước : * * PredG : G → G * sao cho với mọi câu f∈G , hàm PredG trả về câu kế trước của f trong thứ tự đã cho của bảng chữ S. Để hàm PredG là toàn phần, ta cần quy ước rằng câu đứng trước câu rỗng cũng chính là câu rỗng. Bài tập : Xây dựng một máy Turing thực hiện hàm kế trước. III.4. Sự hợp thành (composition) Nhiều hàm được định nghĩa từ nhiều hàm khác hợp thành. Ta sẽ nghiên cứu các kỹ thuật cho phép xây dựng lớp các hàm T−tính được nhờ phép hợp thành.
  38. Mô hình các máy RAM 35 III.4.1. Các máy được tiêu chuẩn hóa Một máy Turing được gọi là đã tiêu chuẩn hóa (standadized) nếu, khi tính toán xong, đầu đọc-ghi được đặt tại vị trí khác ký tự trắng # cận trái nhất của phần hữu ích trên băng. ←−− Phần hữu ích −−→ . . . # # # a # # # . . . q Hình 3.3 Máy Turing được tiêu chuẩn hóa Mệnh đề 3.1 : Nếu T là một máy Turing, thì có thể xây dựng từ T một máy turing T’ khác được tiêu chuẩn hóa cùng thực hiện một chức năng (tính hàm) như T. Bài tập : Chứng minh mệnh đề 3.1 Mệnh đề 3.2 : Có thể luôn luôn giả thiết được rằng trạng thái đầu (trạng thái xuất phát) không nằm trong bất kỳ một vế phải nào của quy tắc. Chứng minh : Thật vậy, nếu q1 là trạng thái đầu, ta thêm vào Q một trạng thái mới q’1 và thêm vào P mọi quy tắc dạng : q’1, x → y, m, qi sao cho quy tắc : q1, x → y, m, qi là một quy tắc của máy Turing đang xét. Vậy người ta chọn lại q’1 là trạng thái đầu. Như vậy, máy Turing vừa thêm q’1 thực hiện cùng một chức năng với máy Turing cũ và thỏa mãn điều kiện của giả thiết. Lúc này, người ta có thể biểu diễn máy Turing có trạng thái đầu thỏa mãn mệnh đề 3.2 bởi sơ đồ sau đây : q1 T Hình 3.4. Máy Turing T có trạng thái đầu
  39. 36 Lý thuyết tính toán III.4.2. Các máy Turing được chuẩn hóa Cho máy Turing T = có một tập hợp con A các trạng thái thõa mãn : 1. Không một trạng thái nào của A nằm trong vế trái của quy tắc 2. Với mọi trạng thái q∈Q\A và mọi ký tự x∈S, tồn tại một quy tắc của P có (q, x) là vế trái. Một máy Turing như vậy được gọi là đã được chuẩn hóa (normalized). Nói cách khác, máy Turing là được chuẩn hóa nếu với một tập hợp trạng thái A, một phép tính dừng nếu và chỉ nếu máy Turing rơi vào một trạng thái của A. Một trạng thái của A được gọi là một trạng thái dừng (halt state) Mệnh đề 3.3 : Nếu T là một máy Turing, có thể xây dựng từ T một máy Turing T’ chuẩn hóa thực hiện cùng chức năng với T. (Tự chứng minh) Chú ý rằng người ta có thể xem rằng máy Turing chỉ có một trạng thái dừng, lúc đó, máy Turing có thể được biểu diễn bởi sơ đồ : q1 T qh Hình 3.5. Máy Turing T được chuẩn hóa Nếu tiến hành đồng thời cả hai cách xây dựng vừa nêu, chúng ta sẽ nhận được một máy Turing vừa được tiêu chuẩn hóa, vừa được chuẩn hóa. III.4.3. Tổ hợp các máy Turing Cho T là một máy Turing chuẩn hóa có một trạng thái dừng duy nhất qh, và T’ là một máy Turing bất kỳ nào đó. Ta định nghĩa máy Turing tổ hợp từ T và T’, ký hiệu T next T’, bằng cách đánh số lại các trạng thái của T’ để nhận được các trạng thái tách rời (disjoint) với các trạng thái của T và lấy trạng thái dừng của T làm trạng thái đầu của T’ : qh q1 T T’ = q’1 Hình 3.6. Máy Turing T next T’ Chú ý rằng nếu T’ được tiêu chuẩn hóa (một cách tương ứng, được chuẩn hóa) thì máy Turing T next T’ cũng được tiêu chuẩn hóa (được chuẩn hóa). Rõ ràng rằng, nếu T được tiêu chuẩn hóa và thực hiện hàm f và nếu T’ thực hiện hàm f’, thì máy Turing T next T’ thực hiện hàm ghép f’°f.
  40. Mô hình các máy RAM 37 III.5. Lập trình trên ngôn ngữ bậc cao máy Turing Để mở rộng phạm vi các lệnh thông dụng và sử dụng chúng như là các lệnh vĩ mô (macro instruction), người ta định nghĩa các máy Turing tiện ích như sau : Ví dụ 3.7 : Xây dựng máy Turing T = cho phép dời đầu đọc−ghi qua phải đến vị trí ký tự thứ n trong tập ký tự G là một tập hợp con của S. Giả sử lấy n = 2, ta có tập hợp P gồm các lệnh như sau : P = { q1, x → x, R, q1, với ∀x ∉ G q1, y → y, R, q2, với ∀y ∈ G q2, x → x, R, q2, với ∀x ∉ G q2, y → y, R, q3, với ∀y ∈ G q3, x → x, L, q4 } với ∀x ∈ S Một cách tương tự, ta có thể xây dựng máy Turing cho phép dời đầu đọc−ghi qua phải (hay qua trái) đến vị trí (ngay trước, hoặc ngay sau) ký tự thứ n trong G là một tập hợp con của S. Ta cũng có thể xây dựng một số máy Turing tiện ích khác để thực hiện các chức năng như : chuyển thành hằng, phép chiếu, kế tiếp, kế trước, và các hàm mới như sao chép, hoán vị. Sau đây, ta sẽ mở rộng phương tiện thể hiện các máy Turing bằng cách đưa vào các cấu trúc điều khiển và chỉ ra cách hoạt động của chúng. III.5.1. Cấu trúc if then else và cấu trúc rẽ nhiều nhánh Cho T là một máy Turing chuẩn hóa dừng ở các trạng thái q , q , , q và h1 h2 hk T1, T2, , Tk là những máy Turing bất kỳ, người ta định nghĩa phép tổ hợp tổng quát (generalized combinator) từ phép tổ hợp next bởi : T next if h1 : T1, if h2 : T2, , if hk : Tk là máy Turing nhận được bằng cách đánh số lại các trạng thái của Ti để nhận được các trạng thái tách rời nhau giữa chúng và tách rời các trạng thái của T, bằng cách lấy trạng thái dừng q của T làm trạng thái đầu của T , lấy trạng thái h1 1 dừng q của T làm trạng thái đầu của T , , lấy trạng thái dừng q của T làm h2 2 hk trạng thái đầu của Tk. Nếu máy Turing T dừng với mọi dữ liệu vào, T sẽ thực hiện phép rẽ nhánh theo các trường hợp khác nhau (với if then else là một trường hợp đặc biệt).
  41. 38 Lý thuyết tính toán Chẳng hạn với k = 2, máy Turing T thực hiện lệnh if then else : q h1 T1 q1 T q h2 T2 Hình 3.7. Máy Turing T next if h1 : T1, if h2 : T2 III.5.2. Cấu trúc while Cho T là máy Turing chuẩn hóa có hai trạng thái dừng q và q , và T’ là h1 h2 một máy Turing chuẩn hóa có duy nhất một trạng thái dừng q’h. Giả thiết rằng T và T’ có các trạng thái rời nhau. Người ta định nghĩa while T do qh : T’ là máy Turing nhận được từ T và T’ bằng cách lấy trạng thái dừng q của T làm trạng h2 thái đầu của T’ và lấy trạng thái dừng của T’ làm trạng thái đầu q1 của T. Máy Turing while T do qh : T’ được vẽ như sau : q h1 q1 T q h2 T’ Hình 3.8. Máy Turing while T do h2 : T’ Người ta nhận thấy rằng, các trạng thái của một máy Turing có thể được xem như là các nhãn (label) của chương trình của chính máy này. Do vậy, các quy tắc trong P dạng q, x → y, m, p có thể được viết dưới dạng : q : if x then y, m next goto p và bằng cách nhóm tất cả các quy tắc có cùng trạng thái q là vế trái, lúc này chỉ cần viết q ở quy tắc đầu tiên liên quan. Chương trình tìm phần tử kế tiếp ở ví dụ 3.7 bây giờ được viết lại như sau : q1 : if 0 then 0, R next goto q1 if 1 then 1, R next goto q1 if 2 then 2, R next goto q1 if # then #, L next goto q2 q2 : if 0 then 1, R next goto q3
  42. Mô hình các máy RAM 39 if 1 then 2, R next goto q3 if 2 then 0, L next goto q2 if # then #, R next goto q3 q3 : halt III.6. Quản lý bộ nhớ Khi xây dựng các máy Turing thực hiện các hàm phức tạp, người ta gặp phải vấn đề quản lý bộ nhớ, nghĩa là khả năng tổ chức lại nội dung các ô ở trên băng. Ta đưa vào các khả năng quản lý bộ nhớ cho máy Turing như sau : III.6.1. Máy Turing chuyển một ô qua phải Việc chuyển một ký tự sang bên phải được thực hiện đối với một bảng chữ có ba ký tự là S = {#, 0, 1} nhờ máy Turing có tập hợp P gồm các quy tắc như sau : P = { q1, 0 → #, R, q(0), q1, 1 → #, R, q(1), q(0), 0 → 0, R, q(0), q(0), 1 → 0, R, q(1), q(1), 0 → 1, R, q(0), q(1), 1 → 1, R, q(1), q(0), # → 0, R, q(#), q(1), # → 1, R, q(#), q(#), 0 → #, R, q(0), q(#), 1 → #, R, q(1) } Máy Turing này dừng lại khi gặp hai ký tự # liên tiếp. Từ cách xây dựng này, dễ dàng xây dựng được các máy Turing chuyển k ô qua phải (hoặc qua trái). III.6.2. Máy Turing chỉ sử dụng phần băng bên phải kể từ vị trí đầu tiên của đầu đọc-ghi Nếu T = là một máy Turing thực hiện hàm f, có thể xây dựng một máy Turing khác mô phỏng T sao cho đầu đọc−ghi không bao giờ vượt qua bên trái vị trí ban đầu. Giả sử T1 là máy Turing đặt một dấu h ở vị trí đầu tiên của đầu đọc−ghi và di chuyển nội dung câu vào một ô qua bên phải. Giả sử T2 là máy Turing cho phép di chuyển nội dung một ô qua bên phải xuất phát từ vị trí đầu tiên của đầu đọc−ghi (và đặt một ô ký tự trắng # tại vị trí ô đầu tiên đã di chuyển). Như vậy, có bao nhiêu trạng thái trong máy T thì có bấy nhiêu máy sao chép của T2 và giả thiết chúng đều đã được tiêu chuẩn hóa và chuẩn hóa. Ký hiệu T2i
  43. 40 Lý thuyết tính toán là bản sao tương ứng với trạng thái q , còn p là trạng thái đầu và p là trạng thái i i1 ih cuối của T2i. Xây dựng từ máy T một máy mới T3 có tất cả các quy tắc của T và các quy tắc của tất cả các máy T , ngoài ra, P còn có thêm các quy tắc sau : 2i 3 P = { q , h → h, R, p 3 i i1 p , x → x, L, q } với x ∈ S là ký tự bất kỳ. ih i Với các điều kiện trên, T1 next T3 là máy thỏa mãn yêu cầu đặt ra. III.7. Một số máy Turing thông dụng Sau đây ta sẽ xét một số máy Turing thực hiện các chức năng phức tạp hơn. III.7.1. Sao chép Xây dựng hàm : * * 2 CopyG : G → (G ) * * 2 sao cho ∀ câu f ∈ G , với G = {0, 1}, hàm CopyG trả về câu f #f ∈ (G ) . Giả sử T1 là máy Turing đọc một ký tự và thay thế ký tự đó bởi ký tự đánh dấu a, sau đó di chuyển qua phải để viết lại ký tự này tại vị trí của ký tự trắng # đầu tiên gặp phải, sau đó quay trở lại ký tự đánh dấu a để thay thế nó bởi ký tự ban đầu. Máy T1 dừng ngay lập tức ở bên phải vị trí này. Cho T1 = với S = G ∪ {a, b, #}, Q = {q1, q2, q3, q4, q5, q6} và P = { q1, 1 → a, R, q2, q1, 0 → a, R, q4, q2, 0 → 0, R, q2, q2, 1 → 1, R, q2, q4, 0 → 0, R, q4, q4, 1 → 1, R, q4, q2, b → b, R, q2, q4, b → b, R, q4, q2, # → 1, L, q3, q4, # → 0, L, q5 q3, 0 → 0, L, q3, q3, 1 → 1, L, q3, q5, 0 → 0, L, q5,
  44. Mô hình các máy RAM 41 q5, 1 → 1, L, q5, q3, b, → b, L, q3, q5, b → b, L, q5, q3, a → 1, R, q6, q5, a, → 0, R, q6 } Xây dựng T2 là máy Turing : while : T1 Xuất phát từ câu vào fb#, T2 cho kết quả là fbf#. Vậy T2 là máy sao chép cần xây dựng. III.7.2. Kiểm tra bằng nhau Cần xây dựng máy Turing so sánh hai câu cho trước có bằng nhau không. Muốn vậy, ta xây dựng máy Turing có hai trạng thái dừng qYes và qNo sao cho khi cho câu vào f#g, máy dừng ở trạng thái qYes nếu f = g và máy dừng ở trạng thái qNo nếu f ≠ g. Máy hoạt động như sau : thay đổi câu vào f#g thành fagb với a và b là hai ký tự đánh dấu. Sau đó, trong khi f và g còn khác rỗng, thay thế các ký tự cuối của f và g bởi a và b tương ứng rồi ghi nhớ chúng. Nếu sau khi thay thế, chúng khác nhau, máy dừng ở trạng thái qNo. Nếu không, tiếp tục quá trình. Cho tới khi đồng thời cả f và g đều rỗng thì máy dừng ở trạng thái thái qYes, nếu không phải, máy dừng ở trạng thái qNo. III.7.3. Liệt kê các câu, các cặp câu và dãy các câu Việc liệt kê các câu của S* rất đơn giản : người ta liệt kê câu đầu tiên của S* (là một hằng), sau đó lần lượt liệt kê câu kế tiếp của câu trước đó đã liệt kê. Việc liệt kê các cặp câu được tiến hành như sau : giả sử máy Turing T1 đã có trên băng vào một cặp câu, giả sử f#g, T1 thực hiện việc chép kế tiếp một cặp câu, * gồm câu đầu tiên của S , là f, và câu kế tiếp của câu kia, là succ(g). Sau đó T1 lặp đi lặp lại việc chép cặp câu tiếp theo bằng cách lấy câu kế tiếp của thành phần thứ nhất, là succ(f), và câu kế trước của thành phần thứ hai, là pred(succ(g)), khi mà thành phần này không phải là câu đầu tiên của S*. Giả sử máy Turing T2 có cặp câu vào x#y trên băng, T2 thực hiện chép một cặp câu, gồm câu kế tiếp của câu đầu tiên, là succ(x), và câu còn lại, là y. Sau đó, T2 thực hiện lặp đi lặp lại việc chép cặp câu tiếp theo bằng cách lấy câu kế trước
  45. 42 Lý thuyết tính toán của thành phần thứ nhất, là pred(succ(x)), khi mà thành phần này không phải là câu đầu tiên của S*, và lấy câu kế tiếp của thành phần thứ hai, là succ(y). Máy Turing cần tìm thực hiện chép một cặp câu gồm hai câu đầu tiên của S*, sau đó lặp đi lặp lại thực hiện T1 next T2. Bài tập : Mô tả máy Turing liệt kê dãy các câu trên S*. III.7.4. Các hàm chiếu ngược (antiprojection function) Xét hàm chiếu ngược : n n-1 Antiprojn, iG : (G*) → (G*) sao cho biến mỗi bộ−n là dãy n câu của G* thành bộ−(n−1) câu, bằng cách lấy đi câu thứ i của dãy n câu. Máy Turing thực hiện hàm chiếu ngược được mô tả như sau : sau khi đặt đầu đọc−ghi ngay trước câu thứ i (tại ký tự # thứ i của dữ liệu vào), máy Turing đánh dấu a tại vị trí này và xóa (thay thế bởi #) câu thứ i cho đến khi gặp ký tự # đặt trước câu thứ i+1. Sau đó, máy thực hiện lặp đi lặp lại phép dời qua trái một ô cho phần các câu còn lại (từ i + 1 đến n) cho đến khi gặp ký tự đánh dấu a. Máy dừng lại sau khi đã xóa ký tự đánh dấu a. III.7.5. Các hàm giao hoán Hàm giao hoán (permutation function) : Permi, j : (G*)n → (G*)n cho phép giao hoán câu thứ i và câu thứ j của dãy n câu : * n (w1, , wi, ,wj, , wn) ∈ (G ) thành : (w1, ,wi-1, wj , wi+1 , , wj-1 , wi , wj+1 , , wn) nghĩa là câu thứ i đổi chỗ cho câu thứ j và ngược lại. Máy Turing thực hiện hàm giao hoán được xây dựng bằng cách tổ hợp cách máy sao chép và máy chiếu ngược. III.8. Các hàm T-tính được phức tạp hơn Bây giờ ta sẽ xây dựng các máy Turing thực hiện các phép tính số học dựa trên các công cụ đã có. Phép cộng : Ta cần thực hiện phép cộng hai số nguyên hệ 2 : Giả sử m và n là hai số nguyên được biểu diễn bởi hai câu u và v trên bảng chữ {0, 1}. Gọi dữ liệu là u#v và ta cần chuyển nó thành uabv, với a và b là hai ký tự đánh dấu.
  46. Mô hình các máy RAM 43 Đặt đầu đọc−ghi tại ký tự cuối cùng của v, tiếp theo, trong khi ký tự đọc được (dưới đầu đọc−ghi) chưa là b thì ghi nhớ bằng cách xóa ký tự đọc được (0 hay 1) và đi đến ngay trước ký tự a. Ở đây, tùy theo ký tự đã đọc (0 hay 1 hoặc ký tự trắng # được xử lý hoàn toàn tương tự 0), tùy theo ký tự đã ghi nhớ, và theo một số nguyên 0 hay 1 cũng đã ghi nhớ (phần nhớ do 1 + 1), lúc đó đã được khởi động giá trị 0, viết ký tự a theo sau 0 hoặc 1 tùy theo kết quả (nghĩa là sự đối chiếu của tổng 3 chữ số này), và ghi nhớ phần nhớ 0 hoặc 1 (tùy theo có hay không ít ra là hai chữ số 1 trong 3 chữ số này). Tiếp tục quay lại ngay trước ký tự trắng # đầu tiên bên phải, rồi lại quay đến ngay trước chữ a và trong khi phần nhớ là 1, thay đổi ký tự đọc được và dời một ô qua bên trái : 1 được thay thế bởi 0, với phần nhớ vẫn giữ, và 0 được thay thế bởi 1, với phần nhớ thay đổi thành 0. Từ đó nhận được câu fagb với fg là biểu diễn nhị phân của m + n. Máy Turing xây dựng theo cách trên có thể thực hiện được phép cộng các số nguyên biểu diễn trong một hệ đếm bất kỳ. Bài tập : Xây dựng máy Turing thực hiện phép trừ, phép nhân và phép chia của hai số nguyên biểu diễn trong hệ 2, hệ 10 hoặc trong một hệ đếm bất kỳ. III.9. Nhận xét Như đã trình bày, nhờ các máy Turing, ta có thể thực hiện được một lớp rộng các hàm xử lý các phép tính số học. Tuy nhiên, như ta sẽ thấy về sau, lớp các hàm T−tính được không chứa tất cả mọi hàm. Như vậy, ta không thể xây dựng bất cứ mọi hàm nhờ các máy Turing. Vì vậy, trong những phần sau, ta cần khoanh vùng chính xác các hàm T−tính được. Bây giờ ta xét một hàm f từ Ν → Ν và bốn cách biểu diễn các số nguyên r1, r2, r3 và r4 (chẳng hạn đơn phân, nhị phân, thập phân và thập lục phân). Giả sử f1 là hàm nhận đối số là một số nguyên n có dạng biểu diễn r1 để cho kết quả f (n) có dạng biểu diễn r2. Giả sử f2 là hàm nhận đối số là một số nguyên n có dạng biểu diễn r3 để cho kết quả f (n) có dạng biểu diễn r4. Khi đó, f1 là T−tính được khi và chỉ khi f2 là T−tính được. Theo cách xây dựng hàm f, ta thấy rằng có thể xây dựng được máy Turing TC có dữ liệu vào là một số nguyên n dưới dạng biểu diễn r1 để có kết quả dưới dạng biểu diễn r3. Tương tự, ta có thể xây dựng máy TD có dữ liệu vào là một số nguyên m dưới dạng biểu diễn r4 để cho kết quả dưới dạng biểu diễn r2. Nếu T’ là máy Turing thực hiện hàm f2, thì T =TC next T’ next TD là một máy Turing thực hiện hàm f1. Như vậy một hàm T−tính được phải không phụ thuộc vào cách biểu diễn lựa chọn, miễn rằng cách biểu diễn này vẫn còn hợp lý. Nghĩa là người ta có thể chuyển từ cách biểu diễn này qua cách biểu diễn khác nhờ một máy Turing.
  47. 44 Lý thuyết tính toán Chính vì vậy mà người ta thường nói theo cách lạm dụng (excessively) về hàm mà không chỉ rõ cách biểu diễn lựa chọn. Chẳng hạn, tồn tại T−tính được phép cộng các số nguyên biểu diễn trong một hệ đếm nào đó thì người ta nói rằng phép cộng các số nguyên là T−tính được. Mối quan hệ hẹp giữa các ngôn ngữ và các hàm được chỉ rõ qua các mệnh đề sau. Mệnh đề 3.4 : Ngôn ngữ L là được nhận biết bởi một máy Turing khi hàm cục bộ đặc trưng của L, viết d’L, là T−tính được. Chứng minh : Nếu ngôn ngữ L nhận biết bởi một máy Turing T, ta có thể giả thiết T được chuẩn hóa và tiêu chuẩn hóa. Nếu T là một máy Turing viết ra hằng 1, thì máy T next T1 là một máy Turing thực hiện hàm d’L. Nếu T’ là một máy Turing thực hiện d’L, T’ nhận biết L. Mệnh đề 3.5 : Hàm f là T−tính được khi và chỉ khi đồ thị Gf của nó là được nhận biết bởi một máy Turing. Chứng minh : «Chỉ khi» : Cho T là máy Turing thực hiện hàm f, ta cần chứng minh rằng đồ thị Gf của nó được nhận biết bởi một máy Turing nào đó. Nếu T là máy Turing thực hiện hàm f : f → f( f) = g, có thể giả thiết rằng T được chuẩn hóa và tiêu chuẩn hóa, đầu đọc−ghi của T sẽ không bao giờ vượt qua bên trái vị trí xuất phát. Để xây dựng máy Turing nhận biết Gf, ta xây dựng hai máy Turing bổ trợ : − T1 hoán vị hai câu vào (f#g trở thành g#f) và dời đầu đọc-ghi về vị trí bắt đầu của câu thứ hai (câu mới), − T2 so sánh hai câu vào g#g và sẽ không bao giờ dừng trong trường hợp không bằng nhau. Từ đây, máy Turing : T1 next T next T2 có thể nhận biết Gf. «Khi» : Cho T là một máy Turing nhận biết ngôn ngữ Gf,, ta cần chứng minh rằng có thể xây dựng được một máy Turing thực hiện hàmf. Giả sử T là máy Turing nhận biết ngôn ngữ (hay đồ thị của φ) Gf ⊂ S*, Gφ = { f # g | f ∈ Dom(φ) và g = φ(f) } Ta xây dựng một máy Turing T’ thực hiện hàm f theo cách sau : nếu f là một dữ liệu vào của T’, máy T’ sẽ liệt kê tất cả các cặp (g, n_ ) có thể, với g là một câu, g∈S* và n là độ dài của phép tính (hay quá trình đoán nhận) đối với dữ liệu f #g của máy T đã cho. Nếu T dừng trên f #g, thì T’ cũng dừng sau mỗi cặp liệt kê.
  48. Mô hình các máy RAM 45 Ở đây, n_ là một biểu diễn nào đó của số nguyên n. Từ nay về sau, ta quy ước rằng mọi số nguyên có gạch dưới chỉ định biểu diễn nhị phân của số nguyên đó. Cụ thể, xuất phát từ máy T, đầu tiên ta xây dựng một máy TU sao cho với mọi dữ liệu f#g và mọi số nguyên n, máy TU thực hiện đối với dữ liệu f#g#n_. và dừng khi gặp trạng thái qYes nếu T thực hiện phép tính đối với dữ liệu f#g dừng ở độ dài n, và dừng ở trạng thái qNo nếu T không dừng. Ta cũng giả thiết rằng, đầu đọc của TU không bao giờ qua trái kể từ vị trí xuất phát, và, trong trường hợp thất bại (dừng ở trạng thái qNo), TU xóa hết nội dung trên băng vào của nó. Tiếp theo, ta xây dựng máy các máy Turing : − T1 nhận dữ liệu vào f#g#n_ để trả về kết quả là f#g’#n_ ’, với (g’, n’) là cặp câu theo sau cặp (g, n). − T2 thực hiện sao chép f#g#n_ thành f#g#n_ #f#g#n_ và đặt đầu đọc−ghi vị trí bắt đầu câu f thứ hai. − T0 chép qua bên phải f cặp (g, n) đầu tiên để nhận được f#g#n_. . Từ đó, máy Turing T’ được xây dựng như sau : T0 next T2 next TU next while T give qNo : T1 next T2 next T_ cho phép thực hiện f.
  49. 46 Lý thuyết tính toán IV. Các biến thế khác của mô hình máy Turing Theo quan niệm của lý thuyết tính toán, hai mô hình được gọi là tương đương nếu những gì tính được (một cách tương ứng : nhận biết được, liệt kê được) trong một mô hình này thì cũng có thể tính được (một cách tương ứng : nhận biết được, liệt kê được) trong mô hình kia. Trong mục này, ta sẽ chỉ ra rằng các mô hình biến thể (variant model) của mô hình các máy Turing tiêu chuẩn hoá đã xét trước đây cũng chỉ là những mô hình tương đương với chúng. Nhờ khái niệm về phép mô phỏng (simulation), trước hết ta cần chỉ ra rằng các máy Turing nhiều băng và các máy Turing không đơn định có thể được mô phỏng bởi các máy Turing tiêu chuẩn hoá. Sau đó, ta sẽ xem xét vấn đề về bản số giới hạn (số lượng ký tự) của một bảng chữ. IV.1. Mô phỏng một máy Turing bởi một máy khác Định nghĩa 3.3 : Một máy Turing T được mô phỏng bởi một máy T’ nếu xây dựng được một phép đơn ánh i từ các cấu hình của T vào các cấu hình của T’, sao cho, nếu cÃ− c’ trong T, thì i(c) Ã−* i(c’) trong T’. Máy T’ dừng kể từ một cấu hình xuất phát i(c) nếu và chỉ nếu T dừng kể từ một cấu hình xuất phát c. Nếu T’ mô phỏng T, thì hàm do T’ thực hiện sẽ cho phép tìm lại hàm do T thực hiện modulo phép biểu diễn các đối tượng ( dữ liệu và kết quả). Một cách cụ thể hơn, giả sử TC là một máy Turing thực hiện phép đơn ánh, nghĩa là, xuất phát từ một dữ liệu của máy T, trả về một dữ liệu tương ứng cho T’ (người ta nói rằng dữ liệu đã được mã hóa). Giả sử TD thực hiện phép đơn ánh ngược lại, nghĩa là xuất phát từ một kết quả của máy T’ trả về một kết quả cho T (người ta nói rằng dữ liệu đã được giải mã). Khi đó máy : TC next T’ next TD quả thực đã thực hiện cùng một hàm với máy T. Ví dụ 3.8 : Phép tính giữa hai ký tự đánh dấu Cho T = là máy Turing thực hiện hàm f, xây dựng máy T’ trên bảng chữ S ∪ {a, b}, với a và b là hai ký tự mới. Máy T’ sẽ mô phỏng máy T sao cho một cấu hình (f, q, g) của T sẽ được mã hóa bởi một cấu hình (af, q, gb) của T’. Cho Q’ và Q’’ là hai tập hợp các trang thái có song ánh (bijection) với Q. Đặt q’i và q’’i lần lượt là các trạng thái của Q’ và Q’’ có song ánh với trạng thái qi của Q. Xây dựng các tập hợp quy tắc P và P” như sau : P’ = { qi, b → #, R, qi’, q’i, # → b, L, qi } với ∀qi ∈ Q
  50. Mô hình các máy RAM 47 P’’ = { qi, a → #, L, q’’i, q’’i, # → a, R, qi } với ∀qi ∈ Q Khi đó, máy T’ = cũng là một máy Turing. Bây giờ xây dựng máy Turing TC (với chương trình PC) có dữ liệu vào là câu f và kết quả là câu afb : PC = { q1, x → x, L, q2, q2, # → a, R, q3, q3, x → x, R, q3, q3, # → #, R, q4, q4, x → x, R, q3 q4, # → #, L, q5, q5, # → b, L, q6, q6, y → y, L, q6 q6, a → a, R, q7 } Ở đây, x ≠ # và x ∈ S là ký tự bất kỳ, y ∈ S cũng là ký tự bất kỳ. Xây dựng máy Turing TD (với chương trình PD) có dữ liệu vào là câu afb và kết quả là câu f : PD = { q1, y → y, R, q1, q1, b → #, L, q2, q2, y → y, L, q2, q2, a → #, R, q3 } Ở đây y là ký tự bất kỳ y ≠ a và y ≠ b. Như vậy máy Turing : TC next T’ next TD thực hiện hàm f.
  51. 48 Lý thuyết tính toán IV.2. Các biến thể của máy Turing Biến thể quan trọng nhất và thông dụng nhất là máy Turing không đơn định (non-deterministic). Tuy nhiên vẫn còn các biến thể khác với những thay đổi không lớn. Ta sẽ nghiên cứu các máy Turing không đơn định ở chương cuối khi nghiên cứu các lớp độ phức tạp. IV.2.1. Máy Turing có k băng Máy Turing loại này có k băng vô hạn về cả hai phía, mỗi băng có đầu đọc−ghi riêng. Mỗi quy tắc lúc này có dạng : q, x1, x2, , xk → y1, m1, y2, m2, , yk, mk, q’ với xi là ký tự nằm dưới đầu đọc-ghi, yi là ký tự thay thế cho xi, và mi∈{L, R} chỉ hướng (qua trái hoặc qua phải) của đầu đọc-ghi tương ứng tại băng thứ i, i=1 k. Giả sử T = là máy Turing có k băng như đã mô tả, ta mô phỏng T bởi một máy Turing T’ hoạt động trên bảng chữ : G = {a, b} ∪ Z, với Z = { | zi ∈ S ∪ {#} }, với a, b và # là những ký tự mới thêm. Ta ký hiệu pi là phép đơn ánh : pi( ) = zi. Một cấu hình (q, f1g1, f2g2, , fkgk) của T (đầu đọc−ghi của băng thứ i đặt tại * ký tự đầu tiên của câu gi, được mã hóa bởi câu awb, với w ∈ Z , sao cho với ∀i : pi(w) = fi#gi (phần không sử dụng của mỗi băng là các ký tự #). Lúc này, mỗi quy tắc của T dạng : q, x1, x2, , xk → y1, m1, y2, m2, , yk, mk, q’ sẽ được mô phỏng bởi một dãy các quy tắc của T’ thực hiện các phép tính sau : Xuất phát từ ký tự đánh dấu a, đầu đọc−ghi của T’ đọc các ký tự của w. Với mỗi thành phần fi#gi, máy ghi nhớ trong các trạng thái của nó, trạng thái q hiện hành của T và ký tự theo sau # là xi (ký tự đầu tiên của gi). Sau khi đã ghi nhớ hết các thành phần bên trái của quy tắc, T’ thực hiện các thay đổi tương ứng với thành phần bên phải của quy tắc này. T’ xem xét câu vào w để trên mỗi băng i : Nếu mi = R, thay đổi # và xi tương ứng bởi yi và #, nghĩa là #xi → yi#. Nếu mi = L và giả sử zi đứng trước # (ký tự cuối của fi), thay đổi zi, # và xi tương ứng bởi #, zi và yi, nghĩa là zi#xi → #ziyi. Cuối cùng, đầu đọc-ghi đặt tại ký tự đánh dấu a. Như đã chỉ ra ở trên, trong phép tính giữa các ký tự đánh dấu, các ký tự a và b có thể bị xê xịch trong quá trình tính toán do ký tự gây ra. Rõ ràng, máy Turing T’ một băng đã mô phỏng máy Turing T có k băng.
  52. Mô hình các máy RAM 49 IV.2.2. Các máy off−line và các máy có băng ra Máy Turing có nhiều băng có đặc tính sau : trên một băng nào đó, đầu đọc−ghi không làm thay đổi ký tự đã đọc. Nói cách khác, đầu đọc-ghi chỉ làm nhiệm vụ đọc không bao giờ ghi, gọi tắt là đầu đọc, không làm thay đổi nội dung câu vào trên băng. Do băng này chỉ dùng để lưu giữ và nhận biết dữ liệu vào, nên được gọi là băng vào của máy Turing. Một máy Turing k + 1 băng có một băng vào với đầu đọc chỉ di chuyển theo một chiều duy nhất (giả sử quy ước từ trái qua phải) như vừa mô tả được gọi là máy off−line. Rõ ràng, một máy Turing k băng có thể được mô phỏng bởi một máy off−line có k + 1 băng (chỉ cần sao chép dữ liệu trên băng vào lên một băng nào đó và sau đó chỉ làm việc với k băng còn lại). Tương tự, ta có thể xây dựng máy Turing nhiều băng có một băng ra có đặc tính như sau : trên một băng nào đó chọn làm băng ra, lúc đầu chỉ chứa toàn ký tự trắng #, đầu đọc−ghi trên băng này chỉ di chuyển theo một chiều duy nhất (từ trái qua phải). Nói cách khác, đầu đọc−ghi chỉ làm nhiệm vụ ghi, gọi tắt là đầu ghi, để ghi các ký tự kết quả lên các ô, sau khi ghi xong, đầu ghi không bao giờ quay lui trở lại để thay đổi nội dung đã ghi. Do đầu ghi chỉ di chuyển theo một chiều nên thực tế, băng ra chỉ vô hạn về một phía mà thôi. Máy Turing vừa có một băng vào và vừa có băng ra được biểu diễn như sau: u y v # # # . . . Băng vào . . . # # # f x g # # # . . . Băng làm việc q w # # # # . . . Băng ra Hình 3.9. Máy Turing có một băng vào và một băng ra Kiểu máy Turing có băng vào và băng ra được xem là kiểu cơ sở của các máy Turing. Ưu điểm của kiểu máy này là tính đồng dạng (similitude) với mô hình các máy RAM đã xét trước đây. IV.2.3. Các máy Turing không đơn định Chúng ta sẽ chỉ ra rằng nếu L là ngôn ngữ được nhận biết bởi một máy Turing không đơn định, thì L cũng được nhận biết bởi một máy Turing đơn định. Cho T là một máy Turing không đơn định. Từ T, người ta xây dựng một máy Turing T’ đơn định có ba băng : băng thứ nhất chứa dữ liệu vào, trên băng thứ hai, ta chép lại dữ liệu vào và tiến hành phép tính một cách lặp đi lặp lại. Còn
  53. 50 Lý thuyết tính toán trên băng thứ ba, ta liệt kê tất cả các dãy số thứ tự của các quy tắc đã dùng đến để tính toán của máy Turing T (trong các dãy số này có các dãy số thứ tự của các quy tắc được dùng cho các tính toán hợp thức). Phép tính thực hiện trên băng thứ hai như sau : áp dụng các quy tắc của T cho dữ liệu vào đã được chép từ băng một, nếu được, thì dãy quy tắc này được liệt kê trên băng thứ ba. Nếu phép tính này là hợp thức và dẫn đến các cấu hình dừng của T, thì người ta dừng tính toán. Nếu không, thay thế nội dung của băng hai bởi dữ liệu vào (đang được lưu giữ trên băng một) và tiến hành lại phép tính. Rõ ràng, nếu một câu được nhận biết bởi T, một tính toán dẫn đến dừng máy và liệt kê được các quy tắc đã dùng đến trên băng ba, thì phép tính của T’ cũng sẽ dừng. Nếu một câu không được nhận biết bởi T, thì các dãy quy tắc của T sẽ liên tục được liệt kê, không bao giờ dừng. Vậy T’ nhận biết cùng một ngôn ngữ với T. IV.2.4. Thu gọn một bảng chữ còn ba ký tự Cho máy Turing T = với || S || = n. Nếu n ≤ 1 + 2k người ta có thể sử dụng mã sau đây : c(#) = # và với ∀xi ∈ S, thì c(xi) là câu thứ i trên {0, 1} có độ dài k. Mô phỏng máy T bởi máy T’ = , trong đó : S’ = {#, 0, 1} Q’ là tập hợp các trạng thái (có 5 thành phần) với : − q ∈ Q, − w và w’ là các câu ∈ S’* có độ dài nhỏ hơn hoặc bằng k, − i ≤ k, i là một số nguyên, − m ∈ {L, R, ε} Một cấu hình (f, q, g) của máy T được mã hóa bởi cấu hình của máy T’ : (c (f), , c (g)) Còn P’ gồm ba loại quy tắc được định nghĩa như sau :
  54. Mô hình các máy RAM 51 z Các quy tắc nhận biết mã ký tự : , x → x, R, nếu |wx| , x → y, L, Khi nhận biết được mã wx của ký tự, mã này sẽ được thay thế bởi mã w’y của ký tự có mặt trong vế phải. Để bắt đầu thay thế, ta viết y, ký tự cuối của mã. Phần còn lại của mã này là w’ sẽ được ghi nhớ trong trạng thái (thành phần thứ ba). Cuối cùng, thành phần thứ tư là một bộ đếm được khởi động đến k − 1. z Các quy tắc di chuyển đầu đọc−ghi : Ta phải di chuyển đầu đọc-ghi theo chiều chỉ ra bởi m, được ghi nhớ trong thành phần thứ năm của trạng thái. Luôn luôn nếu quy tắc q, xi → xj, m, p ∈ P, và nếu wx có giá trị c(xi), thì sau khi tiến hành mọi sự thay thế cần thiết, T’ sẽ rơi vào trạng thái . z Các quy tắc di chuyển trạng thái mới : , z → z, m, Những sự thay đổi cần thiết được thực hiện nhờ các quy tắc : , y → x, L, và , x → x, m, với i > 0. Trạng thái đầu của T’ là ∈ Q’. Ví dụ 3.9 : Với bảng chữ gồm 9 ký tự {x1, x2, , x8, #}, ta sử dụng mã 3 ký tự sau : c(#) = #, c(x3) =010, c(x6) = 101, c(x1) = 000, c(x4) = 011, c(x7) = 110, c(x2) = 001, c(x5) = 100, c(x8) = 111 Chẳng hạn ta mô phỏng quy tắc (q, x4) → (x7, R, p) thành dãy các quy tắc :
  55. 52 Lý thuyết tính toán , 0 → 0, R, , 1 → 1, R, , 1 → 0, L, , , 1 → 1, L, , , 0 → 1, R, , , 1 → 1, R, , , 0 → 0, R, IV.2.5. Rút gọn một bảng chữ còn hai ký tự Cho T = với S = {#, 0, 1} Ta có thể sử dụng mã có cùng độ dài 5 như sau : c(#) = |#|||, c(0) = ||#||, c(1) = ||| # | Ta mô phỏng T bởi máy Turing T’ = trong đó : Q’ là tập hợp các trạng thái có dạng : như ở trên đã trình bày với một cấu hình : (f, q, g) được mã hóa bởi cấu hình : (c(f), , c(g)). P’ là tập hợp các quy tắc cho phép nhận biết mã của một ký tự (được đặt trong thành phần thứ hai của trạng thái), và thực hiện ba thay đổi (ký tự mới, di chuyển đầu đọc-ghi và trạng thái mới) tuân theo vế phải của quy tắc sao cho hai thành phần đầu tiên của trạng thái được dùng cho vế trái. Nếu tại một thời điểm tính toán, máy nhảy ra ngoài phần được mã hóa, thì khi đó sẽ gặp hai ký tự trắng # liên tiếp. Người ta sẽ thay thế năm ký tự # (5 là độ dài của mã) bởi mã của ký tự # trước khi tính toán trở lại. IV.3. Các máy Turing có băng vô hạn một phía Như đã biết, nhiều tác giả chỉ nghiên cứu các máy Turing có băng vô hạn về một phía. Thực ra, mô hình này tương đương với mô hình ta đã định nghĩa trong phần quản lý bộ nhớ (mục III.6).
  56. Mô hình các máy RAM 53 V. Máy Turing vạn năng Trong mục này, ta sẽ giải thích vì sao có thể mã hóa các máy Turing bởi một câu trên một bảng chữ đã cho, từ đó có thể đánh số các máy. Tiếp theo, ta sẽ chỉ ra sự tồn tại của một máy Turing, gọi là máy Turing vạn năng (universal Turing machine), có dữ liệu vào là số thứ tự (number) của một máy Turing T và một dữ liệu vào khác f cùng đạt một kết quả như T đối với f, dù T và f như thế nào. Không làm mất tính chất tổng quát, ta xét các máy Turing có Q = {q1, q2, , qn} và S có 9 ký tự kể cả ký tự trắng # được ký hiệu tổng quát S = {x1, x2, , x9}. Chẳng hạn bảng chữ Z = { #, 0, 1, q, x, L, R, ,, → }. Một quy tắc r ∈ P : qi, xj → xk, m, ql có thể được mã hóa bởi một câu trên Z như sau : c(r) = qi, xj, xk, m, ql trong đó, mỗi số nguyên i được biểu diễn dưới một dạng nhị phân _ i . Từ nay về sau, ta sẽ quy ước rằng mọi số nguyên đều ở dạng biểu diễn nhị phân, chú ý rằng một số nguyên có gạch dưới (_ i, j_ , k_ , l_ ) chỉ định biểu diễn nhị phân của số nguyên đó. Mã của một quy tắc sẽ là một câu của : R = q{0, 1}*, x{0,1}* → x{0, 1}*, M, q{0, 1}* với M = { L, R} Chú ý rằng ở đây R không sử dụng ký tự #. Chương trình của một máy Turing gồm các quy tắc r1, r2, , rs có thể được mã hóa bởi câu : c(r1) # c(r2) # # c(rs). Ta nhận thấy rằng mọi máy Turing có thể được mã hóa bởi một câu trên Z. Do đó các máy Turing là có thể đếm được. Từ đó, có thể gán cho mỗi máy Turing một con số, chẳng hạn hạng của nó trong một thứ tự phân cấp quy ước nào đó. Giả sử Ti là máy Turing thứ i và gi là hàm được tính bởi máy Turing thứ i này. Dễ dàng xây dựng được máy Turing TD sao cho với dữ liệu vào _ i, cho ra kết quả là câu dùng để mã hóa máy Turing thứ i như sau : Ta xây dựng một máy Turing hai băng. Băng thứ nhất chứa dữ liệu vào _.i . Trên băng thứ hai, ta liệt kê các câu của Z*, và với mỗi câu f đã liệt kê, ta kiểm tra nếu đó là mã của một máy Turing, nghĩa là nếu f thuộc về (R#)*R ? Nếu đúng như vậy, thì người ta giảm đi 1 số nguyên đang ở trên băng thứ nhất ( _ i ← i_ −1) và dừng lại nếu số nguyên nhận được là số không. Nếu không phải, tức là số nguyên chưa là số không, hoặc nếu câu vừa liệt kê không là mã của một máy Turing, thì người ta tiếp tục liệt kê các câu của Z*. Mệnh đề 3.6 :
  57. 54 Lý thuyết tính toán Có thể xây dựng được một máy Turing TU, gọi là máy Turing vạn năng, cho phép thực hiện một hàm fu có hai đối số i và f sao cho, với mọi số nguyên i và với mọi dữ liệu vào f của máy Turing thứ i (thực hiện hàm gi), fu thỏa mãn : fu(i_ #f) = gi (f) Chứng minh : Vì tồn tại máy Turing TD nhận dữ liệu vào _ i và cho kết quả là câu mã hóa máy Turing thứ i, nên chỉ cần chứng minh rằng tồn tại một máy Turing T’U thực hiện hàm f’u sao cho với mọi wi là mã của máy Turing thứ i, và với mọi f là dữ liệu vào, sẽ có f’u(wi#f) =gi(f). Ta sẽ chỉ ra cách xây dựng máy T’U nhờ hai máy Turing ba băng là TC và T”U : Máy thứ nhất TC thực hiện việc khởi động : dữ liệu vào wi#f được đọc và câu wi bị xóa khỏi băng thứ nhất để chép lại lên băng thứ hai. Băng thứ ba được ghi hằng q1_ . Khi kết thúc, máy TC ở cấu hình như sau : − Băng thứ nhất chứa câu f với đầu đọc-ghi nằm phía trái của f. − Băng thứ hai chứa câu wi với đầu đọc-ghi nằm phía trái của wi. − Băng thứ ba chứa câu q1_ với đầu đọc-ghi nằm phía trái của q1_. . Máy thứ hai T”U mô phỏng hoạt động của máy Ti, với chương trình wi của Ti được ghi trên băng thứ hai của T”U theo cách sau: Cấu hình uqnv của Ti được mã hóa bởi : − Câu uv trên băng thứ nhất với đầu đọc−ghi đặt tại ký tự đầu tiên của v. − Câu qn_ trên băng thứ ba. Giả sử rằng lúc đầu, người ta đã có cấu hình xuất phát của Ti đã được mã hóa. Một cách lặp đi lặp lại, ta thực hiện phép toán như sau : Đầu đọc của băng thứ hai đặt ở bên trái, lần lượt di chuyển qua bên phải của băng cho đến khi tìm thấy dãy #q. Lúc này máy so sánh số nguyên tiếp theo (số của trạng thái của vế trái của một quy tắc) với số nguyên của trên băng thứ ba (ở đó có mặt trạng thái hiện hành của máy được mô phỏng Ti), sau đó, so sánh ký tự nằm dưới đầu đọc ở băng thứ nhất với ký tự được mã hóa nằm trên băng thứ hai ở ngay sau dấu phẩy chỉ sự kết thúc của số thứ tự của trạng thái vừa được kiểm tra. Xảy ra hai trường hợp như sau : − Chúng không đồng thời bằng nhau, có nghĩa vế trái của một quy tắc không áp dụng được trong cấu hình được mã hóa lúc này. Ta tiếp tục di chuyển
  58. Mô hình các máy RAM 55 đầu đọc của băng thứ hai qua trái. Nếu đã qua tất cả chương trình mà không tìm thấy quy tắc áp dụng được, máy T”U dừng lại. − Chúng bằng nhau, có nghĩa đã tìm thấy vế trái của một quy tắc của Ti áp dụng được cho cấu hình được mã hóa lúc này. Chỉ còn việc thay đổi trên các băng thứ nhất và thứ ba tương ứng với việc áp dụng quy tắc này. Trên băng thứ hai, người ta đọc ký tự nào nằm ngay sau dấu mũi tên → dùng để thay thế cho ký tự nằm trên băng thứ nhất ở dưới đầu đọc-ghi , và người ta tiến hành thay thế. Tiếp theo, đọc sau dấu phẩy một ký tự L hoặc R chỉ chiều di chuyển nào của đầu đọc-ghi của băng thứ nhất sẽ được thực hiện, và tiến hành việc di chuyển này. Sau đó, đọc sau dấu phẩy tiếp theo trạng thái hiện hành mới nào của máy Turing được chọn để chép lại trên băng thứ ba tại vị trí cũ. Rõ ràng, máy T’u vừa mô tả đã mô phỏng được hoạt động của máy Turing có chương trình nằm trên băng thứ hai. Máy này dừng lại trên một dữ liệu vào f ở băng thứ nhất nếu và chỉ nếu máy mô phỏng T’U dừng trên f. Trong trưòng hợp này, những gì mà máy này có trên băng thứ nhất thì máy mô phỏng cũng có đúng như vậy. Từ đó, máy : T’U = TC next T”U là máy cần tìm kiếm. Chú ý rằng ta có thể dễ dàng tổ hợp máy TD đã đưa ra ở đầu chứng minh này với máy TC. Nếu ký hiệu T’C là máy tổ hợp nhận được , thì ta có : TU = T’C next T”U. Cũng chú ý thêm rằng máy Turing vạn năng TU mô phỏng họat động của mọi máy Turing trên một bảng chữ gồm có 9 ký tự. Đồng thời TU cũng là máy trên một bảng chữ có 9 ký tự. Rõ ràng, ta có thể nhận được cùng một lúc kết quả với bất kỳ kích thước nào (k ≥ 2) của bảng chữ. VI. Tồn tại các hàm không là T−tính được Trong mục này, nhờ kỹ thuật chéo (diagonization argument), ta sẽ chứng minh rằng tồn tại các hàm không là T−tính được. Mệnh đề 3.7 : Không tồn tại máy Turing tính được hàm th được định nghĩa như sau : với mọi cặp số nguyên i và j : th(i, j) = 1 nếu máy Turing số hiệu i dừng trên dữ liệu vào j, th(i, j) = 0 nếu không dừng. Ta nhận thấy phát biểu này thoả mãn cho mọi biểu diễn của các số nguyên trong một hệ đếm bất kỳ. Chứng minh :
  59. 56 Lý thuyết tính toán Bằng phản chứng, ta giả thiết rằng tồn tại một máy Turing T như vậy. Xuất phát từ T, ta có thể xây dựng một máy Turing T’ khác T thực hiện hàm g như sau : với mọi số nguyên i : g(i) = 1 nếu th(i, i) = 0, g(i) = không xác định nếu th(i, i) = 1 Máy Turing T’ được xây dựng như sau : TC(i) = (i, i) ∀ i ∈ Ν T (0) = 1, T’ = TC next T next TD D TD(i) không dừng ∀ i > 0 Ở đây, máy Turing TC nhận dữ liệu vào là một số nguyên i để trả về kết quả là cặp (i, i) và máy Turing TD cho kết quả là 1 với từ dữ liệu vào là 0 và không bao giờ dừng trên một dữ liệu vào nào khác 0. Máy Turing T’ vừa xây dựng trên đây quả thực đã thực hiện hàm g và giả sử T’ có số thứ tự là k, T’ = Tk. Xảy ra hai trường hợp như sau :  Giả sử hàm g(k) không xác định, điều này có nghĩa T’ không dừng trên dữ liệu k, điều này cũng có nghĩa máy T, đến lượt nó, có kết quả là 1 trên dữ liệu vào của cặp (k, k), tức là th(k, k) = 1. Vả lại th(k, k) = 1 nếu và chỉ nếu máy Turing có số hiệu k dừng trên dữ liệu vào k. Nhưng máy Turing có số hiệu k, chính là T’, không dừng trên dữ liệu vào k.  Giả sử hàm g(k) xác định và có giá trị 1, điều này có nghĩa rằng máy T dừng trên dữ liệu vào k và có kết quả 0 trên dữ liệu vào của cặp (k,k). Nghĩa là th(k, k) = 0. Vả lại th(k, k) = 0 nếu và chỉ nếu máy Turing có số hiệu k không dừng trên dữ liệu vào k. Tuy nhiên, máy Turing có số hiệu k chính là T’ lại dừng trên dữ liệu vào k. Trong cả hai trường hợp trên, ta đều đi đến mâu thuẫn, vậy không tồn tai máy Turing như đã giả thiết. QED Kết quả chứng minh rất quan trọng vì đã chỉ ra rằng không tồn tại cách nào để tính toán nhờ một máy Turing nếu một máy Turing T sẽ dừng hoặc không dừng trên một dữ liệu vào f. Từ đây, ta cũng có thể chứng minh được : Mệnh đề 3.8 : Tồn tại các hàm T−tính được bộ phận (partial) không thể mở rộng thành một hàm T−tính được nào khác. Chứng minh Định nghĩa hàm bộ phận g : Ν →/ Ν như sau: g(i) = TU(i, i) + 1 nếu TU(i, i) xác định g(i) không xác định nếu TU(i, i) không xác định
  60. Mô hình các máy RAM 57 Hàm g là T−tính được. Thật vậy, xuất phát từ máy Turing vạn năng TU, ta có thể dễ dàng xây dựng được một máy Turing thực thi hàm g này (chỉ việc thêm 1 vào kết quả). Hàm g này không thể được mở rộng thành một hàm toàn phần từ Ν vào Ν dẫu rằng T−tính được. Ta sẽ chỉ ra bằng cách dùng phản chứng. Giả sử rằng g’ là một hàm như vậy. Hàm g’ được thực hiện bởi một máy Turing T có số hiệu k, giả sử Tk. Vì rằng g’ là một hàm toàn phần, nên T có một tính toán dừng cho mọi dữ liệu vào. Chẳng hạn, với dữ liệu vào k, Tk dừng với một kết quả g’(k). Vả lại, vì Tk là máy số hiệu k dừng trên dữ liệu vào k, TU(k, k) là xác định, khi đó g(k) được xác định và có giá trị là TU(k, k)+1. Tuy nhiên, TU là một máy Turing vạn năng, và do đó TU(k, k) là kết quả của máy Turing số hiệu k trên dữ liệu vào k, giả sử là g’(k). Vậy ta có : g(k) = g’(k) + 1 Nhưng g’ là một mở rộng của g, do đó g’(k) + 1 = g’(k). Điều này mâu thuẫn.QED
  61. 58 Lý thuyết tính toán Bài tập 1. Cho bảng chữ S = {a, b, c}, f và g ∈ S*. Hãy viết chương trình của một máy Turing thực hiện các hàm sau : R − Hàm gương (miror function) hay hàm đảo ngược f → f : φ(x1 xn ) = xn x1. − Hàm chép f#g → f#g#g. − Hàm f#g → fg. − Hàm f → ff. − Hàm f → ffR. 2. Cho S = {a, b, c} với thứ tự phân cấp là a 0} Hãy chỉ ra rằng luôn luôn có thể giả thiết các phép tính dừng lại đều có độ dài chẵn (một cách tương ứng : có độ dài lẻ).
  62. CHƯƠNG 4 Luận đề Church «The greatest ocean of truth lay all undiscovered before me» Sir Isaac Newton I. Sự tương đương giữa các mô hình máy Turing và máy RAM Trong mục này, ta sẽ chỉ ra rằng một hàm là T-tính được nếu và chỉ nếu hàm đó là tính được nhờ một máy RAM (hàm tính được nhờ một máy RAM được gọi là R−tính được). I.1. Mọi hàm T-tính được cũng là R−tính được Ở đây, vấn đề là cần chỉ ra làm sao từ một chương trình P của một máy Turing giả thiết chỉ có một băng vô hạn về một chiều, có thể suy ra được chương trình của một máy RAM thỏa mãn cho mỗi bước tính toán của máy Turing. Cách xây dựng như sau : Nội dung các ô trên băng của máy Turing, được đánh số 0, 1, là nội dung tương ứng trong các thanh ghi R2, R3, của máy RAM. Số của thanh ghi tương ứng với ô nằm dưới đầu đọc ghi của máy Turing sẽ nằm trong thanh ghi R1 (lúc đầu nội dung của R1 là 2 do đầu đọc của máy Turing xuất phát từ ô đánh số 0). Với mỗi trạng thái qi của máy Turing, người ta đưa vào một phần của chương trình của máy RAM để mô phỏng các thao tác tính toán của máy Turing tại trạng thái này, tùy theo ký tự được đọc trên băng. Ví dụ, cho máy Turing trên bảng chữ kích thước 2 là S = {0, 1}. Giả sử nếu có hai quy tắc của P tương ứng với trạng thái qi ∈ Q là : qi, 1 → x, m, qr qi, 0 → y, m’, qs (trong đó, các di chuyển m và m’ có thể là L, R và qr, qs ∈ Q), thì một đoạn chương trình của máy RAM tương ứng sẽ là : ki : LOAD I: R1 JZERO k’i LOAD A:x STORE I:R1 INCR R1 (hoặc, tùy theo m :DECR R1) JUMP Kr k’i: LOAD A:y STORE I:R1 INCR R1 (hoặc tùy theo m’ : DECR R1) JUMP ks PGS. TS. PHAN HUY KHÁNH biên soạn 59
  63. 60 Lý thuyết tính toán Nếu một quy tắc tương ứng với một trạng thái qi không tồn tại, nghĩa là nếu một cặp (qi, x) không là vế trái của một quy tắc nào, thì máy Turing dừng. Lúc đó, nhom lệnh tương ứng cuả máy RAM sẽ là lệnh dừng Halt. Rõ ràng, việc thực hiện của nhóm lệnh này mô phỏng một bước tính toán của máy Turing. Các trạng thái của máy Turing tương ứng hoàn toàn với các nhãn ki của chương trình RAM. Khi viết hết các đoạn chương trình (tương ứng với các trạng thái khác nhau của máy Turing), người ta đã đặt chúng kề sát nhau, và có thể thay thế các nhãn ki bởi các con số. Như vậy, việc thực hiện toàn bộ chương trình đã mô phỏng việc tính toán đầy đủ của máy Turing. I.2. Mọi hàm R−tính được cũng là T−tính được Ở đây, ta cần chỉ ra rằng, cho trước chương trình của một máy RAM, với giả thiết máy RAM này rất thô sơ mà không làm mất tính tổng quát, ta có thể xây dựng được một máy Turing cho phép kiểm chứng từng bước tính toán của máy RAM. Cách xây dựng như sau : Nếu x0, x1, là nội dung tương ứng của các thanh ghi R0, R1, , thì băng của máy Turing chứa : 0 : x0 1 : x1 j : xj Ở đây, và : là hai ký tự mới được thêm vào. I.2.1. Tăng nội dung thanh ghi n lên 1 Với mọi lệnh của chương trình của máy RAM có dạng : i: I xây dựng một máy Turing Ti tiêu chuẩn hóa (normalized), có qi là trạng thái xuất phát và qi + 1 là trạng thái dừng. Máy Ti hoạt động như sau : Ti di chuyển đầu đọc−ghi trên băng từ trái qua phải và so sánh số đứng sau mỗi ký tự với n. Nếu là bằng nhau thì Ti tăng số nguyên tiếp theo sau ký tự : lên 1 (increment) bằng cách dời theo nhu cầu những gì theo sau qua bên phải, rồi dừng. I.2.2. Giảm 1 nội dung thanh ghi n Tương tự như vậy, với mỗi lệnh của chương trình của máy RAM có dạng : i: D xây dựng một máy Turing Ti tiêu chuẩn hóa có qi là trạng thái xuất phát và qi + 1 là trạng thái dừng. Máy Ti hoạt động như sau : Ti di chuyển đầu đọc−ghi trên băng từ trái qua phải và so sánh số đứng sau mỗi ký tự với n. Nếu là bằng nhau, thì Ti giảm một (decrement) số nguyên tiếp theo và dừng. I.2.3. Đưa nội dung thanh ghi n về 0 Với mỗi lệnh của chương trình của máy RAM có dạng : i: Z