Giới thiệu về Máy Turing

Năm 1936, nhà toán học thiên tài người Anh, Alan Turing, đã lên ý tưởng cho một chiếc máy tính số hiện đại. Ý tưởng này của ông có ý nghĩa còn quan trọng hơn nhiều so với việc xây dựng một chiếc máy tính vật lý cụ thể. Thật vậy, máy Turing là mô hình toán học cho máy tính tổng quát, là nền tảng của quá trình xử lý của máy tính hiện đại [1]-[3].

Công cụ thử nghiệm của Turing, được ông gọi là "máy tính đa năng", là một chiếc máy rất đơn giản. Về cơ bản, máy Turing có khả năng đọc và ghi các ký hiệu 1 hay 0 trên cuộn giấy dài. Nó chỉ có thể thực hiện một hành động mỗi lúc, đọc hay ghi 1 ký hiệu, có thể nhớ việc đã làm, và với thời gian không giới hạn nó có thể thực hiện vô số hành động.

Turing đã tạo ra "một chiếc máy có thể tái hiện một cách chính xác hành vi của bất kỳ máy tính nào khác". Bất kỳ tính toán nào, dù phức tạp đến đâu, đều có thể phân thành một loạt các bước đơn giản riêng rẽ – thuật toán hay chương trình – và được thực hiện với máy Turing. Điều này có ý nghĩa: "Về nguyên tắc tất cả máy tính số đều tương đương nhau; bất kỳ máy nào có thể đếm, ghi nhận và làm theo các câu lệnh đều có thể thực hiện bất kỳ chức năng tính toán nào". Yêu cầu thực tế duy nhất đối với chiếc máy tính đa năng là kích thước bộ nhớ và tốc độ mà nó có thể thực hiện các phép tính và truyền kết quả. Với bộ nhớ đủ lớn và tốc độ đủ nhanh, phát minh của Turing hàm ý một máy tính đơn với chương trình phần mềm có thể đảm đương mọi việc đang được thực hiện bởi tất cả máy tính vật lý khác trên thế giới hiện nay.

Bỏ qua các yếu tố phần cứng của công nghệ hiện hành, các bài toán được giải trên máy tính phải có thuật toán để xử lý và theo Alan Turing, tất cả các thuật toán đều có thể mô tả lại trên mô hình máy Turing, vậy việc đánh giá các thuật toán trên máy Turing sẽ cho kết quả chính xác và công bằng nhất.

1.1 Khái niệm máy Turing

Khái niệm của máy Turing dựa trên ý tưởng của một người đã thực hiện một thủ tục rất rõ ràng bằng cách thay đổi những nội dung của một băng giấy vô hạn. Trên băng giấy đó được phân thành các ô vuông có thể chứa một trong những tập hợp hữu hạn các ký hiệu. Người này cần phải nhớ một trong các tập trạng thái hữu hạn và một thủ tục được trình bày trong nhiều bước cơ bản, ví dụ:

“Nếu trạng thái của bạn là 1 và kí hiệu bạn đang thấy là 0, thì hãy thay thế nó bằng 1, di chuyển sang phải, và chuyển sang trạng thái 2.”

Mô hình máy Turing (MT) ở hình 1.1 gồm một bộ điều khiển với tập hữu hạn thạng thái q và một đầu đọc/ghi (head), chuyển động trên một băng vô hạn (staionary tape) cả về hai phía. Băng được chia thành từng ô, mỗi ô chứa một ký hiệu thuộc một bảng ký hiệu hữu hạn G. Tại thời điểm bắt đầu hoạt động, dữ liệu vào của MT là dãy ký tự thuộc G, được ghi trên các ô liền nhau của băng, các ô còn lại của băng ghi ký hiệu trắng B, đầu đọc nhìn ký tự bên trái nhất của dãy ký tự vào và bộ điều khiển ở một trạng thái khởi đầu q0 sau đó có thể chuyển sang các trạng thái tiếp theo. Mỗi bước chuyển của máy Turing, phụ thuộc vào ký hiệu do đầu đọc/ghi được từ băng dữ liệu và trạng thái của bộ điều khiển, máy sẽ thực hiện các bước sau:

• Ghi một ký hiệu mới trên băng tại ô đang duyệt (nghĩa là thay ký hiệu đọc được trên băng bằng ký hiệu nào đó).
• Dịch chuyển đầu đọc/ghi (sang trái (L), sang phải (R) hoặc đứng yên (E)).
• Chuyển sang trạng thái tiếp theo

Các thao tác có thể của một máy Turing (Atomic operations)

• Đọc (xác định) kí hiệu hiện tại mà đầu đọc đang trỏ tới
• Viết một kí hiệu lên ô vuông hiện tại mà đầu đọc dang trỏ tới (sau khi xóa lần đầu tiên kí hiệu vừa được ghi ở đó)
• Di chuyển băng sang trái một ô
• Di chuyển băng sang phải một ô
• Thay đổi trạng thái
• Ngắt

1.2 Biểu diễn máy Turing bằng các mô tả hiện thời

Một cách mô tả trạng thái của máy Turing MT là sử dụng dãy {α q β}, trong đó q là trạng thái hiện thời của MT; α và β lần lượt là nội dung có trên băng không tính ký hiệu B, được tính từ đầu bên trái và đầu bên phải băng.

 Ký hiệu dưới đầu R/W là a1 và trạng thái hiện thời của MT là q2. Những ký hiệu khác B là dãy a4a1a2a3 được ghi ở bên trái của q2 và những ký hiệu khác dấu B ở bên phải của a1 là a2a4a3. 

1.3 Ứng dụng của máy Turing trong việc đánh giá về độ phức tạp của thuật toán

Thuật toán là một trong những khái niệm quan trọng nhất trong tin học. Chúng ta có thể xem thuật toán là một công cụ dùng để giải bài toán được xác định trước. Việc nghiên cứu về thuật toán và độ phức tạp của thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải chính xác và phù hợp với điều kiện thực tế (điều kiện về công nghệ và chi phí bộ nhớ, thời gian). Nếu hướng dẫn giải sai hoặc không phù hợp thì máy tính không thể giải đúng được bài toán hoặc lãng phí tài nguyên. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự nhất định sao cho sau khi thực hiện dãy thao tác ấy, từ input của bài toán, ta nhận được output cần tìm. Đối với một thuật toán điều rất quan tâm đến đó chính là độ phức tạp của nó, đánh giá càng chính xác độ phức tạp của thuật toán sẽ giúp cho quá trình lựa chọn và sử dụng.

Trước khi có máy tính điện tử Alan Turing đã trình bày các mô hình máy Turing vào năm 1936 dành cho các thí nghiệm tưởng tượng để tìm hiểu giới hạn tính toán trên máy móc. Tuy không trực tiếp ảnh hưởng tới việc chế tạo máy tính điện tử nhưng máy Turing là một công cụ đo sự hiệu quả của thuật toán của một bài toán cụ thể. Vì vậy, có thể nói, mỗi thuật toán là một máy Turing.

Độ phức tạp thuật toán được đánh giá bằng máy Turing theo hai tiêu chí là: Thời gian (số nhịp làm việc của máy Turing) và bộ nhớ (số ô nhớ cần sử dụng trong quá trình máy làm việc).

• Thời gian (số nhịp làm việc của máy Turing): là số lần dịch chuyển của đầu đọc trên băng.
• Bộ nhớ (số ô nhớ cần sử dụng trong quá trình máy làm việc): là số ô trên bang mà máy Turing ghi các kí tự trong khi xử lý.

Cùng một bài toán, nếu có nhiều thuật toán giải được thì mỗi thuật toán đó có thể có độ phức tạp khác nhau. Nhiệm vụ của người lập trình là tìm ra được thuật toán có độ phức tạp càng thấp càng tốt.