11 ms·
To minimize the number of instructions for some finite set of nontrivial programs, you define the instruction set to have one instruction that performs each of
by kragen 4y ago
To minimize the number of instructions for some finite set of nontrivial programs, you define the instruction set to have one instruction that performs each of the programs. Then each of those programs is one instruction long. (Other programs may or may not be possible to encode at all.)
If the set of nontrivial programs is infinite, the situation is more complex, because an instruction set as normally defined is finite. Also, you can't equally weight every program from an infinite set, so you need some kind of weighting function among the programs. Which instruction set is ideal for encoding this infinite set of programs depends almost entirely on what that weighting function is. In fact, you can usually derive the optimal instruction set directly from the weighting function. Which is to say, when you design the weighting function, you are more or less designing the instruction set.
As retrac points out, it comes down to a question of tradeoffs. There's no objectively optimal answer to which tradeoffs you should prefer.
I took some notes some years ago on the subject of dense instruction sets, optimized for the number of bits to encode programs rather than the number of instructions; perhaps you will find them of interest: https://dercuano.github.io/notes/tiny-interpreters-for-microcontrollers.html https://dercuano.github.io/notes/tiny-interpreters-for-micro...
- anyfoo 4y ago> (Other programs may or may not be possible to encode at all.) Well you would want your instruction set to be Turing complete, but given that the stated goal was to only optimize for those programs for which you already added the super specialized instructions, you can just trivially add whatever “boring” instruction set you like and have uselessly checked that box, as well. Bonus points if you use an instruction from a One Instruction Set Computer (https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer ) just for style, and to claim that you have further minimized the instruction set for any program outside the stated domain!
- Y_Y 4y agoThanks for the notes. Just to clarify, (especially since other respondents misinterpreted to a less interesting question) I was thinking about the number of operations in the binary, not the number of distinct operations in the instruction set. Thus is probably equivalent to your case of number of bits, as long as you don't have some crazy large instruction set.