Trạng thái
Số bước
Ký hiệu trên băng
Tình trạng

Trạng thái Đọc Ghi Di chuyển Trạng thái tiếp theo

Tìm hiểu thêm về máy Turing

Mô phỏng máy Turing

Máy Turing là chiếc máy tính đơn giản nhất có thể có: một đầu đọc đọc một ký hiệu trên một băng dài vô tận, ghi một ký hiệu, di chuyển một ô sang trái hoặc sang phải và đổi trạng thái, theo một bảng quy tắc ngắn. Alan Turing phát minh ra nó vào năm 1936, và về nguyên tắc mọi việc máy tính của bạn làm đều có thể được thực hiện theo cách này. Hãy tự viết quy tắc hoặc tải một ví dụ, nhấn Chạy và xem băng thay đổi từng bước, với sơ đồ toàn bộ lịch sử của nó ở bên dưới. Hãy chọn một chương trình hoặc tự viết, nhập đầu vào rồi nhấn Chạy, hoặc nhấn Từng bước để theo dõi từng quy tắc một; Lùi lại hoàn tác một bước. Mỗi dòng của chương trình là một quy tắc: trạng thái, ký hiệu đọc, ký hiệu ghi, hướng di chuyển (L, R hoặc N nếu không di chuyển) và trạng thái tiếp theo, ví dụ A 0 -> 1 R B. Dùng _ cho ô trống. Máy bắt đầu ở trạng thái của quy tắc đầu tiên, tại ký hiệu đầu tiên của đầu vào, và dừng ở H, accept hoặc reject, hoặc khi không có quy tắc nào phù hợp. Sơ đồ cho thấy băng sau mỗi bước, từ trên xuống dưới.

Cách nó hoạt động

  1. Hãy chọn một chương trình mẫu hoặc viết các quy tắc như A 0 -> 1 R B, mỗi dòng một quy tắc, rồi nhập đầu vào.
  2. Nhấn Chạy để xem đầu đọc di chuyển, hoặc Từng bước để theo dõi từng quy tắc một; Lùi lại hoàn tác một bước.
  3. Xem trạng thái, số bước và ký hiệu trên băng ở các ô thông tin, và lịch sử của băng trong sơ đồ.

Cách máy hoạt động

Tại mỗi thời điểm, máy ở một trong vài trạng thái và đầu đọc của nó nằm trên một ô của băng. Quy tắc cho trạng thái đó và ký hiệu dưới đầu đọc cho biết ba điều: ghi ký hiệu nào vào ô, di chuyển sang trái, sang phải hay đứng yên, và chuyển sang trạng thái nào tiếp theo. Đó là toàn bộ cỗ máy. Nó dừng khi đến một trạng thái dừng, chẳng hạn H, accept hoặc reject, hoặc khi không có quy tắc nào phù hợp. Một chương trình cộng 1 vào một số nhị phân chỉ cần chín quy tắc như vậy.

Hải ly bận rộn

Trong các máy có n trạng thái, khởi động trên một băng trống, máy nào ghi được nhiều số 1 nhất trước khi dừng? Tibor Radó đặt ra câu hỏi này vào năm 1962. Các nhà vô địch được gọi là hải ly bận rộn, và chúng tăng nhanh hơn bất kỳ hàm nào mà máy tính có thể tính. Hai trạng thái cho 4 số 1 trong 6 bước, ba trạng thái cho 6 số 1, bốn trạng thái cho 13 số 1 trong 107 bước. Nhà vô địch năm trạng thái, được tìm thấy năm 1989, ghi 4.098 số 1 trong 47.176.870 bước, và năm 2024 một nhóm hợp tác trực tuyến đã chứng minh bằng toán học được máy tính kiểm chứng rằng không có máy năm trạng thái nào khác dừng mà lại chạy lâu hơn.

Câu hỏi thường gặp

Làm thế nào để viết một quy tắc?

Mỗi dòng một quy tắc: trạng thái hiện tại, ký hiệu nó đọc, ký hiệu cần ghi, hướng di chuyển (L, R hoặc N) và trạng thái tiếp theo, ví dụ A 0 -> 1 R B. Mũi tên và dấu phẩy là tùy chọn. Dùng _ cho ô trống và # cho chú thích. Máy bắt đầu ở trạng thái của quy tắc đầu tiên; trạng thái tiếp theo có tên H hoặc halt sẽ dừng máy, còn accept và reject dừng máy kèm một kết luận.

Máy Turing có thật sự tính được mọi thứ không?

Mọi thứ mà bất kỳ máy tính nào có thể tính, nếu có đủ băng và thời gian: đó là luận đề Church–Turing. Máy Turing không có giới hạn bộ nhớ, nên theo nghĩa đó nó mạnh hơn bất kỳ máy tính thực nào, dù chậm hơn rất nhiều. Điều nó không làm được là trả lời mọi câu hỏi: Turing đã chứng minh rằng không có máy nào có thể quyết định, với mọi chương trình và đầu vào, liệu chương trình đó có dừng hay không.

Tại sao bộ đếm không bao giờ dừng?

Các quy tắc của nó không bao giờ dẫn tới một trạng thái dừng. Nó liên tục cộng 1 vào một số nhị phân ở đầu bên phải của băng rồi đi ngược lại, nên con số lớn lên mãi mãi. Bài toán dừng của Turing nói rằng không có phương pháp tổng quát nào có thể cho biết, với mọi máy, liệu máy đó có dừng hay không; với bộ đếm đơn giản này bạn có thể thấy điều đó, nhưng với một số máy chỉ có sáu trạng thái thì đến nay vẫn chưa ai biết.

Làm sao hải ly bận rộn năm trạng thái có thể chạy 47 triệu bước ở đây?

Băng được lưu dưới dạng một mảng gọn có thể mở rộng về cả hai phía, và ở chế độ nhanh nhất ứng dụng chạy hàng trăm nghìn bước giữa hai lần cập nhật màn hình, nên toàn bộ quá trình chỉ mất vài giây trên một trình duyệt hiện đại. Sơ đồ chỉ ghi lại 400 bước đầu tiên, vì một hình ảnh 47 triệu hàng sẽ không vừa với bất kỳ màn hình nào.

Có dữ liệu nào được gửi lên máy chủ không?

Không. Chương trình chạy trong trình duyệt của bạn, và chương trình cùng đầu vào của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.

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.

Tới trình chỉnh sửa