0.6 Máy turing  (Page 4/15)

Máy Turing như là một máy tính hàm số nguyên

Máy Turing cũng có thể được xem như là một máy tính của các hàm số nguyên (đi từ tập số nguyên đến tập số nguyên). Mỗi số nguyên ta viết dưới dạng số trong hệ nhất phân (unary), tức là với một số i  0 ta viết thành chuỗi 0i (gồm i chữ số 0). Nếu hàm f có k đối số i1, i2, ..., ik thì ta viết lần lượt các số nguyên này trên băng của TM ngăn cách nhau bởi 1, nghĩa là input có dạng 0i110i21 ... 10ik. Nếu TM dừng (chấp nhận hoặc không chấp nhận input) với băng 0m thì ta nói f (i1, i2, ..., ik ) = m.

Chú ý rằng ta cũng có thể tính được hàm chỉ có một đối số. Nếu f xác định với mọi bộ đối số i1, i2, ..., ik thì ta gọi f là hàm đệ qui toàn bộ. Một hàm f tính được bởi máy Turing ta gọi là hàm đệ qui bộ phận. Hàm đệ qui bộ phận tương tự như ngôn ngữ đệ qui liệt kê bởi vì nó tính được bởi máy Turing nhưng có thể không dừng với một số đối số nào đó. Hàm đệ qui toàn bộ tương tự như ngôn ngữ đệ qui vì TM sẽ dừng trên mọi input.

Thí dụ 7.2 :Thiết kế máy Turing tính toán phép trừ riêng

Ta định nghĩa phép trừ riêng (proper subtraction) như sau :

f(m, n) = m\ n =m - n nếu m  n

1. nếu m<n

. Input : 0m10n

. Output : 0 m\ n

M lặp lại việc thay thế lần lượt từng số 0 ở đầu băng bằng B rồi tiến sang phải, ra sau 1 tìm 0 và thay 0 này bằng 1. M lại chuyển sang trái cho đến khi gặp B đầu tiên thì dừng lại, trở về trạng thái bắt đầu và tiếp tục vòng lặp như trên. M dừng nếu :

i) Khi sang phải tìm 0 bên phải, M gặp B. Lúc này M đã thay n số 0 bên phải chuỗi input 0m10n thành 1 và n + 1 số 0 bên trái thành B, trường hợp này xảy ra khi trong chuỗi input có m>n. Do vậy M phải thay lại tất cả n + 1 số 1 sau thành B, và sau đó dịch trái thay trả lại một B về thành 0, cuối cùng trên băng còn lại kết quả phép trừ là m - n số 0.

ii) Khi bắt đầu một vòng lặp mới, M không tìm thấy 0 để đổi thành B, lúc này m số 0 đầu đã bị đổi thành B, trường hợp này xảy ra khi n  m. Khi đó, M thay tất cả các số 1 và 0 trên băng thành B để cho kết quả phép trừ là 0 (biểu diễn gồm toàn ký hiệu B trong hệ nhất phân).

Ta xây dựng TM như sau: M ({q0, q1, ..., q6}, {0, 1}, {0, 1, B}, , q0, B, {q6})

M sẽ bắt đầu bằng 0m10n trên băng và kết thúc với 0m\ n trên băng. Các phép chuyển trạng thái được định nghĩa như sau :

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

M thay 0 đầu băng bởi B.

2) d(q1, 0) = (q1, 0, R)

d(q1, 1) = (q2, 1, R)

M di chuyển sang phải qua 0 tìm 1.

3) d(q2, 1) = (q2, 1, R)

d(q2, 0) = (q3, 1, L)

M di chuyển sang phải vượt qua 1 đến khi gặp 0, đổi 0 thành 1.

4) d(q3, 0) = (q3, 0, L)

d(q3, 1) = (q3, 1, L)

d(q3, B) = (q0, B, R)

M dịch trái tới khi gặp B, trở về trạng thái q0 và bắt đầu một vòng lặp mới.

5) d(q2, B) = (q4, B, L)

d(q4, 1) = (q4, B, L)

d(q4, 0) = (q4, 0, L)

d(q4, B) = (q6, 0, )

Nếu ở trạng thái q2 sang phải tìm 0 để thay thành 1 nhưng chỉ gặp B thì ta xét trường hợp kết thúc i) ở trên: TM đi vào trạng thái q4 và chuyển sang trái đổi tất cả 1 thành B cho tới khi gặp một B bên trái đầu tiên. B này sẽ được thay lại thành 0 rồi M đi vào trạng thái kết thúc q6 và dừng.

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