Mô hình máy turing (TM)

Nội dung chính :

Trong chương này, ta sẽ xét thêm một loại máy trừu tượng khác - máy Turing (TM - Turing Machines). Chúng có khả năng đoán nhận được lớp ngôn ngữ lớn hơn lớp ngôn ngữ phi ngữ cảnh. Đây còn là một mô hình của sự tính toán, mô hình của các thủ tục hiệu quả, là nền tảng cho quá trình xử lý của máy tính hiện đại, được giới thiệu bởi Alan Turing vào năm 1936. Nhờ đó, các khái niệm về "sự tính được", "sự giải được" được xác định một cách rõ ràng trên cơ sở sự xuất hiện của một số hàm không tính được, các bài toán không giải được.

Mục tiêu cần đạt:

Cuối chương, sinh viên cần phải nắm vững:

Khái niệm TM, định nghĩa và các thành phần.

Các kỹ thuật thiết kế TM.

Một số biến dạng TM từ mô hình chuẩn.

Xây dựng TM dùng nhận dạng ngôn ngữ hoặc tính toán các hàm số nguyên đơn giản được biểu diễn trong hệ nhất phân.

Các tính chất của lớp ngôn ngữ được chấp nhận bởi TM.

Kiến thức cơ bản:

Để tiếp thu tốt nội dung của chương này, sinh viên cần hiểu rõ cách thiết kế các hàm chuyển trạng thái trên mô hình máy tính toán; ý tưởng thiết kế một số thuật toán đơn giản trên tập hợp số, …

Tài liệu tham khảo :

John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 7 : Turing Machines )

Peter Linz – An Introduction to Formal Languages and Automata – D.C. Heath and Company – 1990.

Mô tả TM

Máy Turing có rất nhiều dạng đồng khả năng, nghĩa là có nhiều mô hình và định nghĩa khác nhau cho máy Turing nhưng tất cả chúng đều tương đương nhau. Song, nói chung mô hình cơ bản của một máy Turing gồm :

- Một bộ điều khiển hữu hạn.

- Một băng được chia thành các ô.

- Một đầu đọc-viết, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc hay viết ký hiệu.

Mỗi ô có thể giữ được một ký hiệu trong số hữu hạn các ký hiệu băng (các ký hiệu được phép viết trên băng). Khởi đầu xem như n ô bên trái của băng (n ≥ 0) giữ chuỗi nhập (input), chuỗi nhập là một chuỗi các ký tự được chọn từ một tập hợp con của tập hợp các ký hiệu băng, tập hợp con này gọi là tập các ký hiệu nhập. Phần còn lại của băng coi như có vô hạn khoảng trống, ký hiệu B (Blank), B là một ký hiệu đặc biệt của băng nhưng không phải là ký hiệu nhập.

Hình 7.1 - Mô tả một TM

Mỗi bước chuyển của máy Turing, phụ thuộc vào ký hiệu do đầu đọc đọc được trên băng và trạng thái của bộ điều khiển, máy sẽ thực hiện các bước sau :

1) Chuyển trạng thái

2) In một ký hiệu trên băng tại ô đang duyệt (nghĩa là thay ký hiệu đọc được trên băng bằng ký hiệu nào đó)

3) Dịch chuyển đầu đọc-viết (sang trái (L), sang phải (R) hoặc đứng yên(∅))

Định nghĩa

Một cách hình thức, ta định nghĩa một máy Turing (TM) như sau :

Định nghĩa: TM là một hệ thống M (Q, ∑, Γ, δ, q₀, B, F), trong đó:

. Q : tập hữu hạn các trạng thái.

. ∑: bộ ký hiệu nhập.

. Γ : tập hữu hạn các ký tự được phép viết trên băng.

. B : ký hiệu thuộc Γ dùng chỉ khoảng trống trên băng (Blank).

. δ : hàm chuyển ánh xạ : Q × Γ → Q × Γ× {L, R, ∅ size 12{ emptyset } {}}

(δ có thể không xác định với một vài đối số)

. q₀ ∈ Q là trạng thái bắt đầu

. F ⊆ Q là tập các trạng thái kết thúc

Hình thái TM (Instantaneous description - ID)

{}Một hình thái của máy Turing M được cho bởi α₁ q α₂, trong đó q là trạng thái hiện hành của M; α₁α₂ ∈ Γ^* là nội dung của băng tính từ đầu băng cho tới ký hiệu khác Blank bên phải nhất của băng. Giả sử Q và Γ rời nhau: đầu đọc đang đọc ký hiệu bên trái nhất của α₂ hoặc nếu α₂ = ε thì đầu đọc đọc Blank.

Hàm chuyển

Ta định nghĩa một phép chuyển trạng thái của TM như sau :

Đặt X₁X₂ ... X_i-1q X_i ... X_n là một ID.

+ Giả sử δ(q, Xi) = (p, Y, L),trong đó:

- Nếu i - 1 = n thì X_i là B.

- Nếu i =1 thì không có ID kế tiếp, nghĩa là đầu đọc không được phép vượt qua cận trái của băng.

- Nếu i > 1 ta viết :

X₁X₂ ... X_i-1q X_i ... X_n ⊢M X₁X₂ ... X_i-2p X_i-1Y X_i+1 ... X_n

+ Tương tự δ(q, Xi) = (p, Y, R) thì ta viết :

X₁X₂ ... X_i-1q X_i ... X_n ⊢M X₁X₂ ... X_i-1Yp X_i+1 ... X_n

+ Tương tự δ(q, Xi) = (p, Y, ∅) thì ta viết :

X₁X₂ ... X_i-1q X_i ... X_n ⊢M X₁X₂ ... X_i-1pY X_i+1 ... X_n

Chú ý rằng nếu i - 1 = n thì chuỗi X_i ... X_n là rỗng và vế phải dài hơn vế trái, nghĩa là TM M mở rộng chuỗi ký hiệu trên băng.

Nếu hai ID được quan hệ nhau bởi ⊢M thì ta nói ID thứ hai là kết quả của ID thứ nhất bằng một lần chuyển, một bước áp dụng hàm chuyển (hoặc nói cái thứ hai thu được từ cái thứ nhất bằng một lần chuyển). Nếu một ID thu được từ ID khác bằng một số lần chuyển (có thể bằng 0) thì ta ký hiệu quan hệ là ⊢M^* . Ta cũng có thể bỏ đi ký hiệu M trong cách viết các quan hệ trên nếu không có nhầm lẫn.

Ngôn ngữ được chấp nhận bởi TM

Ký hiệu L(M): tập hợp các chuỗi trong Γ^* là nguyên nhân đưa TM M đi vào trạng thái kết thúc khi đã thực hiện việc thay thế từ bên trái các ký hiệu trên băng của M với trạng thái bắt đầu q₀. Một cách hình thức, ta định nghĩa tập hợp ngôn ngữ được chấp nhận bởi TM M (Q, ∑, Γ, δ, q₀, B, F) là tập

L(M) = { w | w ∈ Γ^* và q₀ w ⊢M^* α₁ p α₂ với p ∈ F còn α₁α₂ ∈ Γ^*}

Cho TM nhận diện một ngôn ngữ L là cho lần lượt các từ của L vào TM xem TM có chấp nhận từ đó không. TM sẽ dừng và đi vào một trong những trạng thái kết thúc ∈ F (không có phép chuyển kế tiếp) khi từ được chấp nhận, nhưng nếu TM không chấp nhận một từ nào đó thì TM có thể ngừng ở một trạng thái ∉ F hoặc cũng có thể nó chạy mãi mà không dừng lại.

Thí dụ 7.1 : Thiết kế TM chấp nhận ngôn ngữ L = { 0ⁿ1ⁿ | n ≥ 1}

Khởi đầu TM chứa 0ⁿ1ⁿ bên trái nhất trên băng sau đó là vô hạn khoảng trống Blank. TM lặp lại quá trình sau:

- M thay 0 bên trái nhất bằng X rồi chuyển sang phải tới 1 trái nhất, TM thay 1 này bằng Y rồi dịch chuyển về bên trái cho tới khi gặp X phải nhất nó chuyển sang phải một ô (tới 0 trái nhất) rồi tiếp tục lặp một chu trình mới.

- Nếu trong khi dịch chuyển sang phải để tìm 1 mà TM gặp Blank thì TM dừng và không chấp nhận input. Tương tự, khi TM đã thay hết 0 bằng X và kiểm tra còn 1 trên băng thì TM cũng dừng và không chấp nhận input.

- TM chấp nhận input nếu như cũng không còn ký hiệu 1 nào nữa trên băng.

Đặt TM M (Q, ∑, Γ, δ, q₀, B, F) với các thành phần :

Q = {q₀, q₁, q₂, q₃, q₄}; ∑= {0, 1}; Γ = {0, 1, X, Y, B} và F = {q₄}.

Ta có thể hình dung mỗi trạng thái là một câu lệnh hoặc một nhóm các câu lệnh trong chương trình. Trạng thái q₀ là trạng thái khởi đầu và nó làm cho ký hiệu 0 bên trái nhất thay bằng X. Trạng thái q₁ được dùng để tiến sang phải bỏ qua các số 0 và Y để tìm 1 bên trái nhất. Nếu M tìm thấy 1 nó thay 1 bằng Y rồi đi vào trạng thái q₂. Trạng thái q₂ đưa M tiến sang trái cho tới X đầu tiên và đi vào trạng thái q₀, dịch chuyển sang phải để tới 0 bên trái nhất và tiếp tục một chu trình mới. Khi M tiến sang phải trong trạng thái q₁, nếu B hoặc X được tìm thấy trước 1 thì input bị loại bỏ (không chấp nhận) vì có chứa nhiều ký hiệu 0 hơn 1 hoặc input không có dạng 0^*1^* .

Trạng thái q₀ còn có vai trò khác. Nếu trạng thái q₂ tìm thấy X bên phải nhất và ngay sau đó là Y thì các số 0 đã được xét hết, do đó ở trạng thái bắt đầu một chu trình mới q₀ không tìm thấy ký hiệu 0 nào để thay thành X mà chỉ gặp Y thì TM đi vào trạng thái q₃ duyệt qua các Y để kiểm tra có hay không có ký hiệu 1 còn lại. Nếu theo ngay sau các Y là B, nghĩa là trên băng nhập không còn ký hiệu 1 nào nữa thì TM sẽ đi vào q₄ (trạng thái kết thúc) để chấp nhận input. Ngược lại input bị loại bỏ.

Hàm chuyển δ được cho trong bảng sau :

Các phép chuyển hình thái của TM M trên input 0011 :

q₀0011 ⊢ Xq₁011 ⊢ X0q₁11 ⊢ X q₂0Y1 ⊢ q₂X0Y1 ⊢ X q₀0Y1 ⊢ XXq₁Y1 ⊢ XXY q₁1 ⊢ XX q₂YY ⊢ X q₂XYY ⊢ XX q₀YY ⊢ XXYq₃Y ⊢ XXYYq₃ ⊢ XXYYq₄

Nhận xét: Như vậy, ta có thể dễ dàng thấy, TM khác với một ôtômát hữu hạn ở chỗ đầu đọc-viết có thể dịch chuyển tự do trên băng, không những đọc mà còn có khả năng viết trên băng và vùng làm việc còn có thể mở rộng theo yêu cầu phát sinh. TM khác với ôtômát đẩy xuống ở chỗ nó không dùng thêm Stack như một bộ giữ nhớ mà viết các ký hiệu cần ghi nhớ ngay trên băng.