0.6 Máy turing  (Page 5/15)

d(q5, 0) = (q5, B, R)

d(q5, 1) = (q5, B, R)

d(q5, B) = (q6, B, )

Nếu ở trạng thái bắt đầu vòng lặp mới q0 gặp 1 thay vì gặp 0, thì khối các số 0 bên trái đã xét hết, đây là trường hợp kết thúc ii) nêu trên: TM sẽ đi vào trạng thái q5, xoá phần còn lại của băng rồi đi vào trạng thái kết thúc q6 và dừng.

Chẳng hạn TM tính toán phép trừ 2\1 (tức input 0010 ) như sau :

q00010 ⊢ B q1010 ⊢ B0q110 ⊢ B01q20 ⊢ B0q311 ⊢ Bq3011 ⊢ q3B011 ⊢ Bq0011 ⊢ BBq111 ⊢ BB1q21 ⊢ BB11q2 ⊢ BB1q41 ⊢ BBq41 ⊢ Bq4 ⊢ Bq60

Nếu cho TM tính toán 1\2 (tức input 0100) :

q00100 ⊢ Bq1100 ⊢ B1q200 ⊢ Bq3110 ⊢ q3B110 ⊢ Bq0110 ⊢ BBq510 ⊢ BBBq50 ⊢ BBBBq5 ⊢ BBBBq6

Các kỹ thuật xây dựng máy turing

Việc xây dựng máy Turing bằng cách viết (liệt kê) tất cả các hàm chuyển của nó trên băng nhập có thể là một công việc đơn điệu. Để mô tả đầy đủ cách xây dựng máy Turing, ta cần một vài công cụ "cấp cao" hơn. Phần này sẽ trình bày một số công cụ tổng quát :

Lưu trữ trong bộ điều khiển (storage in the finite control)

Bộ điều khiển có thể dùng để lưu trữ một lượng hữu hạn thông tin. Để làm như thế, ta viết mỗi trạng thái như là một cặp các phần tử: một thành phần để điều khiển, thành phần kia lưu giữ 1 ký hiệu. Chú ý rằng, đây chỉ là một cách mở rộng trên khái niệm chứ không thay đổi định nghĩa máy Turing.

Thí dụ 7.3 :Xét máy Turing M nhận vào ký hiệu đầu tiên trên chuỗi nhập (viết trên bộ chữ cái {0, 1}), lưu trữ vào bộ điều khiển và kiểm tra rằng ký hiệu này không có xuất hiện ở vị trí nào khác trên chuỗi nữa hay không ?.

Ta xây dựng TM M (Q, {0, 1}, {0, 1, B}, , [q0, B], B, F}), trong đó tập trạng thái Q bao gồm các trạng thái dạng một cặp thành phần {q0, q1}  {0, 1, B}, tức là Q gồm chứa các trạng thái [q0, 0], [q0, 1], [q0, B], [q1, 0], [q1, 1]và [q1, B]. Trong mỗi cặp này thành phần thứ nhất ghi trạng thái điều khiển, thành phần thứ hai ghi nhớ ký hiệu. Ta định nghĩa hàm chuyển  như sau:

1)d([q0, B], 0) = ([q1, 0], 0, R)

d([q0, B], 1) = ([q1, 1], 1, R)

Bắt đầu từ trạng thái [q0, B], TM đọc và lưu trữ ký hiệu đầu tiên trên băng vào thành phần thứ hai trong bộ điều khiển.

2)d([q1, 0], 1) = ([q1, 0], 1, R)

d([q1, 1], 0) = ([q1, 1], 0, R)

Nếu các ký hiệu được đọc tiếp theo không giống với ký hiệu đang lưu trữ thì tiếp tục di chuyển sang phải.

3)d([q1, 0], B) = ([q1, B], 0, )

d([q1, 1], B) = ([q1, B], 0, )

M đi vào trạng thái kết thúc [q1, B] khi gặp Blank.

M sẽ đi vào trạng thái kết thúc nếu nó tiến đến gặp ký hiệu B mà không có ký hiệu nào giống với ký hiệu đầu tiên đang được lưu trữ trong bộ điều khiển. Vậy nếu M tiến đến B ở trạng thái [q1, 0] hoặc [q1, 1]thì input được chấp nhận. Ngược lại, ở trạng thái [q1, 0] và gặp 0 hoặc ở trạng thái [q1, 1]và gặp 1 thì M dừng và không chấp nhận chuỗi input vì không có hàm chuyển trạng thái để xác định các bước chuyển này.

Một cách tổng quát, ta có thể xem bộ điều khiển gồm k thành phần trong đó một thành phần giữ trạng thái điều khiển và các thành phần kia (k-1 thành phần) dùng lưu giữ thông tin.

Nhiều rãnh trên băng (multiple tracks)

Một cách mở rộng khác, ta cũng có thể xem băng của TM được chia thành k thành phần, với k>1 và hữu hạn. Một ký hiệu trên băng được xét là một bộ gồm k ký hiệu, mỗi ký hiệu nằm trên một rãnh.