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