X86 mov is turing complete: mov-only compiler
1–10 of 60 posts
Re: X86 mov is turing complete: mov-only compiler
#2HN discussion of the paper that this is based on: https://news.ycombinator.com/item?id=6309631
Re: X86 mov is turing complete: mov-only compiler
#3That's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks.
X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations, but "ldr/str" for register-memory, while X86 just uses mov for everything. Even ARM mov optionally puts a barrel shifter into the path, so it's not that pure either.
Re: X86 mov is turing complete: mov-only compiler
#4Sounds like if we make a JS to BF transpiler, then we can complete this with any language that can be transpiled to JS.
Just imagine the applications of this!
The next step would be to make this into an eventual Quine.
Re: X86 mov is turing complete: mov-only compiler
#5That's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks. X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations…
If you're going down that path, all of x86 is used as a 'bytecode' that turns into microcode instructions anyway in modern processors.
Re: X86 mov is turing complete: mov-only compiler
#6HN discussion of the paper that this is based on: https://news.ycombinator.com/item?id=6309631
That paper is so funny:
Finding Turing-completeness in unlikely places has long been a
pastime of bored computer scientists.
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.
Re: X86 mov is turing complete: mov-only compiler
#7That's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks. X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations…
Even if they weren't a single mnemonic, if you read the paper you'll find that reg = mem[reg + C], mem[reg + C] = reg, and reg = C appear to be the only 3 instruction types that are actually needed; these are only register-memory and register-constant data transfers. Even register-register isn't needed.
Re: X86 mov is turing complete: mov-only compiler
#8That's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks. X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations…
If you're going down that path, all of x86 is used as a 'bytecode' that turns into microcode instructions anyway in modern processors.
Not exactly, most instructions are not "microcoded" for performance reasons. But there is a class of instructions that is.
Re: X86 mov is turing complete: mov-only compiler
#9The Github description is misleading:
> The single instruction C compiler
I was seriously impressed until I got further down.
Re: X86 mov is turing complete: mov-only compiler
#10That's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks. X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations…
ARM mov can be used as a JMP . Program counter is in fact register R15 in ARM.