News for hackers. Stuff that matters.
Re:MOV is Turing-complete (2013) [pdf] by Zecc on Tuesday February 18, 2020 @03:07AM (#22354305)
I honest to goodness thought this was going to be about the video container format. In retrospect this makes much more snse.
Re:MOV is Turing-complete (2013) [pdf] by CharlesW on Tuesday February 18, 2020 @12:08PM (#22357588)
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] by DerekL on Tuesday February 18, 2020 @06:25PM (#22361521)
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] by CharlesW on Tuesday February 18, 2020 @08:48PM (#22362396)
> 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

Re:MOV is Turing-complete (2013) [pdf] by dehrmann on Tuesday February 18, 2020 @11:29AM (#22357181)
Isn't PDF almost Turing-complete?
Re:MOV is Turing-complete (2013) [pdf] by 2038AD on Tuesday February 18, 2020 @01:16PM (#22358538)
I believe at least doubly so (in addition to postscript you can embed JavaScript)
Re:MOV is Turing-complete (2013) [pdf] by genpfault on Tuesday February 18, 2020 @12:06PM (#22357568)
I thought the whole point of PDF was to excise the Turing-completeness from Postscript.
Re:MOV is Turing-complete (2013) [pdf] by naikrovek on Tuesday February 18, 2020 @11:38AM (#22357267)
Postscript definitely is.
Re:MOV is Turing-complete (2013) [pdf] by marcuswebb on Tuesday February 18, 2020 @02:11PM (#22359202)
This is correct.
Re:MOV is Turing-complete (2013) [pdf] by a-wu on Tuesday February 18, 2020 @01:25AM (#22353917)
Re:MOV is Turing-complete (2013) [pdf] by caleb-allen on Tuesday February 18, 2020 @12:05PM (#22357565)
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] by claudiawerner on Tuesday February 18, 2020 @01:22AM (#22353908)
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."

Re:MOV is Turing-complete (2013) [pdf] by dang on Tuesday February 18, 2020 @01:35AM (#22353949)
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)
Re:MOV is Turing-complete (2013) [pdf] by shakna on Tuesday February 18, 2020 @06:44AM (#22355219)
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

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.

Re:MOV is Turing-complete (2013) [pdf] by kees99 on Tuesday February 18, 2020 @07:41AM (#22355524)
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...

Re:MOV is Turing-complete (2013) [pdf] by rrss on Tuesday February 18, 2020 @10:14AM (#22356593)
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.
Re:MOV is Turing-complete (2013) [pdf] by octocop on Tuesday February 18, 2020 @07:28AM (#22355458)
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?
Re:MOV is Turing-complete (2013) [pdf] by Liquid_Fire on Tuesday February 18, 2020 @07:37AM (#22355493)
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.

Re:MOV is Turing-complete (2013) [pdf] by nexuist on Tuesday February 18, 2020 @11:13AM (#22357051)
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?

Re:MOV is Turing-complete (2013) [pdf] by magicalhippo on Tuesday February 18, 2020 @04:05PM (#22360395)
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] by pjc50 on Tuesday February 18, 2020 @07:40AM (#22355521)
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.

Re:MOV is Turing-complete (2013) [pdf] by begoon on Tuesday February 18, 2020 @04:52AM (#22354735)
Re:MOV is Turing-complete (2013) [pdf] by svnpenn on Tuesday February 18, 2020 @11:58AM (#22357461)
FYI is the same Stephen Dolan from here:

https://github.com/stedolan/jq