Does the Program Halt or Loop
A machine has one accumulator and a program of n instructions, numbered 0 to
n - 1. The program counter starts at 0 and the accumulator starts at 0. Each
instruction carries one signed operand:
ACC v add v to the accumulator, then move the counter on by 1
JMP v move the counter on by v, leaving the accumulator alone
NOP v move the counter on by 1 and ignore v entirely
The run ends in exactly one of three ways, and the rules are checked in this order before each instruction is executed:
1. the counter is exactly n -> HALT, print HALT and the accumulator
2. the counter is below 0 or above n -> FAULT, print FAULT and the accumulator
3. the instruction about to run has already run once -> the program will
never do anything new, so print LOOP and the accumulator as it stands
BEFORE that instruction runs a second time
``` 3 instructions: ACC 5 / JMP -1 / ACC 1
counter 0, accumulator 0 -> ACC 5, accumulator 5, counter 1 counter 1 -> JMP -1, counter 0 counter 0 has already run -> LOOP 5 ```
``` 2 instructions: JMP 5 / ACC 1
counter 0 -> JMP 5, counter 5, which is above n = 2 -> FAULT 0 ```
## What most people try first
Running the program and giving up after some large number of steps. That guesses, and it can only ever be wrong in one direction: a program that would have halted on step one million is reported as looping. This problem does not need a guess, because the question is decidable.
## Why marking each instruction once is enough
Look at what each instruction does to the counter. ACC and NOP move it on
by 1, and JMP v moves it on by v. None of the three reads the accumulator.
So the next value of the counter is a function of the counter alone, and the
accumulator is a passenger.
That means the sequence of counters is fixed from the start: 0, then
next(0), then next(next(0)), and so on. If the sequence ever reaches an
instruction it has already reached, every later counter repeats as well, and no
instruction can ever produce a different value. So the run is in a loop, and it
is in one the moment a repeat happens. Marking each instruction as it runs and
stopping on the second visit is therefore exact rather than a heuristic, and it
costs O(n) because the run executes each instruction at most once.
The accumulator still has to be reported, which is why the loop is detected during the run rather than by a separate analysis of the counter: you need the accumulator as it stood at the moment the repeat was found.
## The boundary that breaks a careless implementation
The halt test is counter == n, exactly. A JMP can carry the counter well
past n, or below 0, and that is a FAULT and not a halt: the second worked
example is precisely that. Testing counter >= n for the halt would report
HALT 0 there.
JMP 0 is legal and is an immediate loop on a single instruction, since that
instruction is about to run a second time.
## Overflow
With up to 2000 instructions and an operand as large as 10^9, the accumulator
can reach 2 * 10^12. A signed 32 bit integer stops at 2147483647, so the
accumulator must be 64 bit. The counter itself stays small, but a JMP operand
of 10^9 can push it to 10^9, which still fits in 32 bits.
## Cost
O(n) time and O(n) memory for the marks.