• drathvedro@lemm.ee
    link
    fedilink
    arrow-up
    0
    ·
    5 months ago

    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?

    • casual_turtle_stew_enjoyer@sh.itjust.works
      link
      fedilink
      arrow-up
      0
      ·
      edit-2
      5 months ago

      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.

      • drathvedro@lemm.ee
        link
        fedilink
        arrow-up
        0
        ·
        4 months ago

        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.