Bookmarking your comment so I can come back to it in a couple hours, if I hopefully remember to.
But yes, almost. I don’t think the interrupt is necessary and the return isn’t under certain architectures. I have a doc on my computer somewhere where I was investigating what the absolute minimum was to make a turning complete machine and, to my recollection, there was only 4-6 instructions that were absolutely necessary. The ones I remember off the top of my head are NAND, MOV, JUMPIF, and then I believe I included NOP in accordance with some principle. RET and INT were convenience features in this design.
The key here I think is the NAND. I know you can do practically anything with only NAND gates. But without it, and with just control structures, I don’t think there’s a way to perform computation unless there is some theoretical voodoo withcraft possible, something like nop-padded cellular automata given the infinite memory. But I don’t have any qualification to talk about this, I’m just some random dude who flunked out of the university but finished all Zachtronics games.
You’re remembering correctly, every other logic gate can be built from NAND gates, which is the foundation of this sort of minimal-instruction-set exercise. Beyond that, you need to be able to move data and change your program counter (jump, often conditionally). Then, if you want parity with modern instruction sets beyond just being turning complete, you need return and interrupt for control flow.
Are you implying that an assembly language consisting of just ret, int3 and jmp (and nop, of course) is turing-complete? …are you sure about that?
Bookmarking your comment so I can come back to it in a couple hours, if I hopefully remember to.
But yes, almost. I don’t think the interrupt is necessary and the return isn’t under certain architectures. I have a doc on my computer somewhere where I was investigating what the absolute minimum was to make a turning complete machine and, to my recollection, there was only 4-6 instructions that were absolutely necessary. The ones I remember off the top of my head are NAND, MOV, JUMPIF, and then I believe I included NOP in accordance with some principle. RET and INT were convenience features in this design.
Fun fact: apparently on x86 just MOV all by itself is Turing-complete, without even using it to produce self-modifying code (paper, C compiler).
The key here I think is the NAND. I know you can do practically anything with only NAND gates. But without it, and with just control structures, I don’t think there’s a way to perform computation unless there is some theoretical voodoo withcraft possible, something like nop-padded cellular automata given the infinite memory. But I don’t have any qualification to talk about this, I’m just some random dude who flunked out of the university but finished all Zachtronics games.
You’re remembering correctly, every other logic gate can be built from NAND gates, which is the foundation of this sort of minimal-instruction-set exercise. Beyond that, you need to be able to move data and change your program counter (jump, often conditionally). Then, if you want parity with modern instruction sets beyond just being turning complete, you need return and interrupt for control flow.