0.6 Máy turing  (Page 8/15)

6) d([q2, An, B], B) = ([q2, B, B], An, L)

Cuối cùng, tất cả các ký hiệu không trống trên băng đã được chuyển dịch sang phải 2 ô. Lúc đó nó sẽ được chuyển sang một trạng thái nào đó (có thể quay về trái, trở về đầu băng) để thực hiện một chức năng khác.

Chương trình con (subroutines)

Cũng giống như một chương trình máy tính hiện đại, máy Turing có thể đóng vai trò tương tự như bất kỳ một kiểu chương trình con nào trong ngôn ngữ lập trình bao gồm thủ tục đệ qui hoặc có tham số. Ý tưởng chung là ta viết một phần chương trình của TM như là một chương trình con. Nó sẽ được thiết kế có chứa một trạng thái khởi đầu và một trạng thái trở về, trạng thái trở về là trạng thái không có phép chuyển kế tiếp và nó sẽ đóng vai trò là trạng thái khởi đầu của một TM khác hoặc là một trạng thái nào đó trong một TM khác. Nghĩa là từ trạng thái trở về của TM này ta tiếp tục các phép chuyển của một TM khác, sự kiện này có ý nghĩa như là gọi một chương trình con khác hoặc tiếp tục thực hiện chương trình cấp trên. Lưu ý, các trạng thái của chương trình con phải phân biệt với chương trình cấp trên của nó.

Thí dụ 7.7 :Thiết kế TM thực hiện phép nhân 2 số nguyên m, n.

. Input : 0m10n

. Output : 0m  n

M bắt đầu với 0m10n trên băng và kết thúc với 0m  n trên băng được bao quanh bởi các Blank.

Ý tưởng chung là đặt thêm số 1 sau 0m10n rồi chép khối n số 0 sang phải m lần mỗi lần xoá một con 0 bên trái của 0m. Ta được kết quả cuối cùng là 10n10m  n . Bây giờ ta chỉ việc xoá 10n1 ta sẽ được kết quả 0m  n .

Phần chính của giải thuật trên là thủ tục COPY để chép n số 0 sang phải. Thủ tục này được xác định bằng các hàm chuyển sau:

Ở trạng thái q1 nhìn thấy 0, M đổi 0 thành 2 và đi vào trạng thái q2. Ở trạng thái q2, M dịch phải tới Blank viết 0 rồi dịch trái trong trạng thái q3. Khi ở trạng thái q3 mà gặp 2, M đi vào trạng thái q1 để tiếp tục lặp lại quá trình trên cho tới khi gặp 1. Trạng thái q4 được dùng để biến đổi 2 thành 0 và thủ tục dừng tại q5.

Để làm đầy đủ chương trình ta phải thêm các trạng thái để biến đổi hình thái khởi đầu q00m10n thành B0m-11q10n1. Tức là ta cần ba qui tắc:

d(q0, 0) = (q6, B, R)

d(q6, 0) = (q6, 0, R)

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

Sau đó, ta lại thêm các phép chuyển và trạng thái cần thiết để biến đổi từ hình thái Bi0m-i1q50n10n  i thành Bi+10m-i-11q10n10n  i là trạng thái bắt đầu lại việc COPY, đồng thời kiểm tra i = m hay không (khi tất cả các 0 của 0m đã bị xoá). Nếu i = m thì 10n1 bị xoá và quá trình tính toán sẽ dừng ở trạng thái q12. Các hàm chuyển bổ sung như sau :

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

Sau đây, ta sẽ xét thêm một số dạng khác của máy Turing, chúng có vẻ phức tạp và tinh vi hơn, song thực tế chúng cũng đều tương đương với mô hình TM cơ bản đã định nghĩa ở trên.

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 :