Is move in Motorola 68000 Turing complete?

For hardware talk only (please avoid ROM dumper stuff)
Post Reply
Natsumi
Very interested
Posts: 82
Joined: Mon Oct 05, 2015 3:00 pm
Location: 0x0
Contact:

Is move in Motorola 68000 Turing complete?

Post by Natsumi » Sun Oct 11, 2015 10:22 pm

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
Last edited by Natsumi on Mon Oct 12, 2015 9:47 am, edited 1 time in total.

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Is move in Motorola 68000 Turing complete?

Post by Stef » Mon Oct 12, 2015 9:30 am

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.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Is move in Motorola 68000 Turing complete?

Post by Sik » Mon Oct 12, 2015 4:29 pm

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

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Is move in Motorola 68000 Turing complete?

Post by Stef » Mon Oct 12, 2015 10:20 pm

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.
Yeah from the classic "MOVE" instruction but actually "JMP" instruction is internally a simple MOVE PC,<ea>
JMP is just a "user friendly" mnemonic ;)

Post Reply