The -th problem is to solve all Hanoi instances up to instance . Following our general rule, we represent the dynamic environment for task on the -th task tape, allocating addresses for each peg, to store the order and the sizes of its current disks, and a pointer to its top disk (0 if there isn't one).
We represent pegs by numbers 1, 2, 3, respectively. That is, given an instance of size , we push onto data stack ds the values . By doing so we insert substantial, nontrivial prior knowledge about the fact that it is useful to represent each peg by a symbol, and to know the problem size in advance. The task is completely defined by ; the other 3 values are just useful for the following primitive instructions added to the programming language of Section A: Instruction mvdsk() assumes that are represented by the first three elements on data stack ds above the current base pointer (Section A.1). It operates in the obvious fashion by moving a disk from peg to peg . Instruction xSA() exchanges the representations of and , xAD() those of and (combinations may create arbitrary peg patterns). Illegal moves cause the current program prefix to halt. Overall success is easily verifiable since our objective is achieved once the first two pegs are empty.