5 ms·

MOV is Turing-complete (2013) [pdf]

66 points by susam 7y ago

svnpenn 7y ago
FYI is the same Stephen Dolan from here: https://github.com/stedolan/jq https://github.com/stedolan/jq
claudiawerner 7y ago
A related project: the movfuscator, which converts programs into "mov instructions, and only mov instructions": https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator "The inspiration for the compiler is the paper "mov is Turing-complete", by Stephen Dolan."
a-wu 7y ago
relevant: Chris Domas' movfuscator: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator Presentation: https://www.youtube.com/watch?v=R7EEoWg6Ekk https://www.youtube.com/watch?v=R7EEoWg6Ekk
- caleb-allen 7y ago
  I wish Chris Domas still did presentations. I believe he was hired by Intel and I would guess that they would have asked him to stop publicly presenting. Smart hire on their part, but his presentations are legendary to me!
dang 7y ago
2015: https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 2013: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 (Links are for the curious. Reposts are fine after a year or so: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html)
nneonneo 7y ago
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)
- rrss 7y ago
  Note that Arm64 also doesn't have this kind of direct access to the program counter.
  - Liquid_Fire 7y ago
    Additionally, the ARM mov instruction can't access memory, so it is not Turing complete anyway.
- deleted 7y ago
  [deleted]
- shakna 7y ago
  Movfuscator [0] (which expands on the paper) managed to find a way to jump using just mov - by using a faulting mov. [0] https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
  - nneonneo 7y ago
    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/ 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.
- kees99 7y ago
  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_modes https://en.wikipedia.org/wiki/PDP-11_architecture#Addressing...
Zecc 7y ago
I honest to goodness thought this was going to be about the video container format. In retrospect this makes much more snse.
- dehrmann 7y ago
  Isn't PDF almost Turing-complete?
  - naikrovek 7y ago
    Postscript definitely is.
  - genpfault 7y ago
    I thought the whole point of PDF was to excise the Turing-completeness from Postscript.
  - 2038AD 7y ago
    I believe at least doubly so (in addition to postscript you can embed JavaScript)
  - marcuswebb 7y ago
    This is correct.
- CharlesW 7y ago
  It's not a crazy thought — QuickTime Movies were to be the native file format for HyperCard 3.0[1]. [1] https://en.wikipedia.org/wiki/HyperCard#HyperCard_3.0 https://en.wikipedia.org/wiki/HyperCard#HyperCard_3.0
  - DerekL 7y ago
    Interactivity was added to QuickTime movies. I think this feature was called “wired actions”. I have no idea how this relates to the HyperCard integration. Apple didn't make an authoring tool for this feature, but another company did: “LiveStage” by Totally Hip.
begoon 7y ago
https://pragprog.com/magazines/2012-03/the-nor-machine https://pragprog.com/magazines/2012-03/the-nor-machine
deleted 7y ago
[deleted]
octocop 7y ago
I did not understand how mov could be used for comparison. Is a register set to a certain value if the contents are already the same value when it's trying to write?
- Liquid_Fire 7y ago
  If you are comparing values X and Y, just write 0 to address X and 1 to address Y. Then read address X. If X and Y are equal, then you would have written first 0 and then 1 to the same address, so the final read would give you 1. If X and Y are different, then you would read back the 0 you wrote to address X.
  - nexuist 7y ago
    It took me a bit to grok this but I think I finally understand it. Super clever. Now, how would you do greater than / less than comparisons?
    - magicalhippo 7y ago
      The native and super inefficient way would be basically the same: write 1 to all addresses greater or equal to X, and 0 to all addresses less than X, then read from address Y and see what you end up with. Probably a more clever trick out there though.
- pjc50 7y ago
  No, it's testing "did this MOV clobber address X or not." Put a guard value in address X. Write not-guard value to Y. Read X. If the value you just read wasn't the guard value, then Y was the same as X.

66 points by susam 7y ago

FYI is the same Stephen Dolan from here: https://github.com/stedolan/jq https://github.com/stedolan/jq

A related project: the movfuscator, which converts programs into "mov instructions, and only mov instructions": https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator "The inspiration for the compiler is the paper "mov is Turing-complete", by Stephen Dolan."

a-wu 7y ago

relevant: Chris Domas' movfuscator: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator Presentation: https://www.youtube.com/watch?v=R7EEoWg6Ekk https://www.youtube.com/watch?v=R7EEoWg6Ekk

caleb-allen 7y ago
I wish Chris Domas still did presentations. I believe he was hired by Intel and I would guess that they would have asked him to stop publicly presenting. Smart hire on their part, but his presentations are legendary to me!

dang 7y ago

2015: https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 2013: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 (Links are for the curious. Reposts are fine after a year or so: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html)

nneonneo 7y ago

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)

rrss 7y ago
Note that Arm64 also doesn't have this kind of direct access to the program counter.
- Liquid_Fire 7y ago
  Additionally, the ARM mov instruction can't access memory, so it is not Turing complete anyway.
deleted 7y ago
[deleted]
shakna 7y ago
Movfuscator [0] (which expands on the paper) managed to find a way to jump using just mov - by using a faulting mov. [0] https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- nneonneo 7y ago
  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/ 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.
kees99 7y ago
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_modes https://en.wikipedia.org/wiki/PDP-11_architecture#Addressing...

Zecc 7y ago

I honest to goodness thought this was going to be about the video container format. In retrospect this makes much more snse.

dehrmann 7y ago
Isn't PDF almost Turing-complete?
- naikrovek 7y ago
  Postscript definitely is.
- genpfault 7y ago
  I thought the whole point of PDF was to excise the Turing-completeness from Postscript.
- 2038AD 7y ago
  I believe at least doubly so (in addition to postscript you can embed JavaScript)
- marcuswebb 7y ago
  This is correct.
CharlesW 7y ago
It's not a crazy thought — QuickTime Movies were to be the native file format for HyperCard 3.0[1]. [1] https://en.wikipedia.org/wiki/HyperCard#HyperCard_3.0 https://en.wikipedia.org/wiki/HyperCard#HyperCard_3.0
- DerekL 7y ago
  Interactivity was added to QuickTime movies. I think this feature was called “wired actions”. I have no idea how this relates to the HyperCard integration. Apple didn't make an authoring tool for this feature, but another company did: “LiveStage” by Totally Hip.

begoon 7y ago

https://pragprog.com/magazines/2012-03/the-nor-machine https://pragprog.com/magazines/2012-03/the-nor-machine

deleted 7y ago

[deleted]

octocop 7y ago

I did not understand how mov could be used for comparison. Is a register set to a certain value if the contents are already the same value when it's trying to write?

Liquid_Fire 7y ago
If you are comparing values X and Y, just write 0 to address X and 1 to address Y. Then read address X. If X and Y are equal, then you would have written first 0 and then 1 to the same address, so the final read would give you 1. If X and Y are different, then you would read back the 0 you wrote to address X.
- nexuist 7y ago
  It took me a bit to grok this but I think I finally understand it. Super clever. Now, how would you do greater than / less than comparisons?
  - magicalhippo 7y ago
    The native and super inefficient way would be basically the same: write 1 to all addresses greater or equal to X, and 0 to all addresses less than X, then read from address Y and see what you end up with. Probably a more clever trick out there though.
pjc50 7y ago
No, it's testing "did this MOV clobber address X or not." Put a guard value in address X. Write not-guard value to Y. Read X. If the value you just read wasn't the guard value, then Y was the same as X.