0.6 Máy turing  (Page 9/15)

Nếu (q, X) = (p, Y, L) thì qX ⊢ pBY

Nếu (q, X) = (p, B, R) thì qX ⊢ p

ĐỊNH LÝ 7.1 : Nếu L được nhận diện bởi TM với băng vô hạn hai chiều thì L cũng được nhận diện bằng TM vô hạn một chiều băng

Chứng minh

Gọi M2 là TM với băng vô hạn hai chiều M2 (Q2, 2, 2, 2, q2, B, F2) nhận diện L. Ta xây dựng M1 là TM vô hạn một chiều băng nhận diện L. Băng của M1 có 2 rãnh:

- Rãnh trên biểu diễn cho băng của M2 phía phải đầu đọc lúc khởi đầu.

- Rãnh dưới biểu diễn cho băng phía trái đầu đọc lúc khởi đầu theo thứ tự ngược lại.

(a) - Băng của M2

(b) - Băng của M1

Hình 7.3 - Băng nhập của TM M2 và M1

M1 thực hiện các phép chuyển tương tự như M2 nhưng khi M2 thực hiện các phép chuyển phía phải đầu đọc thì M1 làm việc với rãnh trên, khi M2 thực hiện các phép chuyển bên trái đầu đọc thì M1 làm việc ở rãnh dưới

Một cách hình thức M1 (Q1, 1, 1, 1, q1, B, F1), trong đó :

Q1 là tập hợp các đối tượng dạng [q, U] hoặc [q, D], trong đó q là trạng thái trong Q2, còn U, D dùng chỉ rằng M1 đang làm việc với rãnh trên (Up) hay rãnh dưới (Down). Các ký hiệu băng của M1 (các ký hiệu thuộc 1) có dạng [X, Y] trong đó X, Y thuộc 2, hơn nữa Y có thể là  là ký hiệu không có trong 2 dùng để đánh dấu ô trái nhất trên băng của M1 .

1 là tập hợp các đối tượng dạng [a, B] trong đó a  2.

F1 = {[q, U], [q, D] q Î F2}.

Hàm chuyển 1 có dạng như sau:

1)1(q1, [a, B]) = ([q, U], [X, ], R) nếu 2(q2, a) = (q, X, R)

Nếu M2 chuyển sang phải trong lần chuyển đầu tiên thì M in  trên rãnh dưới, ghi nhớ U vào thành phần thứ hai của trạng thái và dịch phải. Thành phần thứ nhất của trạng thái lưu trạng thái của M2. M1 in X (ký hiệu mà M2 in ra) ở rãnh trên.

1. a Î 2 U {B} :

1(q1, [a, B]) = ([q, D], [X, ], R) nếu 2(q2, a) = (q, X, L)

Nếu M2 chuyển sang trái trong lần chuyển đầu tiên thì M1 in  trên rãnh dưới, ghi nhớ D vào thành phần thứ hai của trạng thái và dịch phải. Thành phần thứ nhất của trạng thái lưu trạng thái của M2. M1 in X (ký hiệu mà M2 in ra) ở rãnh trên.

3) [X, Y] 1, với Y   và A = L hoặc R :

1([q, U], [X, Y]) = ([p, U], [Z, Y], A) nếu 2(q, X) = (p, Z, A)

M1 ở rãnh trên thực hiện tương tự như M2.

4) 1([q, D], [X, Y]) = ([p, D], [X, Z], A) nếu 2(q, Y) = (p,Z, $\overline{A}$ )

(Trong đó nếu A = L thì $\overline{A}$ = R và nếu A = R thì $\overline{A}$ = L)

Ở rãnh dưới, M1 làm tương tự M2 nhưng dịch chuyển đầu đọc theo hướng ngược lại.

5) 1([q, U], [X, ]) = 1([q, D], [X, ]) = ([p, C], [Y,], R]

nếu 2(q, X) = (p, Y, A)

(Trong đó C = U nếu A = R, C = D nếu A = L)

M1 làm tương tự M2 ở ô khởi đầu, công việc tiếp theo của M1 thực hiện ở rãnh trên hay dưới phụ thuộc vào hướng chuyển đầu đọc của M2.

Máy turing với nhiều băng vô hạn hai chiều

Xét máy Turing có một bộ điều khiển có k đầu đọc và k băng vô hạn hai chiều. Mỗi phép chuyển của máy Turing, phụ thuộc vào trạng thái của bộ điều khiển và ký tự đọc được tại mỗi đầu đọc, nó có thể thực hiện các bước sau :

1) Chuyển trạng thái.

2) In ký hiệu mới tại mỗi đầu đọc để thay thế ký hiệu vừa đọc.

3) Đầu đọc có thể giữ nguyên vị trí hoặc dịch trái hoặc dịch phải 1 ô một cách độc lập nhau.