A Program That Rewrites Itself
A machine has an accumulator and a program of n instructions numbered from 0.
The counter and the accumulator both start at 0.
ADD v add v to the accumulator, then move the counter on by 1
JMP v move the counter on by v
SET i v replace the OPERAND of instruction i with v, then move the counter
on by 1. Instruction i is guaranteed to be an ADD or a JMP, and its
opcode is left alone.
HLT stop
The machine performs at most s steps, and one step is: if the counter is
outside 0 to n - 1, stop and report FAULT; otherwise execute the
instruction there. Print the outcome word, one of HALT, FAULT or
RUNNING, and then the accumulator, separated by a single space.
``` n = 4, s = 100: SET 2 0 / JMP 2 / JMP -1 / HLT
SET 2 0 rewrites instruction 2 from JMP -1 to JMP 0, counter 1. JMP 2 sets the counter to 3, which is the HLT, so instruction 2 is never reached and the rewrite never matters. -> HALT 0 ```
``` n = 3, s = 100: SET 1 7 / ADD 0 / HLT
SET 1 7 rewrites instruction 1 from ADD 0 to ADD 7, counter 1. ADD 7 now adds 7 rather than 0. -> HALT 7 ```
## What most people try first
Reusing the loop detection from #2164. There the counter never read anything
that could change, so a repeated instruction proved the run was stuck. Here a
SET can rewrite the very JMP that is about to run, so the same instruction
reached twice can send control two different places. Marking instructions and
stopping on a repeat gives a wrong LOOP on a program that goes on to halt, so
this problem has a step budget instead and reports RUNNING honestly.
The second common slip is decoding the program once into a fixed table and then running from a separate copy. Every read of an operand must see the latest write to it, which means one mutable table and no second copy of the operands.
## Why the budget is the only honest answer
To decide looping you would have to find a repeat of the whole machine state,
which here is the counter together with every operand in the program. That is
n numbers of up to 10^9 in magnitude, so the state space is far beyond
enumeration, and the question of whether such a program halts is exactly the
kind of question a fixed budget exists to sidestep. Stating the budget in the
input is what makes the problem answerable.
## The order inside a SET, which is where the bug lives
SET i v writes to instruction i and then moves the counter on by one. Two
cases are worth separating:
i is the SET itself the opcode stays SET, and the guarantee in the
statement rules this out: i is always an ADD or a JMP
i is the NEXT instruction the write lands before that instruction runs, so the
new operand is the one used
i is an earlier JMP the write takes effect for every later visit, which is
how a program can escape a loop it is already in
A declared test has a SET that rewrites a JMP the run later returns to, so a
solution that caches operands fails it while passing the straight-line cases.
## Overflow
The accumulator is a sum of at most s operands of magnitude up to 10^9,
with s up to 10^5, so it can reach 10^14. A signed 32 bit integer stops
at 2147483647, so the accumulator must be 64 bit. Note that the declared test
which adds 10^9 twice reaches 2000000000, and that FITS in 32 bits, so it
is not tagged as an overflow: only the larger sums need the width.
## Cost
O(n + s) time and O(n) memory.