A while back, as we spoke 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
Is move in Motorola 68000 Turing complete?
Is move in Motorola 68000 Turing complete?
Last edited by Natsumi on Mon Oct 12, 2015 9:47 am, edited 1 time in total.
-
- Very interested
- Posts: 3131
- Joined: Thu Nov 30, 2006 9:46 pm
- Location: France - Sevres
- Contact:
Re: Is move in Motorola 68000 Turing complete?
Can't loop be considered as a move instruction on PC register ?
I do like the Turing completeness concept for the least and i'm surprised you can do that much with single move instruction.
I do like the Turing completeness concept for the least and i'm surprised you can do that much with single move instruction.
Re: Is move in Motorola 68000 Turing complete?
You can't do MOVE to the PC register though (only with BRA and friends and with RTS), so that probably doesn't count.
Sik is pronounced as "seek", not as "sick".
-
- Very interested
- Posts: 3131
- Joined: Thu Nov 30, 2006 9:46 pm
- Location: France - Sevres
- Contact:
Re: Is move in Motorola 68000 Turing complete?
Yeah from the classic "MOVE" instruction but actually "JMP" instruction is internally a simple MOVE PC,<ea>Sik wrote:You can't do MOVE to the PC register though (only with BRA and friends and with RTS), so that probably doesn't count.
JMP is just a "user friendly" mnemonic
![Wink ;)](./images/smilies/icon_wink.gif)