0.6 Máy turing  (Page 3/15)

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

Khởi đầu TM chứa 0n1n 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, ∑, , , q0, B, F) với các thành phần :

Q = {q0, q1, q2, q3, q4}; ∑= {0, 1};  = {0, 1, X, Y, B} và F = {q4}.

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 q0 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 q1 đượ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 q2. Trạng thái q2 đưa M tiến sang trái cho tới X đầu tiên và đi vào trạng thái q0, 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 q1, 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 q0 còn có vai trò khác. Nếu trạng thái q2 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 q0 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 q3 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 q4 (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 :

q00011 ⊢ Xq1011 ⊢ X0q111 ⊢ X q20Y1 ⊢ q2X0Y1 ⊢ X q00Y1 ⊢ XXq1Y1 ⊢ XXY q11 ⊢ XX q2YY ⊢ X q2XYY ⊢ XX q0YY ⊢ XXYq3Y ⊢ XXYYq3 ⊢ XXYYq4

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.

Ngôn ngữ và "hàm tính được"

Ngôn ngữ được chấp nhận bởi một máy Turing được gọi là ngôn ngữ đệ qui liệt kê - recursively enumerable (r.e). Đó là một lớp ngôn ngữ rất rộng, nó thực sự chứa ngôn ngữ phi ngữ cảnh CFL và một số ngôn ngữ mà không thể xác định các thành phần một cách máy móc. Nếu L(M) là một ngôn ngữ như vậy thì bất kỳ một máy Turing nào nhận diện L(M) cũng sẽ không dừng trên một số input không thuộc L(M). Nhưng nếu một chuỗi w  L(M) thì chắc chắn TM dừng, tuy nhiên TM sẽ chạy bao lâu trên input thì chúng ta không thể biết được và ta cũng không biết chắc chắn liệu TM có dừng lại hay không. Một cách thuận lợi và có ý nghĩa hơn là xét một lớp con của lớp ngôn ngữ đệ qui liệt kê, trong đó mọi ngôn ngữ đều được chấp nhận bởi ít nhất một máy Turing dừng trên mọi input. Lớp ngôn ngữ này gọi là lớp ngôn ngữ đệ qui - recursive sets.