Is conditional branching a requirement of Turing-c

问题:

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?

回答1:

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.

回答2:

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.

回答3:

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.

回答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.

回答5:

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.

回答6:

You don't need conditional branching to build a Turing-complete machine, but of course any Turing-complete machine will provide conditional branching as a core feature.

It was proved that systems as simple as the Rule 110 Cellular Automaton can be used to implement a Turing machine. You sure don't need conditional branching to pull such a system from the bit bucket. Actually one could just use a bunch of rocks.

The point is that a Turing machine will provide the conditional branching, so what you are doing anyway by proving Turing completeness is somewhat implementing conditional branching. You have to do it without conditional branching at some point, be it rocks or PN-junctions in semi-conductors.

回答7:

If a machine can branch, then yes its Turing complete.

Hoever there are also machines which can't jump branch or even IF but are still Turing complete.

The reason having conditional-branching automatically makes any computer Turing complete is thus.

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 too stores the correct output for that input.

So to finally clarify; If you have conditional branching your computer is necessarily computationally equivalent. HOWEVER, there are plenty of other ways for a computer to achieve completeness. (lambda, IF's, CL)