Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Busy Beaver nâng cao: dừng hay chạy tiếp

    Busy Beaver nâng cao: dừng hay chạy tiếp

    Tiếp tục với máy Busy Beaver (bảng chữ {0, 1}, ô trắng 0, băng khởi tạo toàn 0, có trạng thái dừng halt).

    Hàm Busy Beaver Σ(k) — số dấu 1 tối đa mà một máy k trạng thái dừng có thể để lại — là không tính được (uncomputable). Nhưng với một máy cụ thể và giới hạn bước, ta luôn mô phỏng được.

    Mô phỏng máy tối đa limit bước:

    • Nếu máy dừng (vào halt hoặc hết luật): in HALT <số_bước> <số_dấu_1>.
    • Nếu chưa dừng: in RUN <số_bước> <số_dấu_1>.

    Ví dụ (BB-3, Σ(3)=6): máy 3 trạng thái dừng sau 14 bước để lại 6 dấu 1 → HALT 14 6.

    • Định dạng đầu vào:

      Dòng 1: n số luật. n dòng: q a ns wr d (ký hiệu 0/1). Dòng tiếp: start halt. Dòng tiếp: số nguyên limit.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 40; 1 ≤ limit ≤ 1000000.

    • Định dạng đầu ra:

      HALT <bước> <số_1> nếu dừng, ngược lại RUN <bước> <số_1>.

    Ví dụ:

    Đầu vào:

    6
A 0 B 1 R
A 1 H 1 R
B 0 C 0 R
B 1 B 1 R
C 0 C 1 L
C 1 A 1 L
A H
1000

    Đầu ra:

    HALT 14 6

    Giải thích:

    Busy Beaver 3 trạng thái: dừng sau đúng 14 bước, để lại 6 dấu 1 → `HALT 14 6`.

    Đang tải editor...