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.
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.