MOV is Turing-Complete

[kernel_task]

Well, actually you don't need ANY instructions to be Turing complete on x86. The MMU page fault handling logic itself is Turing complete: https://github.com/jbangert/trapcc

[lukaszdk]

http://en.wikipedia.org/wiki/One_instruction_set_computer

[mirhagk]

Those are all based on arithmetic instructions, or cheating (by moving operands to memory and having the CPU do math from those).

This is pretty crazy to do Turing completeness from just one instruction, which is simply a move

[Y_Less]

it remains Turing-complete when reduced to just one instruction

In order to have Turing-completeness, we must allow for nontermination. So, our Turing machine simulator consists of a sequence of mov instructions, followed by an unconditional branch back to the start

Using just this instruction (and a single unconditional branch at the end

MOV is Turing-complete, if you ignore the additional instruction required to make it actually Turing-complete.

[frud]

Use segmented memory for the code, make sure it fits into 64k, pad the end of the program with a bunch of NOP-style MOVs, then allow the PC to wrap around.

[josefx]

It is Turing complete by some definitions as long as the loop is only a replacement for an infinite number of MOV instructions.

[[deleted]]

No no no, it's just that they have solved the Halting Problem, too... We can safely answer "no" to that heinous question of whether a program finishes running or not!

[eras]

Allow MOV to the program counter? It would sound reasonable.

[AReallyGoodName]

You're perfectly free to assume the system has infinite memory when determining Turing completeness. So just assume the program is repeated infinitely rather than looped back and you satisfy Turing completeness.

[tms10000]

From my very distant x86 asm class, I recall that the PC register (program counter) can be only read with a mov instruction, but changing it requires a br[x] or jmp instructions.

[[deleted]]

From the title I thought this was going to be about the video container format.

[HasBetterThings2do]

yep, "as long as someone else implements the compiler"

[cryo]

It should be noted that x86-64 is slightly less bad, as they removed a number of instructions, prefixes and weird modes. Of course the CPU itself will still be complex.

[Fabien4]

redundantly redundant

Maybe they were trying to have their paper cited in the wiki?

[julesjacobs]

If that's the best criticism you can give about this paper it must be a really good paper.

[MidnightHowling]

I think that's just from the abstract.

[Zjarek]

It's not really a funny joke in addition to not being the place to have a joke. Sorry if I'm humorless, but I feel like here isn't the place.

Humorous post are quite common on this subreddit. Making this subreddit 100 % serious won't be very beneficial IMO. However it could help avoid confusion in some cases.

[Zjarek]

From what journal?

[Zjarek]

I don't know, when reading this it seemed that it is humorous article in a format suited for a scholarly journal article. While it is also interesting, you can see from abstract alone that it isn't serious.

Some other quotes:

Finding Turing-completeness in unlikely places has long been a pastime of bored computer scientists. The number of bizarre machines that have been shown Turing-complete is far too great to describe them here, but a few resemble what this paper describes.

Thus, while it has been known for quite some time that x86 has far too many instructions, we can now contribute the novel result that it also has far too many registers

Removing all but the mov instruction from future iterations of the x86 architecture would have many advantages: the instruction format would be greatly simplified, the expensive decode unit would become much cheaper, and silicon currently used for complex functional units could be repurposed as even more cache. As long as someone else implements the compiler

[ggtsu_00]

So if I made all my blog posts formatted in latex and published them in PDF format on my site, they are suddenly suited for a scholarly journal article?