Why, there is a well-known approach to having constant-size, small opcodes: a data stack. The only non-constant size instruction would be the one that puts an immediate argument onto the stack. Jumps would pop the target address off the stack, too. The stack should be the width of the ALU, say, 32 bit, while the machine codes could be half a byte, like here.
I'm very surprised this smallest machine is not a stack machine.
Another way could be to use registers, possibly just one register. Like in old machines that had an accumulator, which was implied. So „Add x“ adds x to the accumulator.
In some sense, there is already a register file in the proposed VM, the whole memory.
Another, related way, to reduce instruction size is to not allow all operands to be 16 bit, that is, have some registers that are more „special“ than others. For example, say the first 16 memory locations are special. Then it’s possible to have a
Opcode, arg1, arg2, arg3
Encoding using 4 bits each, for 16 bit instructions. The problem is that some instructions will need a full 16 bit argument, for example some load immediate, or goto.
Common ways to deal with that:
1) variable width instructions (16/32 bit) - makes machine less simple.
2) always use 32 bit instructions, meaning instructions are
opcode, arg4bit, arg4bit, arg16bit.
This is simpler, but still pretty wasteful for instruction length. Could also use
opcode4bit, arg6bit, arg6bit, arg16bit
This turns the first 64 memory locations into special registers, but uses awkward 6bit values.
3) use 8 bit immediates with hi/lo access (like arm). So then u have instructions like
mov_hi dest4, imm8
nov_lo dest4, imm8
Setting the hi/lo byte of the register file (I.e. the first 16 memory locations). This in turn means there will be more instructions, they will not work directly on memory (like goto needs 2 loads). So while there is the nice property that instruction length equals word length, it also means more kinds of instructions (perhaps, like jump relative), more complicated instructions, and more instructions needing to be executed to accomplish similar tasks (eg 3 instructions for arbitrary jump).
All these considerations are probably counter to wanting a maximally simple machine.
I'm very surprised this smallest machine is not a stack machine.