TAOCP 1.3.1 Exercise 20

Exercise 20. [20] Write a program that sets all 4000 memory cells equal to a HLT instruction, and then stops.

Verified: yes
Solve time: 1m39s

Let $H$ be the MIX word representing the halt instruction. In MIX notation this is a word whose $C$-byte is $5$ and whose other bytes are irrelevant, so we define it explicitly in the program as a constant

$$ H ;=; (+,0,0,0,0,5). $$

This removes any dependence on memory initialization: the value of $H$ is constructed by the program itself as an assembled constant stored in the program’s data section.

Key correction to the previous solution

The earlier argument incorrectly assumed that some memory location already contained $H$. Instead, $H$ must be explicitly defined as part of the program and then loaded into a register using a symbolic address. The MIX assembler guarantees that a constant like $H$ is materialized in memory at assembly time, so LDA H is a valid and self-contained way to obtain the required word.

Construction of the program

We use index register $rI1$ to sweep through memory locations $3999, 3998, \dots, 0$. At each step we store $H$ into the effective address $0 + rI1$.

The loop invariant is that $rA$ always contains $H$, so every store writes the correct word.

Program:

3000  ENT1 3999        ; rI1 ← 3999
3001  LDA  H           ; rA ← H (constructed constant)

3002 LOOP STA 0,1      ; M[rI1] ← rA
3003      DEC1 1       ; rI1 ← rI1 − 1
3004      J1P LOOP     ; if rI1 > 0, continue loop

3005      STA 0,1      ; store into location 0 (when rI1 = 0)
3006      HLT

H     CON  +0 +0 +0 +0 5

Correctness argument

Correct construction of $H$

The value $H = (+0,0,0,0,5)$ is explicitly defined in the program as a constant word. When LDA H is executed, the MIX machine loads this exact word into register $rA$. No external memory assumptions are used. 2. Loop coverage of all memory cells

Initially $rI1 = 3999$. Each iteration stores into address $0 + rI1$, so the sequence of writes is:

$$ 3999, 3998, \dots, 1. $$

After DEC1 1, the final iteration reaches $rI1 = 0$, which is handled explicitly by the final STA 0,1.

Thus every address $0 \le M \le 3999$ is written exactly once. 3. Correct termination condition

After storing into address $0$, DEC1 1 sets $rI1 = -1$. The test J1P LOOP fails because the index register is no longer positive, so control proceeds to HLT. 4. No reliance on preexisting memory content

The value written to memory is entirely determined by the program constant $H$, not by any initial memory state.

Conclusion

The program explicitly constructs the halt instruction word $H$, loads it into a register, and uses indexed addressing to write it into all 4000 memory cells exactly once before halting.