Live data from Hacker News

MOV is Turing-complete (2013) [pdf]

drwho.virtadpt.net

21–29 of 29 posts

Re: MOV is Turing-complete (2013) [pdf]

#21
post #3

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!

Re: MOV is Turing-complete (2013) [pdf]

#22
post #6

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?

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

Re: MOV is Turing-complete (2013) [pdf]

#23
post #6

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

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

Re: MOV is Turing-complete (2013) [pdf]

#24
post #6

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?

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

Re: MOV is Turing-complete (2013) [pdf]

#26
post #16

Earlier quoted context omitted.

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.

Re: MOV is Turing-complete (2013) [pdf]

#27
post #10
post #5

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.

Re: MOV is Turing-complete (2013) [pdf]

#28
post #6

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

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.

Re: MOV is Turing-complete (2013) [pdf]

#29
post #28

Earlier quoted context omitted.

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

Post reply on HN