Các biến dạng của máy turing

Máy Turing với băng vô hạn 2 chiều

Máy Turing với băng vô hạn hai chiều cũng tương tự như mô hình gốc (TM vô hạn một chiều băng), chỉ khác là băng của nó không có cận trái như mô hình gốc, nghĩa là ta xem như TM có vô hạn Blank ở cả hai đầu băng. Vì thế hàm δ được mở rộng thêm bằng cách xét thêm các trường hợp đặc biệt tại cận trái như sau :

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 M₂ là TM với băng vô hạn hai chiều M₂ (Q₂, Σ₂, Γ₂, δ₂, q₂, B, F₂) nhận diện L. Ta xây dựng M₁ là TM vô hạn một chiều băng nhận diện L. Băng của M₁ có 2 rãnh:

- Rãnh trên biểu diễn cho băng của M₂ 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.

Hình 7.3 - Băng nhập của TM M 2 và M 1

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

Một cách hình thức M₁ (Q₁, Σ₁, Γ₁, δ₁, q₁, B, F₁), trong đó :

Q₁ 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 Q₂, còn U, D dùng chỉ rằng M₁ đ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 M₁ (các ký hiệu thuộc Γ₁) có dạng [X, Y] trong đó X, Y thuộc Γ₂, hơn nữa Y có thể là  là ký hiệu không có trong Γ₂ dùng để đánh dấu ô trái nhất trên băng của M₁ .

Σ₁ là tập hợp các đối tượng dạng [a, B] trong đó a ∈ Γ₂.

F₁ = {[q, U], [q, D] q Î F₂}.

Hàm chuyển δ₁ có dạng như sau:

1) δ₁(q₁, [a, B]) = ([q, U], [X, ], R) nếu δ₂(q₂, a) = (q, X, R)

Nếu M₂ 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 M₂. M₁ in X (ký hiệu mà M₂ in ra) ở rãnh trên.

1. ∀a Î Σ₂ U {B} :

δ₁(q₁, [a, B]) = ([q, D], [X, ], R) nếu δ₂(q₂, a) = (q, X, L)

Nếu M₂ chuyển sang trái trong lần chuyển đầu tiên thì M₁ 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 M₂. M₁ in X (ký hiệu mà M₂ in ra) ở rãnh trên.

3) ∀ [X, Y] ∈Γ₁, với Y ≠  và A = L hoặc R :

δ₁([q, U], [X, Y]) = ([p, U], [Z, Y], A) nếu δ₂(q, X) = (p, Z, A)

M₁ ở rãnh trên thực hiện tương tự như M₂.

4) δ₁([q, D], [X, Y]) = ([p, D], [X, Z], A) nếu δ₂(q, Y) = (p,Z, A¯ size 12{ {overline {A}} } {})

(Trong đó nếu A = L thì A¯ size 12{ {overline {A}} } {} = R và nếu A = R thì A¯ size 12{ {overline {A}} } {} = L)

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

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

nếu δ₂(q, X) = (p, Y, A)

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

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

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.

Khởi đầu input xuất hiện trên băng thứ nhất, các băng khác chỉ toàn Blank.

Một máy Turing như vậy gọi là máy Turing với nhiều băng vô hạn hai chiều.

ĐỊNH LÝ 7.2 : Nếu L được nhận dạng bởi máy Turing nhiều băng vô hạn hai chiều thì nó cũng được nhận dạng bởi máy Turing một băng vô hạn hai chiều.

Chứng minh

Giả sử L được nhận diện bởi máy Turing k băng vô hạn hai chiều M₁, ta xây dựng máy Turing M₂ một băng với 2k rãnh, 2 rãnh sẽ mô phỏng một băng của M₁ bằng cách: một rãnh giữ ký hiệu trên băng của M₁ một rãnh kia giữ ký hiệu đánh dấu vị trí đầu đọc.

Mỗi phép chuyển của M₁ được mô phỏng bằng M₂ như sau:

M₂ xuất phát tại vị trí trái nhất chứa ký hiệu đánh dấu đầu đọc, M₂ quét sang phải, khi qua mỗi ô có đánh dấu vị trí đầu đọc nó ghi nhớ ký hiệu tại vị trí này và đếm số vị trí đầu đọc đã gặp. Khi M₂ đi sang phải và đã đếm đủ k đầu đọc thì nó đã có đủ thông tin để xác định phép chuyển tương tự như M₁, M₂ lại quét từ phải sang trái, khi đi ngang qua mỗi ô có đánh dấu đầu đọc nó in ký hiệu thay thế ký hiệu tại đầu đọc (như M₁) chuyển vị trí đánh dấu đầu đọc (như M₁ chuyển đầu đọc của nó). Cuối cùng M₂ đổi trạng thái trong bộ điều khiển của nó thành trạng thái mà M₁ chuyển tới.

Hình 7.4 - Máy Turing 1 băng mô phỏng máy Turing 3 băng

Thí dụ 7..8 : Ngôn ngữ {ww | w ∈ (0+1)^*} có thể được chấp nhận bởi một máy Turing có 2 băng bằng cách như sau: Đầu tiên, nó chép lại chuỗi nhập ở băng thứ nhất lên băng thứ hai. Sau đó, trên băng thứ nhất đầu đọc chuyển dần từ cận trái sang cận phải của chuỗi, trong khi trên băng thứ hai đầu đọc lại chuyển ngược lại từ cận phải sang cận trái của chuỗi đó. Chuỗi được chấp nhận nếu suốt quá trình đó, các ký hiệu đọc được trên 2 băng luôn luôn đồng nhất.

Như ta đã biết, để đoán nhận ngôn ngữ này bằng TM một băng thì đầu đọc phải dịch chuyển tới lui rất nhiều lần để so sánh hai nửa của chuỗi nhập từ cả hai đầu băng. Như vậy, số bước dịch chuyển của nó xấp xỉ bằng bình phương độ dài chuỗi nhập, trong khi TM với 2 băng nhập chỉ cần thực hiện số bước chuyển tỷ lệ với độ dài của chuỗi nhập.

Máy Turing không đơn định

Máy Turing không đơn định có mô hình tương tự như mô hình gốc nhưng điểm khác biệt ở chỗ là trong mỗi lần chuyển, máy Turing có thể lựa chọn một trong một số hữu hạn các trạng thái kế tiếp, lựa chọn hướng chuyển đầu đọc, và lựa chọn ký hiệu in ra trên băng để thay thế ký hiệu vừa đọc được. Máy Turing trong mô hình gốc còn gọi là máy Turing đơn định.

ĐỊNH LÝ 7.3 : Nếu L được chấp nhận bởi máy Turing không đơn định M 1 thì L cũng được chấp nhận bởi một máy Turing đơn định M 2 nào đó.

Chứng minh

Với một trạng thái và một ký hiệu băng bất kỳ của M₁, có một số hữu hạn các phép chuyển đến trạng thái kế tiếp, ta có thể đấnh số các trạng thái này là 1, 2, ... Gọi r là số lớn nhất của số các cách lựa chọn với một cặp trạng thái và ký kiệu bất kỳ. Ta có, mọi dãy các phép chuyển trạng thái đều được chỉ ra bằng một dãy chứa các số từ 1 đến r. Ngược lại một dãy hữu hạn bất kỳ gồm các số từ 1 đến r có thể biểu diễn cho một dãy các phép chuyển nào đó cũng có thể không. M₂ được thiết kế có ba băng:

Băng 1 chứa input

Băng 2 sinh ra dãy chứa các số từ 1 đến r một cách tự động theo tính chất dãy ngắn sinh ra trước, nếu các dãy cùng độ dài thì nó sinh ra theo thứ tự liệt kê số (numerical order).

Băng 3 dùng chép input trên băng 1 vào để xử lý: với mỗi số sinh ra trên băng 2, M₂ chép input trên băng 1 vào băng 3 và thực hiện các phép chuyển theo dãy số trên băng 2.

Nếu có một chuỗi nào đó trên băng 2 làm cho M₂ đi vào trạng thái kết thúc thì M₂ dừng và chấp nhận input. Nếu không có chuỗi nào như vậy thì M₂ không chấp nhận input. Tất nhiên M₂ chấp nhận input khi và chỉ khi M₁ chấp nhận input.

Máy Turing nhiều chiều

Máy Turing nhiều chiều gồm một bộ điều khiển hữu hạn, nhưng băng của nó là một mảng k chiều vô hạn về cả 2k phía. Với một số k nào đó, phụ thuộc vào trạng thái và một ký hiệu được đọc, máy thay đổi trạng thái, in một ký hiệu mới tại ô đang đọc và dịch chuyển đầu đọc theo một trong 2k phía.

ĐỊNH LÝ 7.4: Nếu L được chấp nhận bởi máy Turing k chiều M 1 thì L cũng được chấp nhận bởi một máy Turing một chiều M 2 nào đó.

(Phần chứng minh, xem như bài tập)

Máy Turing nhiều đầu đọc

Máy Turing nhiều đầu đọc có k đầu đọc được đánh số từ 1 đến k với k là một số hữu hạn nào đó, nhưng chỉ có một băng input. Một phép chuyển của máy Turing phụ thuộc vào trạng thái và các ký tự được đọc bởi mỗi đầu băng. Mỗi đầu dịch chuyển một cách độc lập sang trái, sang phải hoặc đứng yên.

ĐỊNH LÝ 7.5 : Nếu L được chấp nhận bởi máy Turing k đầu đọc M 1 thì L cũng được chấp nhận bởi một máy Turing một đầu đọc M 2 nào đó.

(Phần chứng minh, xem như bài tập)