0.6 Máy turing  (Page 6/15)

Thí dụ 7.4 : Thiết kế TM nhận vào một số nguyên n (viết ở dạng nhị phân) và kiểm tra xem đó có phải là số nguyên tố hay không ?

Ta dùng băng 3 rãnh như hình 7.2 với nguyên tắc sau :

Số n ở dạng nhị phân được đưa vào trên rãnh 1 và được bao bởi cặp dấu Ë và $. Như vậy các ký hiệu được phép ghi trên băng là [Ë, B, B], [0, B, B], [1, B, B] và [$, B, B]. Các ký hiệu này tương ứng với Ë, 0, 1, $ khi xem chúng là ký hiệu nhập. Ký hiệu Blank là [B, B, B].

Viết số 2 dạng nhị phân trên rãnh 2 (tức 10)

Chép rãnh 1 vào rãnh 3 sau đó lấy rãnh 3 trừ rãnh 2 nhiều lần nhất có thể được (thực hiện việc chia số cần kiểm tra cho số trên rãnh 2, lấy phần dư)

Xét số còn lại (số dư) :

- Nếu số còn lại là 0 thì input không là số nguyên tố (vì nó chia hết cho số trên rãnh 2)

- Nếu số còn lại khác 0 thì tăng số trên rãnh 2 thêm một đơn vị: nếu số trên rãnh 2 bằng số trên rãnh 1 (số n) thì input n là số nguyên tố vì n đã không chia hết cho bất kỳ số nào từ 2 đến n -1. Nếu số trên rãnh 2 nhỏ hơn số trên rãnh 1 thì ta lặp lại quá trình trên với số mới trên rãnh 2.

Hình 7.2 - TM với băng 3 rãnh

Hình 7.2 trên mô tả một TM với k = 3, kiểm tra số n = 47 viết trên rãnh 1 dưới dạng nhị phân, TM đang thực hiện phép chia 47 cho 5. Nó đã trừ 2 lần số 5 vào số 47, vậy ở rãnh 3 hiện đang có số 37.

Đánh dấu ký hiệu (checking off symbols)

Kỹ thuật đánh dấu thường dùng để nhận diện các ngôn ngữ được định nghĩa bằng cách lặp lại chuỗi chẳng hạn như {ww  w  å*}; {wcy  w, y  å*, w  y} hoặc {wwR  w  å*} hoặc các ngôn ngữ có độ dài các chuỗi con cần được so sánh, như {aibi  i  1} hoặc {aibjck  i = j hoặc j = k}.

Ta dùng một rãnh mở rộng trên băng để giữ ký hiệu đánh dấu . Ký hiệu  xuất hiện khi ký hiệu trên rãnh ngay bên dưới nó đã hoặc đang được xét bởi TM.

Thí dụ 7.5 :Xét máy Turing M (Q, å, , , q0, B, F) nhận diện ngôn ngữ L có dạng {wcw  w  (a+b)+} với các thành phần như sau :

Q = {[q, d]  q = q1, ..., q9 và d = a, b hoặc B} = {q1, ..., q9}  {a, b, B} (thành phần thứ hai của các trạng thái dùng để lưu trữ ký hiệu nhập)

å = {[B, d]  d = a, b, c} (ký hiệu nhập [B, d]được xác định bởi d)

 = {[X, d]  X = B hoặc  ; d = a, b, c hoặc B}.

q0 = [q1, B]

B = [B, B] được định nghĩa là B, ký hiệu Blank.

F = {[q9, B]}.

Với d = a hoặc b; e = a hoặc b, ta định nghĩa hàm chuyển  như sau:

1) d([q1, B], [B, d]) = ([q2, d], [Ö, d], R)

M đánh dấu ký hiệu được duyệt trên băng, lưu trữ vào bộ điều khiển và dịch chuyển sang phải.

2) d([q2, d], [B, e]) = ([q2, d], [B, e], R)

M tiếp tục dịch phải trên các ký hiệu chưa đánh dấu và tìm c.

3) d([q2, d], [B, c]) = ([q3, d], [B, c], R)

Khi tìm thấy c, M đi vào trạng thái mà thành phần đầu tiên là q3.

4) d([q3, d], [Ö, e]) = ([q3, d], [Ö, e], R)

M dịch phải qua các ký hiệu đã đánh dấu.

5) d([q3, d], [B, d]) = ([q4, B], [Ö, d], L)

M gặp ký hiệu chưa đánh dấu. Nếu ký hiệu chưa đánh dấu giống với ký hiệu đang lưu trong bộ điều khiển thì M đánh dấu rồi dịch trái. Nếu ký hiệu không giống ký hiệu lưu trong bộ điều khiển thì M không dịch chuyển nữa và không chấp nhận input. M cũng dừng nếu ở trạng thái q3 và gặp ký hiệu [B, B] trước khi gặp ký hiệu chưa đánh dấu.