Re:MOV is Turing-complete (2013) [pdf]
by nneonneo on Tuesday February 18, 2020 @01:57AM
(#22354036)
It’s actually a shame that there is no `mov rip, ...` instruction. That would make it truly Turing-complete. ARM has this instruction! (Of course, jmp [...] works just as well, but it isn’t called mov)
[ Parent
| on HN ]
Movfuscator [0] (which expands on the paper) managed to find a way to jump using just mov - by using a faulting mov.
Re:MOV is Turing-complete (2013) [pdf]
by nneonneo on Tuesday February 18, 2020 @04:20PM
(#22360517)
Yeah, I remember this. It requires setting up a custom signal handler though. IIRC something similar is used to get system/library calls (which also can’t be expressed purely with mov instructions, normally).
If I recall correctly tom7 had a cute trick to get looping behavior in his ASCII-only compiler for 16-bit Intel (http://tom7.org/abc/) which was to make the program 64KB exactly, such that the program counter just loops around at the end. I suppose that’s another option to get _pure_ mov-only code.
PDP-11 architechture [1] has a "jmp" that is a variant of "mov". And "push", "pop", and even "ret" are too. Also this beauty:
MOV -(PC), -(PC)
This is a 1-word self-replicating program that (when run from the topmost RAM address) will clobber entire RAM by copying itself all over it.[1] https://en.wikipedia.org/wiki/PDP-11_architecture#Addressing...
Note that Arm64 also doesn't have this kind of direct access to the program counter.
Re:MOV is Turing-complete (2013) [pdf]
by Liquid_Fire on Tuesday February 18, 2020 @11:58AM
(#22357467)
Additionally, the ARM mov instruction can't access memory, so it is not Turing complete anyway.