Is conditional branching a requirement of Turing-completeness?

Viewed 2996

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?

7 Answers

If a machine can branch, then yes it's considered Turing complete.

The reason is having conditional-branching automatically makes any computer Turing complete. However, there are also machines that can't jump branch or even IF but are still considered Turing complete.

Processing is just the process of identifying inputs in-order to select outputs.

Branching is one way to mentalize this process, the condition of the jump is what can classify inputs, the place you branch to stores the correct output for that input.

So finally, to clarify things:

If you have conditional branching your computer is necessarily computationally equivalent to a Turing machine. However, there are plenty of other ways for a computer to achieve Turing completeness (lambda, IF's, CL).

Related