Monday, August 29, 2016

mov Is Turing-complete

Stephen Dolan (PDF, via Emily St.):

It is well-known that the x86 instruction set is baroque, overcomplicated, and redundantly redundant. We show just how much fluff it has by demonstrating that it remains Turing-complete when reduced to just one instruction.

The instruction we choose is mov, which can do both loads and stores. We use no unusual addressing modes, self-modifying code, or runtime code generation. Using just this instruction (and a single unconditional branch at the end of the program to make nontermination possible), we demonstrate how an arbitrary Turing machine can be simulated.

movfuscator:

The M/o/Vfuscator (short ‘o’, sounds like “mobfuscator”) compiles programs into “mov” instructions, and only “mov” instructions. Arithmetic, comparisons, jumps, function calls, and everything else a program needs are all performed through mov operations; there is no self-modifying code, no transport-triggered calculation, and no other form of non-mov cheating.

Update (2016-08-29): Rosyna Keller:

As is xor

Comments RSS · Twitter

Leave a Comment