Giải thích máy Turing
Năm 1936, khi máy tính điện tử còn chưa ra đời, nhà toán học 24 tuổi Alan Turing đặt câu hỏi: một phép tính mang tính cơ học nghĩa là gì? Câu trả lời của ông là một cỗ máy tưởng tượng đơn giản đến mức khó có thể làm ít hơn được nữa: nó đọc và ghi ký hiệu trên một băng, mỗi lần một ô, theo một bảng quy tắc cố định. Hóa ra cỗ máy ấy định nghĩa chính khái niệm tính toán, và nó cho thấy có những câu hỏi mà không một máy tính nào có thể trả lời được.
Câu hỏi của Turing
Năm 1928, David Hilbert hỏi liệu có một thủ tục cơ học nào quyết định được, với mọi mệnh đề toán học, liệu nó có thể được chứng minh hay không: đó là Entscheidungsproblem. Để trả lời, phải có ai đó nói chính xác thủ tục cơ học là gì. Trong bài báo năm 1936 On Computable Numbers, Turing hình dung một người thư ký làm việc bằng bút chì và giấy, rồi rút gọn công việc xuống những bước nhỏ nhất: nhìn một ký hiệu, thay đổi nó, chuyển sang ký hiệu bên cạnh và nhớ một chút về việc mình đang làm. Kết quả là máy Turing.
Cỗ máy
Máy Turing có một băng được chia thành các ô, dài vô tận về cả hai phía, mỗi ô chứa một ký hiệu, thường là ô trống. Một đầu đọc nằm trên một ô và máy ở một trong hữu hạn trạng thái. Một bảng quy tắc cho biết, với mỗi trạng thái và mỗi ký hiệu mà đầu đọc có thể đọc, ký hiệu cần ghi, hướng di chuyển và trạng thái tiếp theo. Máy áp dụng một quy tắc mỗi bước. Khi vào một trạng thái dừng, nó dừng lại, và những gì còn lại trên băng là câu trả lời của nó.
Chương trình là bảng quy tắc
Mỗi bảng quy tắc là một chương trình. Để cộng 1 vào một số nhị phân, máy đi đến đầu bên phải của số, rồi di chuyển sang trái và biến các số 1 thành 0 cho đến khi gặp một số 0 hoặc một ô trống, rồi biến nó thành 1. Để kiểm tra một từ có phải là chuỗi đối xứng hay không, máy xóa ký hiệu đầu tiên, ghi nhớ nó trong trạng thái của mình, chạy đến đầu kia và kiểm tra xem ký hiệu cuối có khớp không, rồi lặp lại. Những chương trình dài, chẳng hạn chương trình nhân hay sắp xếp, đều được xây từ chính vài loại quy tắc đó.
Máy vạn năng
Ý tưởng quan trọng nhất của Turing là bản thân bảng quy tắc cũng có thể được ghi lên băng. Một máy Turing vạn năng đọc mô tả của bất kỳ máy nào khác cùng đầu vào của nó, rồi bắt chước nó từng bước. Vì vậy một cỗ máy cố định có thể chạy mọi chương trình: đây là nguyên lý đằng sau mọi máy tính lưu trữ chương trình, nơi phần mềm chỉ là dữ liệu trong bộ nhớ. Mọi hệ thống có thể bắt chước một máy Turing vạn năng đều được gọi là Turing đầy đủ, bao gồm mọi ngôn ngữ lập trình, Trò chơi của sự sống của Conway và ô tô-mát tế bào Luật 110.
Luận đề Church–Turing
Cùng năm đó, Alonzo Church mô tả sự tính toán bằng phép tính lambda của ông, và hóa ra hai định nghĩa tính được đúng cùng những hàm như nhau. Mọi mô hình sau này cũng vậy, từ máy thanh ghi đến bộ xử lý hiện đại. Luận đề Church–Turing phát biểu rằng mọi thứ có thể tính được bằng một thủ tục từng bước đều có thể tính được bằng máy Turing. Nó không thể được chứng minh, vì “thủ tục từng bước” là một khái niệm không hình thức, nhưng chưa từng có phản ví dụ nào được tìm thấy.
Bài toán dừng
Sau đó Turing chỉ ra rằng có những câu hỏi không có câu trả lời cơ học. Giả sử có một máy có thể quyết định, với mọi chương trình và đầu vào, liệu chương trình đó cuối cùng có dừng hay không. Hãy xây dựng một chương trình mới hỏi bộ quyết định này về chính nó rồi làm điều ngược lại: nếu được cho biết là nó dừng, nó lặp mãi mãi, còn nếu được cho biết là nó lặp, nó dừng. Câu trả lời nào cũng sai, nên bộ quyết định không thể tồn tại. Bài toán dừng là không quyết định được, và cùng với nó là Entscheidungsproblem: không thuật toán nào giải quyết được mọi câu hỏi toán học.
Hải ly bận rộn
Năm 1962, Tibor Radó biến bài toán dừng thành một trò chơi: trong tất cả các máy có n trạng thái và các ký hiệu 0 và 1 dừng lại khi khởi động trên một băng trống, máy nào ghi được nhiều số 1 nhất, và một máy như vậy có thể chạy bao nhiêu bước? Những con số này, các giá trị hải ly bận rộn, tăng nhanh hơn mọi hàm khả tính, vì một cách tính được chúng sẽ giải được bài toán dừng. Các giá trị đã biết là 6, 21 và 107 bước cho hai, ba và bốn trạng thái; với năm trạng thái, nhà vô địch của Heiner Marxen và Jürgen Buntrock chạy 47.176.870 bước, một giá trị được nhóm hợp tác trực tuyến bbchallenge chứng minh năm 2024 bằng một chứng minh được máy tính kiểm chứng. Với sáu trạng thái, người ta biết những máy chạy nhiều bước hơn mức có thể viết ra bằng ký hiệu thông thường.
Khám phá
Hãy mở trình mô phỏng máy Turing để chạy tám chương trình có sẵn hoặc tự viết chương trình của bạn. Theo dõi đầu đọc từng bước và xem quy tắc nào được áp dụng, quan sát bộ đếm không bao giờ dừng, kiểm tra chuỗi đối xứng và chạy các hải ly bận rộn: 107 bước của nhà vô địch bốn trạng thái vừa trong sơ đồ, còn 47 triệu bước của nhà vô địch năm trạng thái mất vài giây ở tốc độ nhanh nhất.
Câu hỏi thường gặp
Máy Turing đã từng được chế tạo chưa?
Không đúng như Turing mô tả, vì băng của nó dài vô tận, nhưng ngay sau đó ý tưởng này được tiếp nối bởi những máy tính lưu trữ chương trình thực sự, mà chính Turing đã góp phần thiết kế sau Chiến tranh thế giới thứ hai. Từ đó, những người chơi nghiệp dư đã chế tạo các mô hình hoạt động được bằng gỗ, LEGO và thậm chí cả trong Trò chơi của sự sống, tất cả đều có băng hữu hạn, đủ cho mọi phép tính có kết thúc.
Sự khác nhau giữa số bước 14 và 21 với ba trạng thái là gì?
Có hai câu hỏi hải ly bận rộn: nhiều số 1 được ghi nhất và nhiều bước được chạy nhất. Với ba trạng thái, máy trong trình mô phỏng ghi tối đa sáu số 1 trong 14 bước, còn một máy ba trạng thái khác chạy tối đa 21 bước nhưng chỉ để lại năm số 1. Với hai, bốn và năm trạng thái, một máy thắng cả hai.
Turing đầy đủ có nghĩa là mạnh không?
Nó có nghĩa là có khả năng tính mọi thứ khả tính, nếu có đủ thời gian và bộ nhớ, và điều đó không nói gì về tốc độ. Một máy Turing cần rất nhiều bước cho phép tính số học đơn giản, và một số hệ thống là Turing đầy đủ gần như do tình cờ, chẳng hạn các trò chơi bài, công thức bảng tính và redstone trong Minecraft.
Tại sao máy tính không thể chỉ chạy chương trình để xem nó có dừng không?
Chạy thử sẽ cho thấy một chương trình dừng, nếu nó dừng, nhưng nếu nó chưa dừng thì bạn không thể biết liệu nó sẽ không bao giờ dừng hay chỉ cần thêm thời gian. Chứng minh của Turing cho thấy không có phương pháp khéo léo hơn nào hiệu quả với mọi chương trình, dù với nhiều chương trình cụ thể thì câu hỏi này có thể trả lời được.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở trình mô phỏng máy Turing