Is conditional branching a requirement of Turing-completeness?

Question

I've been searching the web and I'm finding somewhat contradictory answers. Some sources assert that a language/machine/what-have-you is Turing complete if and only if it has both conditional and unconditional branching (which I guess is kind of redundant), some say that only unconditional is required, others that only conditional is required.

Reading about the German Z3 and ENIAC, Wikipedia says:

The German Z3 (shown working in May 1941) was designed by Konrad Zuse. It was the first general-purpose digital computer, but it was electromechanical, rather than electronic, as it used relays for all functions. It computed logically using binary math. It was programmable by punched tape, but lacked the conditional branch. While not designed for Turing-completeness, it accidentally was, as it was found out in 1998 (but to exploit this Turing-completeness, complex, clever hacks were necessary).

What complex, clever hacks, exactly?

A 1998 paper Abstract by R. Rojas also states (Note that I haven't read this paper, it's just a snippet from IEEE.):

The computing machine Z3, built by Konrad Zuse between 1938 and 1941, could execute only fixed sequences of floating point arithmetical operations (addition, subtraction, multiplication, division, and square root) coded in a punched tape. An interesting question to ask, from the viewpoint of the history of computing, is whether or not these operations are sufficient for universal computation. The paper shows that, in fact, a single program loop containing these arithmetical instructions can simulate any Turing machine whose tape is of a given finite size. This is done by simulating conditional branching and indirect addressing by purely arithmetical means. Zuse's Z3 is therefore, at least in principle, as universal as today's computers that have a bounded addressing space.

In short, SOers, what type of branching is exactly required for Turing-completeness? Assuming infinite memory, can a language with only a goto or jmp branching construct (no if or jnz constructs) be considered Turing-complete?

Answer 1

The Z3 was only Turing complete from an abstract point of view. You can have an arbitrarily long program tape and just have it compute both sides of every conditional branch. In other words, for each branch, it would compute both answers and tell you which one to ignore. Obviously this creates exponentially larger programs for every conditional branch you would have, so you could never use this machine in a Turing-complete manner.

Answer 2

You need something that can branch based on (results from) input.

One way to simulate conditional branches is with self-modifying code -- you do a computation that deposits its result into the stream of instructions being executed. You could put the op-code for an unconditional jump into the instruction stream, and do math on an input to create the correct target for that jump, depending on some set of conditions for the input. For example, subtract x from y, shift right to 0-fill if it was positive, or 1-fill if it was negative, then add a base address, and store that result immediately following the jmp op-code. When you get to that jmp, you'll go to one address if x==y, and another if x!=y.

Answer 3

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.

Answer 4

If you can compute the address for your goto or jmp, you can simulate arbritary conditionals. I occasionally used this to simulate "ON x GOTO a,b,c" in ZX Basic.

If "true" has the numerical value 1 and "false" 0, then a construction like:

if A then goto B else goto C

is identical to:

goto C+(B-C)*A

So, yes, with a "computed goto" or the ability to self-modify, a goto or jmp can act as a conditional.

Answer 5

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.