MOV is Turing-complete (2013) [pdf] | Hacker News Reader

MOV is Turing-complete (2013) [pdf]

drwho.virtadpt.net

66 pointssusam26 comments

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

Isn't PDF almost Turing-complete?

Postscript definitely is.

I thought the whole point of PDF was to excise the Turing-completeness from Postscript.

I believe at least doubly so (in addition to postscript you can embed JavaScript)

This is correct.

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

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.

> I have no idea how this relates to the HyperCard integration.

As I mentioned, QuickTime Movies were to be the file format for HyperCard 3.0 stacks, with QuickTime the HyperCard 3.0 runtime. The QuickTime team demonstrated it at WWDC in 1996.

> Apple didn't make an authoring tool for this feature, but another company did: “LiveStage” by Totally Hip.

The two most Flash-like tools for authoring QuickTime's interactivity capabilities were LiveStage and Electrifier Pro[1]. Additionally, several other tools (like Adobe GoLive and Terran Cleaner) supported simpler forms of interactivity. I was in Apple evangelism/developer relations then, so I was the person working with QuickTime developers on the Apple side.

[1] https://www.macworld.com/article/1014980/quicktime.html

relevant:

Chris Domas' movfuscator: https://github.com/xoreaxeaxeax/movfuscator

Presentation: https://www.youtube.com/watch?v=R7EEoWg6Ekk

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!

A related project: the movfuscator, which converts programs into "mov instructions, and only mov instructions": https://github.com/xoreaxeaxeax/movfuscator

"The inspiration for the compiler is the paper "mov is Turing-complete", by Stephen Dolan."

2015: https://news.ycombinator.com/item?id=9751312

2013: 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)

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)

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

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.

Additionally, the ARM mov instruction can't access memory, so it is not Turing complete anyway.

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?

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.

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?

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.

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.

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

FYI is the same Stephen Dolan from here:

https://github.com/stedolan/jq

Reply on news.ycombinator.com