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?
MOV is Turing-complete (2013) [pdf]
11–20 of 29 posts
Re: MOV is Turing-complete (2013) [pdf]
#12I 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.
Re: MOV is Turing-complete (2013) [pdf]
#13I 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?
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]
#14It’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)
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)
[1] https://en.wikipedia.org/wiki/PDP-11_architecture#Addressing...
Re: MOV is Turing-complete (2013) [pdf]
#15It’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)
Note that Arm64 also doesn't have this kind of direct access to the program counter.
Re: MOV is Turing-complete (2013) [pdf]
#16I 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?
Re: MOV is Turing-complete (2013) [pdf]
#17I 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?
Re: MOV is Turing-complete (2013) [pdf]
#18Re: MOV is Turing-complete (2013) [pdf]
#19FYI is the same Stephen Dolan from here:
Re: MOV is Turing-complete (2013) [pdf]
#20It’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)
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.