lý thuyết tính toán

Chia sẻ: Phan Van611 Phanvan | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

113
lượt xem 93
download

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

Tham khảo tài liệu 'lý thuyết tính toán', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: lý thuyết tính toán

ĐẠI HỌC ĐÀ NẴNG T R ƯỜ NG Đ Ạ I H Ọ C BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN LÝ THUYẾT TÍNH TOÁN PGS.TS. PHAN HUY KHÁNH ĐÀ NẴNG 1999
2 Lý thuyết tính toán III.7. Một số máy Turing thông dụng ..................................................................40 III.6.1. Sao chép .....................................................................................................40 MỤC LỤC 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 CHƯƠNG 1 NHẬP MÔN LÝ THUYẾT TÍNH TOÁN ........................................... 1 III.7. Các hàm T-tính được phức tạp hơn............................................................42 I. CÁC ĐốI TƯợNG ĐƯợC Xử LÝ TRONG TIN HọC ......................................................... 1 III.8. Nhận xét......................................................................................................43 II. CÁC MÁY (MACHINES)........................................................................................ 2 IV. CÁC BIếN THế KHÁC CủA MÔ HÌNH MÁY TURING ..............................................46 II.1. Khía cạnh chức năng (functional look)........................................................ 2 IV.1. Mô phỏng một máy Turing bởi một máy khác............................................46 II.2. Khía cạnh cấu trúc (structural look)............................................................ 3 IV.2. Các biến thể của máy Turing .....................................................................48 III. MÔ HÌNH TÍNH TOÁN .......................................................................................... 4 IV.2.1. Máy Turing có k băng ................................................................................48 IV. ĐịNH NGHĨA BÀI TOÁN........................................................................................ 5 Các máy off−line và các máy có băng ra ...................................................49 IV.2.2. IV.2.3. Các máy Turing không đơn định................................................................49 CHƯƠNG 2 MÔ HÌNH CÁC MÁY RAM ............................................................... 9 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 I. CÁC MÁY RAM...................................................................................................... 9 IV.3. Các máy Turing có băng vô hạn một phía .................................................52 II. MÔ PHỎNG MỘT MÁY BỞI MỘT MÁY KHÁC........................................ 16 V. MÁY TURING VạN NĂNG.......................................................................................53 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ự VI. TồN TạI CAC HAM KHONG LA T TINH DƯợC ....................................................55 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 CHƯƠNG 4 LUẬN ĐỀ CHURCH..........................................................................59 III.3. Thu gọn tập hợp các lệnh số học................................................................ 20 I. Sự TƯƠNG ĐƯƠNG GIữA CÁC MÔ HÌNH MÁY TURING VÀ MÁY RAM ....................59 IV. MÁY RAM VạN NĂNG ...................................................................................... 22 Mọi hàm T-tính được cũng là R−tính được................................................59 I.1. Mọi hàm R−tính được cũng là T−tính được ...............................................60 CHƯƠNG 3 MÔ HÌNH CÁC MÁY TURING ....................................................... 25 I.2. I.2.1. Tăng nội dung thanh ghi n lên 1.................................................................60 I. MÔ Tả VÀ HOạT ĐộNG CủA MÁY TURING .............................................................. 25 I.2.2. Giảm 1 nội dung thanh ghi n ......................................................................60 I.1. Mô tả máy Turing....................................................................................... 25 I.2.3. Đưa nội dung thanh ghi n về 0 ...................................................................60 I.2. Hoạt động của máy Turing ........................................................................ 26 I.2.4. Nhảy theo nội dung thanh ghi n .................................................................61 I.3. Cấu hình xuất phát của máy Turing........................................................... 29 I.2.5. Hoán vị nội dung hai thanh ghi n và m ......................................................61 I.4. Máy Turing đơn định.................................................................................. 29 I.3. Sự khác nhau giữa máy Turing và máy RAM.............................................61 II. CAC HAM T−TINH DƯợC ....................................................................................... 30 II. MÔ HÌNH CÁC HÀM Đệ QUY ..................................................................................62 LớP CÁC HÀM T−TÍNH ĐƯợC ............................................................................. 32 III. II.1. Các hàm đệ quy nguyên thủy (primitive recursive functions)....................62 III.1. Một số hàm sơ cấp...................................................................................... 32 II.1.1. Xây dựng các hàm sơ cấp...........................................................................62 III.1.1. Các hàm hằng (constant functions)............................................................ 32 II.1.2. Sơ đồ hợp thành tổng quát..........................................................................62 III.1.2. Các hàm chiếu (projection functions) ........................................................ 33 II.1.3. Sơ đồ đệ quy đơn (simple recurrence)........................................................63 III.2. Các hàm kế tiếp (successor functions) ....................................................... 33 II.1.4. Sơ đồ đệ quy đồng thời ..............................................................................63 Các hàm kế trước (predecessor functions).......................................................... 34 II.1.5. Các hàm được định nghĩa bởi case.............................................................65 III.3. II.2. Các hàm đệ quy ..........................................................................................67 III.4. Sự hợp thành (composition) ....................................................................... 34 II.2.1. Sơ đồ tối thiểu ............................................................................................67 III.3.1. Các máy được tiêu chuẩn hóa .................................................................... 35 II.2.2. Các hàm đệ quy trừu tượng (abstract recursive functions) ........................68 III.3.2. Các máy Turing được chuẩn hóa ............................................................... 36 II.2.3. Một số ví dụ ................................................................................................68 III.3.3. Tổ hợp các máy Turing.............................................................................. 36 Các hàm đệ quy đều T−tính được...............................................................70 III.5. Lập trình trên ngôn ngữ bậc cao máy Turing ............................................ 37 II.3. III.4.1. Cấu trúc if then else và cấu trúc rẽ nhiều nhánh ........................................ 37 II.3.1. Sơ đồ hợp thành tổng quát..........................................................................70 III.4.2. Cấu trúc while ............................................................................................ 38 II.3.2. Sơ đồ đệ quy đơn........................................................................................70 III.6. Quản lý bộ nhớ ........................................................................................... 39 II.3.3. Sơ đồ tối thiểu ............................................................................................71 Mọi hàm T−tính được là đệ quy bộ phận ...................................................71 III.5.1. Máy Turing chuyển một ô qua phải........................................................... 39 II.4. III.5.2. Máy Turing chỉ sử dụng phần băng bên phải III. LUậN Đề CHURCH ..............................................................................................73 kể từ vị trí đầu tiên của đầu đọc-ghi........................................................... 39 PGS.TS. PHAN HUY KHÁNH biên soạn 1
Nhập môn lý thuyết tính toán 3 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ớ .............................................................. 93 II. CÁC LớP CủA Độ PHứC TạP ..................................................................................... 95 II.1. Hiện tượng nén........................................................................................... 96 Các họ P, NP và P−bộ nhớ (P−space)..................................................... 97 II.2. − III. RUT GọN DA THứC VA CAC BAI TOAN NP DầY Dủ .......................................... 98 III.1. Khái niệm ................................................................................................... 98 III.2. Các bài toán cổ điển................................................................................... 99 III.3. Ví dụ về rút gọn kiểu đa thức ................................................................... 100
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 CHƯƠNG 1 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 : N h ậ p môn lý thuy ế t tính toán e1 (Introduction to the theory of computation) It’s not bad being the small fish. a2 b3 c4 I. Các đối tượng được xử lý trong Tin học aa 5 ab 6 ac 7 ba 8 bb 9 bc 10 ca 11 cb 12 cc 13 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 aaa 14 aab 15 aac 16 . . . đượ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ệ Hình 1.1. Thứ tự phân cấp trong S* đế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 II. Các máy (machines) 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. II.1. Khía cạnh chức năng (functional look) Người ta giả thiết rằng các đối tượng được xử lý là những câu (word, hay Một máy (machine) được biểu diễn một cách hệ thống như sau : 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. Dữ liệu vào Dữ liệu ra Định nghĩa 1.1 : Máy 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 Hình 1.2. Khía cạnh chức năng của một máy ký hiệu ||S||, hay |S|, nếu không sợ nhầm lẫn. Ở 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, 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 người ta nhận được kết quả (result). bảng chữ S được viết liên tiếp nhau. 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 Độ 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ó 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 trong câu. Câu rỗng (empty word), được ký hiệu là e (ω hoặc e, hoặc l), là 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 câu có độ dài không, tức không chứa ký tự nào. (machine type) tùy theo bản chất của tập hợp kết quả này như sau : Ghép (concatenation) của hai câu là đặt kế tiếp hai câu đã cho (trên cùng 1. Nếu tập hợp chỉ có hai phần tử { không, có } hay {0, 1}, máy sẽ chia dữ 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ý liệu vào thành ba phần tùy theo kết quả : 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 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 S*. Người ta nói S*là một cấu trúc đồng đẳng (nonoide), mà phần tử trung hòa quả là có (đúng, true), hoặc không (sai, false). (neutral element) chính là câu rỗng. Tập hợp các câu mà máy đưa ra một kết quả khác. Cho trước một bảng chữ S, người ta định nghĩa một quan hệ có thứ tự toàn 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. 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
4 Lý thuyết tính toán 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ù III. Mô hình tính toán 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. 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 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 đị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 ở bảng chữ G nào đó. chương trình. 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 : 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 f : S * → G* 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 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 hiện (execution) trên máy. 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*, 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 thì f được gọi là hàm toàn phần (partial function). Người ta gọi đó là máy 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 tính toán (computation machine) hay máy tính. nghĩa bởi dữ liệu vào của chương trì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 Mô hình + Chương trình = Máy 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). 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, 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ó vấn đề đặt ra là làm sao để có thể biết : 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 #, − lớp ngôn ngữ đoán nhận được (recognized), được gọi là T−nhận biết được, tạo thành một ngôn ngữ. Người ta gọi ngôn ngữ này là liệt kê được hoặc (enumerated) bởi máy. − lớp các hàm tính được (computable), được gọi là T−tính được, hoặc II.2. Khía cạnh cấu trúc (structural look) − 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 ? Ở đâ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ê : Hai mô hình tính toán được đưa ra so sánh với nhau : một mô hình T1 được Thực hiện các phép toán sơ cấp (elementary operation) trong một khoảng nói là mạnh hơn so với một mô hình T2 nếu : 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, − mọi ngôn ngữ T2−nhận biết được cũng là T1−nhận biết được, hoặ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. − mọi hàm T2-tính được cũng là T1−tính được, hoặc 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 − mọi ngôn ngữ T2-liệt kê được cũng là T1-liệt kê được. 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 Hai mô hình được gọi là tương đương (equivalent) nếu mỗi mô hình mạnh tính toán (computation) của máy. 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.
6 Lý thuyết tính toán Nhập môn lý thuyết tính toán 5 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 IV. Định nghĩa bài toán 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 Trong Tin học lý thuyết, định nghĩa về bài toán (problem) có vai trò đặ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. 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ớ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 vực Toán học hoặc hiểu theo nghĩa thông dụng. 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 Định nghĩa 1.2 : bài toán P với một ngôn ngữ, gọi là ngôn ngữ đặc trưng (characteristic language) Một bài toán là : 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 − 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 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à hay vô hạn đếm được. ngôn ngữ đặc trưng của bài toán P. − 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, 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 hoặc có thể là sai tùy theo phần tử được chọn. 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 Sau đây là một số ví dụ : 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 : Bài toán 1’ : Dữ liệu: Một số nguyên viết trong hệ 10. Dữ liệu : Cho 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 ? Câu hỏi : Số nguyên này không phải là một số nguyên tố ? Bài toán 2 : 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 Dữ liệu : Một số nguyên viết trong hệ 10. 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 : 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 Đị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 Bài toán 3 : 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, 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. trong một khoảng thời gian hữu hạn, nếu câu này thuộc về LP hay LCP. Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Người ta phân lớp các bài toán tùy theo độ khó (difficulty) để đưa ra câu trả Bài toán 4 : lời từ dữ liệu vào đã cho. 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 Một bài toán là tầm thường (trivial) nếu LP = ∅ hoặc nếu LCP = ∅. và các cung, trong đó mỗi đỉnh được biểu diễn bởi một số nguyên 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 trong hệ 10. 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, 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 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. đồ thị, mỗi đỉnh đi qua đúng một lần) trong đồ thị đã cho không ? Ví dụ, bài toán 2 là tầm thường. Bài toán 5 : 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 : Dữ liệu : Một biểu thức chính quy (regular expression) được xây dựng trên 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 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 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 các phép hoặc, phép ghép tiếp, phép * và lấy bù). 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. 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 ? Đố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 Bài toán 6 : 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 Dữ liệu : Một dãy hữu hạn các cặp câu (u1, v1), (u2, v2)..., (uk, vk). 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 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 toán tương ứng Post (Post’s correspondence problem). ui1 ui2... uin = vi1 vi2... vin ?
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.
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 CHƯƠNG 2 ... ... ... ... Các thanh ghi j Ri M ô hình các máy RAM ... ... ... ... p Rn i « I like the dreams of the future better than the history of the past » Thanh Jefferson đếm lệnh y1 y2 y3 I. Các máy RAM ... Băng ra 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ữ Hình 2.1 Sơ đồ một máy RAM assembler. Máy RAM có các thành phần đặc trưng chung như sau : 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 Một băng vào, hay dải vào (input tape) được chia thành nhiều ô (square hay thành từ 2 thành phần : mã lệnh (operation code) và toán hạng (operand) : 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 Mã lệnh Toán hạng qua phải. 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 : Một băng ra (output tape) cũng chia ra thành nhiều ô liên tiếp nhau và một Nhóm lệnh gán : đầu ghi (write head) có thể ghi mỗi lần lên một ô và tiến từ trái qua phải. LOAD Operand Người ta nói rằng đầu đọc (hoặc ghi) được đặt trên (tại) một ô và di chuyển STORE Operand 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. Nhóm lệnh số học : Máy RAM còn có các thành phần bên trong như sau : INCR Operand Các thanh ghi (registers) là các phần tử nhớ được đánh số thứ tự, số lượng DECR Operand các thanh ghi có thể lớn tuỳ ý. Mỗi thanh ghi có thể lưu giữ một số nguyên. AD Operand Các thanh ghi lần lượt được đặt tên là R0, R1, R2, ... , Rn... SUB Operand MULT Operand Chỉ số i, i = 0, 1, 2, ..., được gọi là địa chỉ (address) của mỗi thanh ghi (hay DIV Operand của bộ nhớ). Riêng R0 là một thanh ghi đặc biệt, được gọi là thanh tổng (ACC − 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) : accumulator) hay thanh tích luỹ. JUMP Label 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 JGTZ Label dưới dạng một dãy các lệnh sơ cấp (primary instructions) không bị thay đổi JZERO Label trong quá trình chạy (thực hiện). Mỗi lệnh được lưu trữ trong một đơn vị HALT nhớ, được đánh số tương ứng với số thứ tự hay nhãn của lệnh (label). Nhóm lệnh vào − ra : 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. READ Operand WRITE Operand 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
12 Lý thuyết tính toán 11 Mô hình các máy RAM Theo nguyên tắc địa chỉ, phần toán hạng là địa chỉ (address) của toán hạng Lệnh Ý nghĩa 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 ACC ← LOAD n  kiểu sau : ACC ← giá trị n LOAD A: n  ACC ← Kiểu địa chỉ Ý nghĩa LOAD I: n  n ← Số nguyên n Chỉ nội dung của thanh ghi thứ n (Rn). STORE n  ← STORE I: n A: n (A = Absolute) toán hạng chính là số nguyên n đó.  n ← + 1 INCR n I: n (I = Indirection) toán hạng là nội dung của thanh ghi có số thứ  n ← - 1 DECR n tự là nội dung của thanh ghi Rn. Đây là kiểu lệnh gián tiếp.  ACC ← + ADD n  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 ACC ← − SUB n  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ữ ACC ← × MULT n  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 ACC ← / DIV n  đơn giản cách trình bày. CO ← n JUMP n  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 CO ← n nếu ≥ 0 JGTZ n  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 CO ← n nếu = 0 JZERO 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. Cả hai trường hợp trên, nếu không thỏa mãn, CO ← + 1 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  HALT Dừng máy 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  n ← số nguyên trong ô dưới đầu đọc của băng, READ n 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.  đầu đọc dịch một ô qua phải 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  WRITE n Nội dung được ghi vào ô dưới đầu ghi, địa chỉ của lệnh nhảy này.  đầu ghi dịch qua phải một ô.  Sau đây sử dụng một số quy ước để giải thích cách thực hiện lệnh. Ví dụ 2.1 : Chương trình RAM sau đây đánh giá trị n! ← dấu gán ; quy ước số nguyên i nằm bên trái dấu gán chỉ thanh ghi READ 0 đọc một giá nguyên n vào ACC 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ố JZERO 10 nếu n = 0, nhảy đến nhãn 10, nguyên i đó. nếu không, thực hiện lệnh tiếp theo R1 ← STORE 1 Chỉ nội dung của thanh ghi Ri. R2 ← 4: STORE 2 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. R 1 ← < R1 > − 1 DECR 1 ACC Chỉ thanh ghi R0. ACC ← LOAD 1 CO Chỉ thanh đếm lệnh. JZERO 12 nếu = 0 nhảy đến 12 Nội dung của CO. ACC ← * MULT 2 Sau đây là bảng các lệnh RAM và ý nghĩa sử dụng của chúng. CO ← 4 JUMP 4 ACC ← 1 10: LOAD A: 1 R2 ← STORE 2 12 : WRITE 2 ghi ra HALT Dừng máy
14 Lý thuyết tính toán 13 Mô hình các máy RAM Dạng hàm f : S* → S* Ví dụ 2.2 : Chương trình RAM tính nn R1 ← số nguyên trên ô của băng vào READ 1 Giả sử chương trình P luôn đọc được từ băng vào n số nguyên x1, x2, ..., xn và ACC ← LOAD 1 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. nếu ≥ 0, nhảy đều 6 JGTZ 6 WRITE A:0 in ra 0 Dạng ngôn ngữ L ⊆ S* JUMP 22 về lệnh dừng 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ứ ACC ← 6 : LOAD 1 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 R2 ← STORE 2 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 ACC ← LOAD 1 một ký tự kết quả và dừng. ACC ← − 1 DECR 0 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 R3 ← 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 STORE 3 băng ra, hoặc bị hóc (crash), hoặc không bao giờ dừng. ACC ← 11 : LOAD 3 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 nếu ≥ 0, nhảy đến 14 JGTZ 14 tinh điện tử hiện nay là ở chỗ : nhảy đến 21 nếu < 0 JUMP 21 1) Ta đã giả thiết có thể sử dụng một số lớn tùy ý các thanh ghi, tuy nhiên ACC ← 14: LOAD 2 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 ACC ← * MULT 1 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 đó R2 ← STORE 2 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. ACC ← LOAD 3 ACC ← − 1 DECR 0 2) Ta đã giả thiết rằng chương trình có sẵn trong bộ nhớ RAM chỉ có thể đọc R3 ← STORE 3 (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. JUMP 11 nhảy đến 11 21: WRITE 2 in ra nội dung Sự khác nhau chi tiết như sau : 22: HALT dừng 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 Ta có thể viết đoạn trình Pascal minh họa trình RAM như sau : giảm đáng kể tập hợp các lệnh sơ cấp. begin 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ộ read (R1) 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ố), if R1 < 0 then write (R0) tương tự như vậy đối với các kết quả ra. else begin R2:= R1 ; R3:= R1 − 1 ; 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 while R3 > 0 do begin R2:= R2*R1 ; R3:= R3–1 end ; 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ỉ write (R2) 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 end thành biểu diễn nhị phân để đặt trong các thanh ghi, sau đó chuyển đổi kết quả end ; đ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. 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 Đ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 băng ra. Đây là ánh xạ bộ phận (partial map) vì một số ánh xạ có thể không xác 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 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 nhớ, hay từ nhớ (memory word). Chú ý rằng nếu chỉ làm việc với cách biểu diễn dừng. 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. 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ữ.
16 Lý thuyết tính toán 15 Mô hình các máy RAM Cuối cùng, sự khác nhau ở điếm (2) đưa đến việc xây dựng một mô hình II. Mô phỏng một máy bởi một máy khác 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 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 : with Stored Program). Sự khác nhau cơ bản với các máy RAM là vùng nhớ lưu 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ô 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. 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ả. Máy RASP 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 Để thuận tiện cách trình bày, ta quy ước rằng mỗi lệnh RASP chiếm chỗ hai 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 thanh ghi liên tiếp nhau : thanh ghi đầu chứa trường toán hạng, thanh ghi thứ hai M nếu : chứa trường địa chỉ của lệnh. Tồn tại một ánh xạ I từ N vào N mà biến 0 thành 0. x1 x2 ... xn 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 Băng vào 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 R0 Thanh tổng thanh ghi R của M sau khi thực hiện các lệnh tương ứng của P. R1 Ví dụ 2.3 : Dịch chuyển các địa chỉ thanh ghi. R2 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 Chương trình 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 Rp trình Pk mô phỏng trình P với ánh xạ I xác định bởi : i I (0) = 0 Thanh đếm lệnh ... Các thanh ghi khác 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 y1 y2 y3 liên quan (đặt sau I) để thực hiện kiểu gián tiếp. ... Băng ra Các máy RASP cũng có thể được mô phỏng và có thể xử lý kiểu lệnh gián Hình 2.2 Sơ đồ một máy RASP tiếp. Trong máy RASP, thanh tổng luôn luôn là R0, thanh ghi R1 dùng để lưu giữ Dịch chuyển các địa chỉ thanh ghi của RASP trung gian nội dung của thanh tổng. Những gì mà một máy RAM làm được thì một máy RASP cũng có thể được 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 làm được. Thật vậy, nếu chương trình của RASP được lưu giữ trong các thanh RASP, và các thanh ghi tiếp theo, từ p + 1 trở đi, là các thanh ghi còn trống. 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. 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. 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.
18 Lý thuyết tính toán 17 Mô hình các máy RAM 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ố Ví dụ 2.4 : Dịch chuyển một trình RASP có một lệnh dạng gián tiếp : lệnh kiểu gián tiếp của chương trình. ⎧1 + a nãúu a ≤ b ⎪ Tính in ⎨ ⎪1 + b nãúu a > b 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 Chương trình RASP xuất phát P : sau khi dịch chuyển thành P’ : 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 2 READ READ R27 ← a 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 3 27 37 đầ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 4 READ READ R27 ← b R1 : 5 28 38 6 LOAD A: LOAD A: ACC ← 50 STORE 7 27 37 R1 ← 51 1 8 STORE STORE R26 ← 9 26 36 Phần này là Lệnh thứ hai nạp vào thanh tổng nội dung của thanh ghi n + p’ − p (tương ứng 10 LOAD LOAD dịch chuyển của P ACC ← với thanh ghi n trong chương trình xuất phát) : với ánh xạ : 11 28 38 52 LOAD I(r) = r+p’-p = r+10 12 SUB ACC ← - SUB ACC ← + (p’ − p) 13 27 37 53 n + p’- p 14 JGTZ JGTZ OC ← 18, if > 0 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 15 18 18 chứa địa chỉ của thanh ghi chứa giá trị cần nhân : 16 INCR INCR R26 ← < R26> + 1 17 26 36 54 ADD A: 18 LOAD A: LOAD A: ACC ← 1 ACC ← + (p’ − p) 55 p’- p 19 1 1 20 ADD I: ACC ← + STORE 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 R1 ← 21 26 1 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 đó) : 22 WRITE LOAD ACC ← In ra 56 STORE 23 0 36 R61 ← 57 61 ACC ← + 24 HALT ADD A: Dừng p 25 0 10 10 Lệnh thứ năm khôi phục nội dung lúc đầu của thanh tổng : R31 ← : số P+1 26 27 / 28 Nội dung 27, hoặc 28 STORE 58 LOAD 27 a Chứa giá trị a 31 x ACC ← 59 1 q 28 b Chứa giá trị b LOAD ACC ← 29 1 Cuối cùng, thực hiện phép nhân : 30 ADD ACC← + 60 MULT Nội dung thay đổi : số x 31 0 ACC ← * → 61 x 32 WRITE Ở đâ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 33 0 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ị 34 HALT 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ư P’ 35 0 P’+1 36 37 / 38 Nội dung 37, hoặc 38 vậy, khi mô phỏng trình P thành P’ đặt trong các thanh ghi RASP, P’ đã bị thay 37 a Chứa giá trị a đổi khi thực hiện nó. 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
20 Lý thuyết tính toán 19 Mô hình các máy RAM III. Một mô hình thô sơ kiểu RAM 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 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 (zero) JZERO và lệnh dừng máy HALP. nhỏ. Đặc biệt, ta sẽ chỉ ra rằng có thể xử lý ký tự và xử lý các số nguyên. Lệnh JUMP n sẽ sử dụng thanh ghi R1 làm trung gian để lưu giữ nội dung của 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 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 : 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à độ R1 ← STORE 1 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). ← R1 LOAD 1 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 sau đó thay thế lệnh nhảy bởi : 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. R1 ← STORE 1 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 ← 0 LOAD A: 0 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 JZERO n’ goto n’, if = 0 phải tối ưu. Trong đó n’ là nhãn của lệnh STORE 1 đặt trước ngay lệnh có nhãn n trong III.1. Mô phỏng các phép toán trên chuỗi ký tự bởi các máy xuất phát. phép toán trên các số nguyên 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). 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 III.3. Thu gọn tập hợp các lệnh số học 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ố 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à nguyên nhờ thực hiện các phép toán trên các số nguyên. INCR (tăng 1) và DECR (giảm 1). 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 Chẳng hạn, lệnh nhân MULT n sẽ được chuyển đổi bằng cách thêm lần 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 : 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 : ~ × 198 28 7 198 7 + STORE 1 Hình 2.4 Ghép hai số nguyên LOAD 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ố STORE 2 nguyên bởi các chuỗi ký tự, đó là các phép tính sơ cấp. LOAD A: 0 STORE 3 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 return: LOAD 2 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 JZERO lab toán được thực thi trên các ký tự. 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 ...
22 Lý thuyết tính toán 21 Mô hình các máy RAM 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 IV. Máy RAM vạn năng thô sơ, chỉ có tập hợp các lệnh tối thiểu sau : Lệnh Ý nghĩa 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ể I Tăng thêm 1 nội dung của thanh ghi n 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ô D Giảm bớt 1 nội dung của thanh ghi n phỏng như sau : lúc đầu, người ta đọc chương trình của máy RASP, chương trình Z Đặt nội dung của thanh ghi n về 0 này được lưu giữ trong các thanh ghi từ 4 đến p của máy RAM. Thanh ghi R1 S Hoán đổi nội dung các thanh ghi n và m dùng làm địa chỉ gián tiếp ; thanh ghi R2 dùng để mô phỏng thanh đếm lệnh của J (i, j) Nếu nội dung của thanh ghi n là 0, nhảy đến lệnh có nhãn i, RASP. Thanh ghi R3 dùng để mô phỏng thanh tổng của RASP. Sau đó, thực hiện nếu không nhảy đến lệnh có nhãn j 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ô HALT Dừng máy phỏng một lệnh của RASP. 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. Giả thiết rằng thanh ghi R2 chứa địa chỉ của thanh ghi đầu tiên trong hai thanh 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à . ghi chứa lệnh cần mô phỏng (bắt đầu từ 4). Vòng lặp như sau : Loop: Ví dụ 2.5 : − Nội dung của thanh ghi của R2 được gán cho thanh tổng : 1: J (5, 2) 2: I LOAD I: 2 3: D − 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 4: J (1, 1) đế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 5: HALT 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 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 dương JGTZ và t là nhãn của dãy phép toán mô phỏng JGTZ : khi hai thanh ghi này chứa lần lượt n + p và 0. ... 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
24 Lý thuyết tính toán 23 Mô hình các máy RAM − 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 : Bài tập INCR 2 − Quay lại từ đầu vòng lặp bởi lệnh nhảy : 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. JUMP loop 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 Tương tự, từ nhãn t, thực hiện mô phỏng phép toán nhảy dương JGTZ : số nguyên cho trước, với n lẻ. − Kiểm tra nội dung thanh tổng của RASP, nếu dương thì nhảy : 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. LOAD 3 JGTZ lab 4. Viết chương trình của một máy RAM thô sơ tính : − 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 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 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 : 5. Chứng tỏ rằng có thể rút lệnh hoán đổi : S trong máy RAM thô sơ. INCR 2 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, INCR 2 trong một máy RASP và trong một máy RAM thô sơ. JUMPloop 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ô − Nếu kết quả dương, từ nhãn lab, tăng nội dung thanh ghi R2 lên 1 để R2 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ơ. chứa địa chỉ của thanh ghi chứa toán hạng : 8. Viết chương trình của một máy RAM vạn nă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 JUMPloop 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).
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. CHƯƠNG 3 Một chương trình P là một tập hợp con của Q×S´S´M´Q, trong đó, M ô hình các máy Turing 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 ô. « If the human brain was so simple that we could understand it, Mỗi phần tử (q, x, y, m, p) của P là một quy tắc, được viết như sau : then we would be so simple that we could not » q, x → y, m, p (L. Watson) với x và y ∈ S, q và p ∈ Q, m ∈ M, trong đó : Mô hình các máy Turing (Turing machines model) là một trong trong những 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. 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, 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 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 áp dụng quy tắc, theo một thể thức sẽ trình bày dưới đây. 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 Người ta thường biểu diễn một quy tắc của P dưới dạng sơ đồ như sau : 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. x | y, m q p I. Mô tả và hoạt động của máy Turing Hình 3.1. Biểu diễn dạng sơ đồ một quy tắc của máy Turing I.1. Mô tả máy Turing Như vậy, một máy Turing là một bộ ba T = được đặc tả một cách Một máy Turing gồm : 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 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 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. 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ự) Mô hình được chọn định nghĩa ở đây cũng có những điều bất tiện. Đó là cách này tạo ra bảng chữ của máy Turing, đưọc định nghĩa đồng thời với máy 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 Turing. 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 đầu đọc−ghi để đọc hay ghi (làm thay đổi) nội dung từng ô của băng, 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, 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 gọi là phần hữu ích (usable part). một ô. Như vậy, tại mỗi thời điểm, chỉ duy nhất một ô được đọc, hoặc được 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 ghi mà thôi. hai ký tự #. Người ta viết f#f. 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 Chú ý rằng một số tài liệu xem ký tự trắng không thuộc bảng chữ S, # ∉ S. 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ứ I.2. Hoạt động của máy Turing tự, gọi là trạng thái 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 = 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 là một bộ ba : thông tin trên băng và nội dung của bộ nhớ phụ. c = (f, q, xg) ∈ S* ´ Q ´ SS* Một cách hình thức, máy Turing được định nghĩa từ các thành phần sau đây : 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. PGS. TS. PHAN HUY KHÁNH biên soạn 25
28 Lý thuyết tính toán 27 Mô hình các máy RAM q3, 1 → 1, L, q3, 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. q3, 1 → 1, R, q3, 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 q3, 1 → #, R, q1 } hình c’ = (f’, q’, g’), ký hiệu : Xét cấu hình c = (e, q1, 111), ta có thể có các chuyển tiếp sau : c Ã− c’ c = (e, q1, 111) Ã− (11, q1, 1) Ã- (111, q2, #) 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à : 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ếu m = R thì f’ = fy và g’ = g nên không thể tiếp tục được nữa. − nếu m = L thì f = f’z và g’ = zyg, với z là ký tự trên băng. Bây giờ xét cấu hình c’ = (e, q1, 1111), ta có các chuyển tiếp sau : Trong cả hai trường hợp, chuyển tiếp làm thay đổi nội dung của ô nằm dưới c’ = (e, q1, 1111) Ã− (e, q1, 111) đầu đọc−ghi, và dịch đầu đọc−ghi qua trái hoặc qua phải tuỳ theo giá trị chỉ Ã− (11, q1, 11) 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’. Ã− (111, q2, 1) Ã− (1111, q1, #) ←−− Phần hữu ích −−→ Ã− (111, q3, 1) Ã− (11, q3, 1) ...### f x g ###... Ã− (11, q3, 11) Ã− (1, q3, 111) q Ã− (e, q3, 1111) = (#, q3, 1111) Ã− (e, q3, # 1111) Hình 3.2. Máy Turing trong cấu hình c = (f, q, xg) Ã− (#, q1, 1111) = (e, q1, 1111) 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 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á 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 trình tính toán có thể lặp lại vô hạn. hình c’, ký hiệu c Ã−n c’, nếu và chỉ nếu : 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 − tồn tại một dãy các cấu hình c0, c1, ..., cn sao cho c = c0, c’ = cn (111, q3, 1) chẳng hạn, người ta có thể thực hiện chuyển tiếp : − 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 (111, q3, 1) Ã− (1111, q3, #) 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ó độ Chúng ta sẽ quay lại xét hiện tượng này. 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 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ó cầu của quan hệ Ã−). thể, người ta nói rằng máy Turing dừng (halt) tại những cấu hình đó. Chú ý rằng người ta không xét các phép tính không hợp lệ. 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 : Ví dụ 3.1 : c Ã− c’ Cho máy Turing T = với S = {1, #}, Q = {q1, q2, q3, q4} và T P = { q1, 1 → 1, R, q2, 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’. q2, 1 → 1, R, q1, 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 q1, # → #, L, q3, 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 :
30 Lý thuyết tính toán 29 Mô hình các máy RAM 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 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) nhất một phép tính hợp lệ dừng, gọi là L(T). trong Q ´ S : 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 nc : Q ´ S → S hàm ký tự mới phép tính hợp lệ nào dừng. hàm dịch chuyển đầu đọc−ghi mh : Q ´ S → M I.3. Cấu hình xuất phát của máy Turing ns : Q ´ S → Q hàm trạng thái mới 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ễ Ba hàm này được định nghĩa như sau : 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ữ nc (q, x) = y 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 mh (q, x) = m 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 ns (q, x) = q’ cấu hình xuất phát như sau : nếu và chỉ nếu (q, x, y, m, q’) là một quy tắc của P. 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 Các máy Turing được sử dụng theo nhiều cách khác nhau. Ví dụ vừa được máy Turing. 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, 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 ta sẽ tiếp tục trình bày cách máy Turing tính toán các hàm. đị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. II. Các hàm T−tính được Mặt khác, người ta cũng quy ước thêm như sau : Giả sử ta chỉ xét các máy Turing đơn định. 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). Cho T = là một máy Turing. Ta nói T xác định một hàm bộ phận fT Đầ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. 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 Một câu f ∈ S* được gọi là được thừa nhận (accepted) bởi máy Turing nếu, T, và với mỗi câu f ∈ S*, ta có một phép tính hợp lệ tối đa : 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 (e, q1, f) Ã− c’ = (g, q, h) 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à T ngôn ngữ được thừa nhận (accepted language) bởi máy Turing. với fT được xác định bởi : 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 : fT(f) = gh L(T) = { f ∈ S * | f gồm một số lẻ chữ số 1 }. 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. I.4. Máy Turing đơn định Ví dụ 3.2 : Điểm bất tiện thứ hai trong mô hình máy Turing là có thể thực hiện nhiều Cho T1 = với S = {0, 1, #}, Q = {q1, q2, q3} và 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 P = { q1, 1 → 1, R, q1, 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 q2, 0 → 1, L, q3, Turing như vậy là đơn định (deterministic). q1, 0 → 0, R, q1, 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 q2, 1 → 0 L, q2, 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 q1, # → #, L, q2, 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 q2, # → 1, L, q3 } Turing : P⊆Q´S´S´M´Q
32 Lý thuyết tính toán 31 Mô hình các máy RAM Bây giờ xét các cấu hình c1 = (e, q1, 10100) và c2 = (e, q1, 100111). Tồn tại 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 : 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 : δ‘L(f) = 1 nếu f ∈ L c1 = { e, q1, 10100} Ã− (1010, q3, 1) δ‘L(f) không xác định nếu không (f ∉ L) T c2 = { e, q1, 100111} Ã− (10, q3, 1000) 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φ , T trên S ∪ {#} chẳng hạn, gọi là đồ thị của hàm, được xác định bởi : 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 Gφ = { f # φ(f) | f ∈ Dom(φ) } 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. 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. 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. III. Lớp các hàm T−tính được Ví dụ 3.3 : 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 Cho T2 = < S, Q, P> với S = {1, #}, Q = {q1, q2, q3, q4} và cũng tìm cách mở rộng khả năng hoạt động của các máy Turing. P = { q1, 1 → #, R, q2, q2, 1 → # R, q3, III.1. Một số hàm sơ cấp q3, 1 → 1, R, q3, 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*, q3, # → 1, L, q4 } 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 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 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 #. Đó 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ố là các hàm hằng, hàm chiếu, hàm kế tiếp và hàm kế trước. 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 III.1.1. Các hàm hằng (constant functions) cho kết quả là một biểu diễn đơn nguyên. Chẳng hạn : Xét hàm hằng : (ε, q1, 11 # 111) Ã− (##1111, q4, 111) n Bin_FivnG : (G*) → G* T 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 Đị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 luôn trả về một câu nào đó của G*. −computable), viết tắt T−tính được, nếu tồn tại một máy Turing đơn định tính Ví dụ 3.4 : được hàm này. 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, 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ó. Bin_Fiv2G luôn trả về một câu, chẳng hạn 101∈G* (101 là biểu diễn nhị phân Chú ý rằng quan điểm tính được trong lý thuyết tính toán được nêu ra ở đây của số 5). liên quan chặt chẽ đến sự nhận biết (cognition) : Xây dựng máy Turing thực hiện hàm hằng Bin_Fiv2G như sau : Một mặt, với mọi ngôn ngữ L ⊂ S*, sẽ có một hàm đặc trưng T = với S = G ∪ {#}, Q = {q1, q2, q3, q4, q5} và (characteristic function) δL tương ứng được định nghĩa bởi : P = { q1, 1 → $, R, q1, δL(f) = 1 nếu f ∈ L q1, # → #, R, q2, δ L (f ) = 0 nếu không (f ∉ L) q1, 0 → #, R, q1,
34 Lý thuyết tính toán 33 Mô hình các máy RAM q2, 0 → #, R, q2, SuccG : G* → G* q2, 1 → #, R, q2, 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. q2, # → 1, L, q3, Ví dụ 3.6 : q3, # → 0, L, q4, Giả sử G = {0, 1, 2} với thứ tự 0 với S = G ∪ {#}, Q = q1, q2, q3, q4, q5} và 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 P = { q1, 1 → #, R, q1, chữ và cho mọi kiểu thứ tự của các ký tự trong bảng chữ. q1, 0 → # R, q1, III.3. Các hàm kế trước (predecessor functions) q1, # → #, R, q2, Tương tự hàm kế tiếp, ta có thể dễ dàng xây dựng hàm kế trước : q2, 1 → 1, R, q2, PredG : G* → G* q2, 0 → 0, R, q2, q2, # → #, R, q3, 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ự đã q3, 1 → #, R, q3, 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 q3, 0 → #, R, q3, trước câu rỗng cũng chính là câu rỗng. q3, # → #, R, q4, Bài tập : Xây dựng một máy Turing thực hiện hàm kế trước. q4, 1 → #, R, q4, q4, 0 → #, R, q4 q4, # → #, L, q5 } III.4. Sự hợp thành (composition) Ta có c = (e, q1, 10#01#100#101#) Ã−* (#, q5, #10#) 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 T 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. 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 :