So you can have One Instruction Set Computers. But typically these instructions have rather complicated underlying implementations.

  • addition (addleq, add and branch if less than or equal to zero)
  • decrement (DJN, decrement and branch (jump) if nonzero)
  • increment (P1eq, plus 1 and branch if equal to another value)
  • subtraction (subleq, subtract and branch if less than or equal)
  • subtraction when possible (Arithmetic machine)

Those first ones involve 3+ underlying operations. I'm wondering though what bitwise operations you would need in order to produce a Turing-complete computer. The minimal set of bitwise operations, independent of efficiency. Then if that's an easy answer perhaps one that takes efficiency into account, but not necessary for the main question, would just be interesting to know.

I am pretty sure I've seen that you can create every other bitwise operation from a NAND gate, so perhaps you can create them all with a NAND gate. But I am in particular wondering if only using bitshifts can produce a Turing machine. Or if not, what minimal set of bit operations can do it.

  • 2
    $\begingroup$ Counter programs are pretty simple. Look them up. $\endgroup$ – Yuval Filmus Feb 5 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.