Bài toán dừng tổng quát là không quyết định được (undecidable). Tuy nhiên, phiên bản có giới hạn bước thì quyết định được: ta chỉ cần mô phỏng máy tối đa limit bước.
Cho máy Turing xác định và một băng đầu vào. Hãy xác định máy có dừng trong không quá limit bước hay không (máy dừng khi không có luật áp dụng).
YES và số bước.NO.Ví dụ: máy q0 a -> q0 a R, băng aa, limit=100: dừng sau 2 bước → YES 2.
Dòng 1: n số luật.
n dòng: q a ns wr d.
Dòng tiếp: start.
Dòng tiếp: số nguyên limit.
Dòng cuối: chuỗi băng đầu.
1 ≤ n ≤ 50; 1 ≤ limit ≤ 1000000; độ dài băng ≤ 100.
YES <số_bước> nếu dừng trong giới hạn, ngược lại NO.
Ví dụ:
Đầu vào:
1
q0 a q0 a R
q0
100
aa
Đầu ra:
YES 2
Giải thích:
Đang tải editor...