Open Questions

Bergstra and Middelburg (2o12a) have shown that, in the case where the number of instructions is not bounded, there exist instruction sequences with direct and indirect jump instructions from which elimination of indirect jump instructions is possible without a super-linear increase of their maximal internal delay on execution only if their lengths increase super-linearly on elimination of indirect jump instructions. It is an open question whether this result goes through in the case where the number of instructions is bounded. It is also an open question whether the presence of other common kinds of instructions that do not increase the expressiveness have comparable effects.

Bergstra and Middelburg (2013c) have shown that the long multiplication algorithm can be computed by quadratic-length instruction sequences without backward jump instructions and by linear-length instruction sequences with backward jump instructions. It is an open question whether it can be computed by linear-length instruction sequences without backward jump instructions.

Bergstra and Middelburg (2o14a) have developed an approach to non-uniform computational complexity in which algorithmic problems are viewed as families of Boolean functions that consist of an n-ary Boolean function for each natural number n and the complexity of such problems is assessed in terms of the length of finite single-pass instruction sequences acting on Boolean registers that compute the members of these families. The instruction sequences concerned contain only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. Each Boolean register used serves as either input register, output register or auxiliary register. Complexity classes isomorphic to well-known ones, such as P/poly and NP/poly, are naturally defined without restrictions on the number of auxiliary registers used or the length of jumps. For these complexity classes, it is an open problem whether such restrictions yield properly included ones.

Bergstra and Middelburg (2016b)  have shown that, in the case of the parity functions, shorter instruction sequences are possible with the use of an auxiliary Boolean register than without the use of an auxiliary Boolean register provided the instruction set is extended with instructions to complement the content of auxiliary Boolean registers. It is still an open question whether smaller programs are also possible in the absence of instructions to complement the content of auxiliary Boolean registers.