What is the minimum set of mathematical operators that can generate all the calculations?

Question

I am thinking of a minimal set of processors, say, ten or fewer operation codes. I want to find the smallest set of mathematical codes that can perform any general purpose function.

For example, in logic, the AND, OR, NOT operators are redundant. You can calculate any function with two others, so the minimum set of logical operators requires only two.

For arithmetic functions, could I get using two operation codes, perhaps ADD and bit-wise invert? (suppose a carry bit and a transfer jump instruction).

With ADD and BITINV, I can do subtraction without an explicit SUB statement. Multiplication and division are simple extensions from addition and subtraction. SHL is multiplied by two, and SHR is divided by two.

To cover logic and arithmetic, it looks like AND, BITINV, ADD - this is a complete minimal set. Did I miss something?

Answer 1

You probably also need to include control instructions, such as conditional expressions and transitions, to complete your Turing command setup (or maybe your instruction set should be able to construct all computable functions ).

For example, in your question

Multiplication and division are simple extensions from addition and Subtraction

(, , ). -, .