Simulate a tiny programming language, and see why a step limit can only ever answer "halted" or "still running".
What to build
A program that runs a counter-machine program for at most k steps.
Requirements
- Instructions:
INC r,DEC r(not below 0),JZ r L(jump to line L if register r is 0),JMP L,HALT. Lines are numbered from 0; registers are 0 to 3. - Every executed instruction, HALT included, is one step. Running past the last line also halts.
- Print
halt after S steps: r0 r1 r2 r3orstill running after k steps.
Input
Line 1: the four starting register values. Line 2: k. Line 3: m. Then m instructions.
Output
One line.
Constraints
m ≤ 30; k ≤ 10⁵.
Example
Input:
2 3 0 0
100
5
JZ 1 4
DEC 1
INC 0
JMP 0
HALT
Output:
halt after 14 steps: 5 0 0 0
Why it works
Counter machines can compute anything a Turing machine can, so whether they halt is undecidable; running them for k steps answers only for those k steps.
Examples
2 3 0 0 100 5 JZ 1 4 DEC 1 INC 0 JMP 0 HALT
halt after 14 steps: 5 0 0 0
0 0 0 0 50 1 JMP 0
still running after 50 steps
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a program counter and four registers; execute one instruction per step.
Hint 2
Before each step: if the counter is past the last line the program has halted; if the step count has reached k, it is still running.
Solution
Show one correct solution (try it yourself first)
regs = list(map(int, input().split()))
k = int(input())
program = [input().split() for _ in range(int(input()))]
pc = steps = 0
while True:
if pc >= len(program):
print(f"halt after {steps} steps:", *regs)
break
if steps == k:
print(f"still running after {k} steps")
break
op = program[pc]
steps += 1
if op[0] == "HALT":
print(f"halt after {steps} steps:", *regs)
break
if op[0] == "INC":
regs[int(op[1])] += 1
pc += 1
elif op[0] == "DEC":
r = int(op[1])
regs[r] = max(0, regs[r] - 1)
pc += 1
elif op[0] == "JZ":
pc = int(op[2]) if regs[int(op[1])] == 0 else pc + 1
elif op[0] == "JMP":
pc = int(op[1])