The Intel architecture is already Turing complete when you just use MOV instructions: https://github.com/xoreaxeaxeax/movfuscator. Of course, you don't even need instructions at all: https://news.ycombinator.com/item?id=5261598

▲

mk_stjames 4 days ago | parent | next [-]

I came back to reply with just this. Christopher Domas's conference talk on the movfuscator is legendary:

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

▲

QuadmasterXLII 4 days ago | parent | prev | next [-]

While this is true, I suspect a spec compliant implementation of the x86 mov instruction would many use more transistors than OP’s entire CPU.

	▲	crest 4 days ago \| parent [-]
		Of course, but you don't have the toy CPU under your desk or in your laptop running at several GHz nor are you likely to find it in a target that really needs a cute hack to obscure your exploit.

▲

aleph_minus_one 3 days ago | parent | prev [-]

> The Intel architecture is already Turing complete when you just use MOV instructions

No physically existing architecture is Turing-complete, since every CPU can (by physics) only access a finite amount of memory, which means that its state space is finite, in opposite to the infinite state space of a Turing machine.

	▲	jdiff 3 days ago \| parent \| next [-]
		But that's not a very useful definition so we usually don't both enforcing that constraint.
	▲	a day ago \| parent \| prev [-]
		[deleted]