Is conditional branching a requirement of Turing-completeness?

If you have only arithmetical expressions you can use some properties of arithmetical operations. E.g., is A is either 0 or 1 depending on some condition (which is previously computed), then A*B+(1-A)*C computes the expression if A then B else C.

The original Rojas paper can be found here. The basic idea is that the Z3 only supports a unconditional single loop (by gluing the ends of the instruction tape together). You build conditional execution of it by putting all code sections one after another in the loop, and having a variable z that determines which section to execute. At the beginning of section j, you set

 if (z==j) then t=0 else t=1

and then make each assignment a = b op c in this section read

 a = a*t + (b op c)*(1-t)

(i.e. each assignment is a no-op, except in the active section). Now, this still includes a conditional assignment: how to compare z==j? He proposes to use the binary representation of z (z1..zm) along with the negated binary representation of j (c1..cm), and then compute

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

This product will be 1 only if c and z differ in all bits, which will happen only if z==j. An assignment to z (which essentially is an indirect jump) must also assign to z1..zm.

Rojas has also written Conditional Branching is not Necessary for Universal Computation in von Neumann Computers. There he proposes a machine with self-modifying code and relative addressing, so that you can read the Turing instructions from memory, and modify the program to jump accordingly. As an alternative, he proposes the above approach (for Z3), in a version that only uses LOAD(A), STORE(A), INC and DEC.