Ngôn ngữ và hàm tính được

Ngôn ngữ được chấp nhận bởi một máy Turing được gọi là ngôn ngữ đệ qui liệt kê - recursively enumerable (r.e). Đó là một lớp ngôn ngữ rất rộng, nó thực sự chứa ngôn ngữ phi ngữ cảnh CFL và một số ngôn ngữ mà không thể xác định các thành phần một cách máy móc. Nếu L(M) là một ngôn ngữ như vậy thì bất kỳ một máy Turing nào nhận diện L(M) cũng sẽ không dừng trên một số input không thuộc L(M). Nhưng nếu một chuỗi w ∈ L(M) thì chắc chắn TM dừng, tuy nhiên TM sẽ chạy bao lâu trên input thì chúng ta không thể biết được và ta cũng không biết chắc chắn liệu TM có dừng lại hay không. Một cách thuận lợi và có ý nghĩa hơn là xét một lớp con của lớp ngôn ngữ đệ qui liệt kê, trong đó mọi ngôn ngữ đều được chấp nhận bởi ít nhất một máy Turing dừng trên mọi input. Lớp ngôn ngữ này gọi là lớp ngôn ngữ đệ qui -recursive sets.

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 0ⁱ (gồm i chữ số 0). Nếu hàm f có k đối số i₁, i₂, ..., i_k 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 0ⁱ¹10ⁱ²1 ... 10^ik. Nếu TM dừng (chấp nhận hoặc không chấp nhận input) với băng 0^m thì ta nói f (i₁, i₂, ..., i_k ) = 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ố i₁, i₂, ..., i_k 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 : 0^m10ⁿ

. 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 0^m10ⁿ 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 ({q₀, q₁, ..., q₆}, {0, 1}, {0, 1, B}, δ, q₀, B, {q₆})

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

1) d(q₀, 0) = (q₁, B, R)

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

2) d(q₁, 0) = (q₁, 0, R)

d(q₁, 1) = (q₂, 1, R)

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

3) d(q₂, 1) = (q₂, 1, R)

d(q₂, 0) = (q₃, 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(q₃, 0) = (q₃, 0, L)

d(q₃, 1) = (q₃, 1, L)

d(q₃, B) = (q₀, B, R)

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

5) d(q₂, B) = (q₄, B, L)

d(q₄, 1) = (q₄, B, L)

d(q₄, 0) = (q₄, 0, L)

d(q₄, B) = (q₆, 0, ∅)

Nếu ở trạng thái q₂ 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 q₄ 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 q₆ và dừng.

6) d(q₀, 1) = (q₅, B, R)

d(q₅, 0) = (q₅, B, R)

d(q₅, 1) = (q₅, B, R)

d(q₅, B) = (q₆, B, ∅)

Nếu ở trạng thái bắt đầu vòng lặp mới q₀ 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 q₅, xoá phần còn lại của băng rồi đi vào trạng thái kết thúc q₆ và dừng.

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

q₀0010 ⊢ B q₁010 ⊢ B0q₁10 ⊢ B01q₂0 ⊢ B0q₃11 ⊢ Bq₃011 ⊢ q₃B011 ⊢ Bq₀011 ⊢ BBq₁11 ⊢ BB1q₂1 ⊢ BB11q₂ ⊢ BB1q₄1 ⊢ BBq₄1 ⊢ Bq₄ ⊢ Bq60

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

q₀0100 ⊢ Bq₁100 ⊢ B1q₂00 ⊢ Bq₃110 ⊢ q₃B110 ⊢ Bq₀110 ⊢ BBq₅10 ⊢ BBBq₅0 ⊢ BBBBq₅ ⊢ BBBBq6