Theory: Run programs with a step limit

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 r3 or still 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

Example 1 · Input
2 3 0 0
100
5
JZ 1 4
DEC 1
INC 0
JMP 0
HALT
Expected output
halt after 14 steps: 5 0 0 0
Example 2 · Input
0 0 0 0
50
1
JMP 0
Expected output
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])

Lesson: Decidability and the halting problem →