[billforsternz]

Forgive my ignorance but I thought being Turing complete was important because a Turing complete machine can in principle perform any arbitrary computation. As far as I know the program counter cannot be a destination for an X86 MOV. So you can't branch with only MOVs. How can you do an arbitrary computation if you can't branch?

Maybe you have to reorganize if(a) { b; } else { c; } as a kind of permuted b; followed by c; such that either the permuted b; or the permuted c; are effectively no-ops depending on the value of a.

[DSMan195276]

You're right, they never actually do any jumping. From what I can tell, they use a variable called `on` to control where every set of commands write their results too. They do some funky `mov` stuff to do a comparison, and then set `on` with that comparison. They use a stack of `on` variables and then pop off the value of `on` from that stack when you exit a loop.

They cheat to get a jump without using anything but `mov`'s by executing an illegal set of `cs` using `mov`, and then use the sigill generated to execute a signal handler, which is just the same spot that the code starts at. IMO, it doesn't really count, so a `mov`-only program requires at least one jmp instruction to work.

I think loops are achieved by simply running the code to the end without saving any of the results, and then hitting the singal and going back to the beginning - ignoring all the code until you hit the loop you're executing. But, the `mov` code is fairly hard to understand so I could be wrong on that.

[nitrogen]

Could one use self-modifying code (such as rewriting the SIGILL handler) to simplify this a bit?

[Buge]

It also uses a single jmp instruction to branch back to the start in a loop.

Two values a and b can be compared by storing 0 into * a and 1 into * b. Then a == b if * a is 1. Then this value can be used to index into an array to provide different behavior based on if a == b.

Edit: apparently HN doesn't allow me to escape * with \, which the markdown spec says I should be able to do.

[thaumasiotes]

> HN doesn't allow me to escape * with \, which the markdown spec says I should be able to do

So? What does the markdown spec have to do with... anything? The XML spec says you have to begin your comment with a version number declaration, but you're not doing that.

[Buge]

I thought it was trying to implement markdown by italicizing half my sentence when I put * in. Markdown was what popped into my mind when I saw that behavior. It would be nice if I could find a way of escaping them without having to insert spaces where I don't want spaces.

[lorenzhs]

There isn't one, HN doesn't use markdown. See https://news.ycombinator.com/formatdoc

[kuschku]

It should use markdown, though.

[nickodell]

It's not just mov's. There's a non-branching jump at the end that loops back to the beginning. Termination is accomplished by reading from address 0.

It's based on this paper: http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

[jacobwcarlson]

http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf