solution

Nhiều trình thông dịch trung gian (bytecode interpreter) mô phỏng một máy thanh ghi (register machine) đơn giản với các lệnh nhảy có điều kiện để thực hiện vòng lặp và rẽ nhánh.

Chương trình gồm $n$ dòng lệnh đánh số $1..n$. Các thanh ghi được đặt tên là chuỗi chữ cái thường độ dài từ 1 đến 10, khởi tạo ngầm định bằng $0$ khi được nhắc đến lần đầu. Tập lệnh:

• SET r v: gán thanh ghi r := v (v là hằng số nguyên).
• ADD r1 r2: r1 := r1 + r2.
• SUB r1 r2: r1 := r1 - r2.
• JMP L: nhảy tới dòng số L.
• JZ r L: nếu r = 0 thì nhảy tới dòng L, ngược lại thực hiện tiếp dòng kế tiếp.
• JNZ r L: nếu r \ne 0 thì nhảy tới dòng L, ngược lại thực hiện tiếp dòng kế tiếp.
• HALT: dừng chương trình.

Chương trình bắt đầu chạy tại dòng $1$. Cho trước giới hạn số bước thực thi tối đa $S$. Có ba khả năng xảy ra:

1. Dừng bình thường: chương trình thực hiện HALT trong vòng không quá $S$ bước (mỗi lần thực hiện một lệnh tính là một bước, kể cả HALT).
2. CRASH: tại một thời điểm nào đó (trước khi vượt quá $S$ bước), con trỏ lệnh (program counter) rơi ra ngoài phạm vi $[1, n]$ — do một lệnh JMP/JZ/JNZ nhảy tới dòng không tồn tại, hoặc do lệnh cuối cùng ($n$) không phải HALT/lệnh nhảy nên con trỏ tự động tăng vượt quá $n$.
3. TIMEOUT: chương trình chạy đủ $S$ bước mà vẫn chưa HALT và cũng chưa CRASH.

Yêu cầu: xác định chương trình rơi vào trường hợp nào; nếu dừng bình thường, in ra giá trị cuối cùng của mọi thanh ghi đã từng được nhắc đến (dù ở vai trò r, r1 hay r2 trong bất kỳ lệnh nào).