Is move in Motorola 68000 Turing complete?

Discussion in 'Technical Discussion' started by Natsumi, Oct 12, 2015.

  1. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    A while back, as we spoke in IRC about MoVfuscator, an utility which compiles any C code to only use mov instruction, we thought if move in Motorola 68000 would also be in fact Turing complete. A lot came out of it, but no real way to fully exploit Motorola 68000 with working methods. After that, I took some time to figure out how to do simple programs quickly and efficiently.

    But before we dig into my research, what is Turing completeness? Well, as I understand it, is ability to process certain types of arithmetic functions within a processor by only using a single type of its instructions. In the case of this topic and MoVfuscator, only mov/move, with its various forms. If you want to find more in depth information about Turing completeness and MoVfuscator, you can watch this video.

    So what can we do in 68000? Well, a lot! First of all, add, sub, eor, or, and, etc etc, can all be done with just arrays and moves. No problem. You should be able to do this by yourself quite easily. Ok, what about loops? Well, this strictly isn't possible as far as I know, unless they are designed quite intelligently. But you can always repeat a single move... a lot of times, to achieve this. It isn't ideal, of course! But probably the biggest question is, branching. One way would be to follow MoVfuscator, and have half of the RAM be responsible for actual RAM and other half for scratch RAM. But that is lame, isn't it!

    Instead what I would do, is to use Address Error, Privilege Violation, and Trace errors to create a routine to be ran that loads data to RAM, while other error would then jump to that RAM! Now it still does use RAM, but considerably less than half of it. The problem is for the moment I haven't gotten it to fully work. Either code falls through Trace and Privilege Violation, or freezes on 2 Address Errors. You can however, use Illegal Instruction, LineA Emulator and LineF Emulator as well, but I feel its a little bit cheating.

    I've created 2 demo's that utilize and explore the bounds of the Turing completeness a little, however more research is to be done! These demo's can be built with ASM68K as is.
    Demo 1, Demo 2
     
  2. vectrexian

    vectrexian

    Member
    8
    0
    1
    Really cool work, I love this sort of thing. Reminds me of the guys who proved that the x86 MMU is Turing complete (https://github.com/jbangert/trapcc). Can you MOVE to program counter on 68000? If so, branching should be doable using lookup tables. Your conditional value is used as an index into a jump table, and the table value is moved into the program counter, no traps required.
     
  3. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    you cant move to PC, that is a huge issue in 68k for turing completeness, therefore I need to keep doing the stupid traps to keep it working. It would be a lot easier to use loouptables tor move PC but that isnt possible. Technically jmp is move to pc, but I think move-only is better to me and staying off of that seems cheaty.
     
  4. qiuu

    qiuu

    Tech Member
    144
    9
    18
    Blue Ball & Blocks
    Turing complete roughly means that whatever you're dealing with is as powerful as a Turing machine. Any modern processor basically qualifies, though strictly speaking you have to assume unlimited memory. The term is often also applied to programming languages, or restricted instruction sets of programming languages. It basically means you can re-write any program that runs on a Turing machine with your instruction set and infinite memory.

    Usually, to show that an instruction set is Turing complete, you just take another Turing complete instruction set and then show that you simulate all of its instructions with your instruction set.
    For instance, the single instruction subleq (subtract and branch if less or equal to zero) is Turing complete, so if you can show that you can simulate it just using move instructions you'd be done.

    The problem now is that you need to come up with a way to change the control flow, because usually you'd just process one move after the other until you reach the end, and then it's over.
    The way MoVuscator is the only scalable way of doing this, I think. Because there's only a limited amount of types of exceptions, if you have many conditional branches, some of them will have to jump to the same address, and so you need to disable some code depending on what you want to run. So yeah: Trigger an exception, and have the exception handler basically be the start address of your code. That way you can at least achieve looping, and from there by enabling and disabling code (or more precisely, having it have no effect) somehow you can also simulate branches (disable all code until the code you want to branch to). On the Genesis you'd trigger that, as you said, e.g. by trying to move a word or a long from/to a misaligned (I.e. odd) address.

    I don't know if you can execute code in RAM on the Genesis, but if so, you can cheat in a way by jumping into an address in RAM, and then you can just use move to put all kinds of instructions there.

    Either way, I like this kind of discussion which seems rather scarce here. On another, smaller, forum I frequent we've also done things like showing that Lemmings is NP-hard (and actually it's been shown that it is, in fact, PSPACE-complete). Another question could be, which objects do you need in Sonic to make solving a Sonic level an NP-hard problem? Or do you need any objects at all?
     
  5. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    I think you should look at the demos I provide, as it mostly works for control flow, and even the demo 2 is a very simple program with scrolling text, redrawing, etc.. As you can easily load code to RAM and then just cause interruption, it is possible to run it. However making it move only is still a thing to do. I also did a simple conditional branching, as to load different code by getting a pointer from table. It is quite rough and impractical, but works. Then again doing move only in MD is as impractical as it gets. And as you described, you can jump into a RAM and load it up with all kids of move instructions, and is in fact what I do. In fact I would be interested in said forum, as SpritesMind and this forum seem to not have interest in anything alike this, maybe they'd be more so interested!
     
  6. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,138
    0
    16
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    You can execute code on RAM, yes, and I suggested the same thing to him (having an exception vector point to RAM, moving instructions there, triggering the exception).
     
  7. GerbilSoft

    GerbilSoft

    RickRotate'd. Administrator
    2,893
    24
    18
    USA
    rom-properties
    Do note that older versions of Gens (including Gens/GS r7) don't fully support this. In particular, they only support the RAM mirrors $FFxxxx and $F0xxxx.