0.6 Máy turing  (Page 7/15)

6) d([q4, B], [Ö, d]) = ([q4, B], [Ö, d], L)

M dịch trái trên các ký hiệu đã đánh dấu.

7) d([q4, B], [B, c]) = ([q5, B], [B, c], L)

M gặp ký hiệu c.

8) d([q5, B], [B, d]) = ([q6, B], [B, d], L)

Nếu ký hiệu ngay bên trái c chưa được đánh dấu thì M tiến sang trái để tìm ký hiệu bên phải nhất đã được đánh dấu.

9) d([q6, B], [B, d]) = ([q6, B], [B, d], L)

M tiếp tục dịch chuyển sang trái.

10) d([ q6, B], [Ö, d]) = ([q1, B], [Ö, d], R)

M gặp ký hiệu đã đánh dấu, nó dịch phải để lấy ký hiệu chưa đánh dấu bên cạnh và tiếp tục vòng lặp so sánh. Khi đó, thành phần thứ 1 lại trở thành q1.

11) d([q5, B], [Ö, d]) = ([q7, B], [Ö, d], R)

M ở trạng thái [q5, B] ngay sau khi vượt sang trái c. Nếu ký hiệu xuất hiện ngay trước c đã được đánh dấu thì tất cả các ký hiệu trước c đều đã được đánh dấu. M phải kiểm tra xem bên phải c còn có ký hiệu nào chưa được đánh dấu hay không. Nếu không còn ký hiệu nào thì M chấp nhận input.

12) d([q7, B], [B, c]) = ([q8, B], [B, c], R)

M dịch sang phải c.

13) d([q8, B], [Ö, d]) = ([q8, B], [Ö, d], R)

M tiếp tục dịch sang phải trên các ký hiệu đã được đánh dấu.

14) d([q8, B], [B, B]) = ([q9, B], [Ö, B], )

M tìm gặp Blank, nó dừng và chấp nhận chuỗi. Nếu M gặp ký hiệu chưa được đánh dấu khi thành phần thứ 1 là q8 thì nó dừng và không chấp nhận.

Dịch qua (shifting over)

Máy Turing có thể tạo ra một không gian trống trên băng bằng cách dời các ký hiệu không trống trên băng đi sang phải hữu hạn ô. Để làm điều đó đầu đọc phải thực hiện dịch phải, lặp lại việc lưu ký hiệu đọc được vào bộ điều khiển và thay thế chúng bằng ký hiệu đọc được ở ô bên trái. Nếu có đủ ô trống, TM cũng có thể chuyển dịch một khối ký hiệu sang trái một cách tương tự.

Thí dụ 7.6 :Xây dựng TM M(Q, å, , , q0, B, F) dịch toàn bộ các ký hiệu không trống trên băng sang phải 2 ô.

Ta giả sử không có Blank giữa các ký hiệu không trống, vì vậy khi đầu đọc gặp Blank thì nó đã dịch xong các ký hiệu khác trống trên băng. Tập các trạng thái Q chứa các phần tử dạng [q, A1, A2] với q = q1 hoặc q2 và A1, A2  . Gọi X là một ký hiệu đặc biệt được chấp nhận trên băng của M, nó không được sử dụng với mục đích nào khác ngoài quá trình dịch chuyển trên băng. M bắt đầu với trạng thái [q1, B, B]và hàm chuyển thực hiện như sau:

Với Ai   - {B, X}

1) d([q1, B, B], A1) = ([q1, B, A1], X, R)

M lưu ký hiệu đọc đầu tiên vào thành phần thứ 3 trong bộ điều khiển, ghi X vào ô đang đọc rồi dịch sang phải.

2) d([q1, B, A1], A2) = ([q1, A1, A2], X, R)

M chuyển ký hiệu ở thành phần thứ 3 sang thành phần thứ 2, lưu trữ ký hiệu đọc được vào thành phần thứ 3, viết X vào ô đang đọc rồi dịch sang phải.

3) d([q1, A1, A2], A3) = ([q1, A2, A3], A1, R)

Bắt đầu từ bước chuyển này, M lần lượt đọc vào một ký hiệu, ghi nó vào thành phần thứ 3, chuyển ký hiệu được ghi trước đó ở thành phần thứ 3 sang thành phần thứ 2, chép lại ký hiệu ở thành phần thứ 2 vào ô đang đọc rồi dịch sang phải.

4) d([q1, Ai - 2, Ai – 1], Ai) = ([q1, Ai - 1, Ai], Ai - 2, R)

5) d([q1, An - 1, An], B) = ([q2, An, B], An - 1, R)

Cho đến khi M gặp B, nó dốc nốt 2 ký hiệu cuối đang giữ trong bộ nhớ để bắt đầu đi vào trạng thái kết thúc.