Can we write algorithms without conditional statements?

Question

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.

Consider the factorial problem, we would typically define the algorithm as

Solution 1.

int fact(int n)
{
if n == 0 then
 return 1;
else
 return n*fact(n-1);
}

An alternative would be to define the function fact as

Solution 2.

int fact(int n)
{
 if n == 0 then return 1;
 elseif n == 1 then return 1;
 elseif n == 2 then return 2;
 elseif n == 3 then return 6;
 ....
 all cases define as above
}

Also, another solution would be to have functions like:

Solution 3.

int fact0()
{
return 1;
}

int fact1()
{
return 1*fact0;
}

int fact2()
{
return 2*fact1;
}

int fact3()
{
return 3*fact2;
}

Then we would have an array of function pointers p which we would have to index according to the factorial we want to determine, such that p[0] points to fact0, p[1] points to fact1, and so forth.

I know that this might sound dumb, but it actually works! What makes solution 1. a valid argument to show that conditionals are required to compute the factorial?

Some additional thoughts on my part:

1. Is solution 1 the only true "algorithm"? Because the other 2 solutions to not seem to "compute" anything
2. Are conditionals required only because we don't know the results (or execution steps) of functions beforehand?

Answer 1

Here is a Turing complete "programming" language. It has just two constants, called $K$ and $S$, and one operation called "application", written $x \cdot y$. The two constants satisfy the rules $$(K \cdot x) \cdot y = x$$ and $$((S \cdot x) \cdot y) \cdot z = (x \cdot z) \cdot (y \cdot z).$$ This is known as a combinatory algebra and is well known to be Turing complete. There is an actual programming language based on $S$ and $K$, called unlambda. I think we can agree that there is no builtin conditional. Of course, since this language is Turing complete, it can also simulate conditional statements.

Answer 2

You'd have to stretch the definition of "conditional" beyond all credibility to say that Turing completeness requires conditionals. Many minimalistic models of computation lack anything remotely resembling a conditional statement, any statement at all, or a conditional anything.

For a well-known example, take the untyped lambda calculus. It consists only of defining lambda abstractions and applying them (unconditionally), yet it is Turing complete. Arguable even simpler, the SKI calculus: Which of the following combinators is a conditional?

Ix = x
Kxy = x
Sxyz = xz(yz)

One problem with your proposals #2 and #3 is that they require (countably) infinite programs to define the function for all inputs. This is generally very undesirable (for starters, this model might decide undecidable problems, or more precisely, have a higher Turing degree).

Oh, of course you're just talking about fewer, more well-behaved and regular programs, where the function for each n is generated by a finite mechanical rule. Guess what? Now that rule is your program, with or without conditionals. The expansion for various values of n is just a trace of the execution for each n.

Answer 3

Yes, some sort of conditional is required in a Turing-complete language. It doesn't have to be the if-then-else construct found in most programming languages: there are many other ways to design a conditional. Something in the language needs to capture the essence of the conditional statement, namely, making the computation path depend on the data.

If the computation path is independent of the data, then for a given program, the number of computation steps would be predetermined, independently of the input. This is incompatible with Turing-completeness, which allows writing programs that terminate for some inputs and don't terminate for other inputs.

If-then-else is in some sense a minimalist conditional: it takes one bit of data and selects between two execution paths based on the value of this bit.

It's possible to define if-then-else as a macro on top of other primitives. An obvious one is case/switch/match statements, which generalize the idea of selecting execution paths based on some value. It's also possible to define if from some more complex primitive that combines a conditional with some other form of flow control, such as a while loop.

Note that an if_then_else function in a strict language (a language where the arguments of a function are evaluated before the function call) is not a conditional in this sense, because the computation path is always the same (first compute the arguments, then compute the result of the if_then_else call). An if_then_else function needs to be call-by-need, for its then-value and else-value arguments.

A computed goto statement is another form of conditional. That's what is sketched in your solution 3 is (though your solution 3 isn't a proper definition of a factorial computation, since it would require defining an infinite family of functions). goto (address1 * condition + address2 * (1 - condition)), where condition can be 0 or 1 standing for true or false, is equivalent to if condition then goto address1 else goto address2 in a language with a basic if-then-else conditional.

In a Turing machine, conditionals are implemented in a way that's reminiscent of computed goto: at each computation step, the automaton reads a value from the tape and the transition taken by the automaton depends on that value. Each computation step essentially includes a case statement.

In the lambda calculus, conditionals stem from the lack of separation between data and computation — it's all functions. If you want to define a function that makes different computations depending on its argument, just make it apply its argument to something! A basic implementation of if-then-else in the lambda calculus is: $\lambda c. c x y$ — this function takes a “boolean” $c$ and applies it to two arguments. See $\lambda x. \lambda y. x$ as true and $\lambda x. \lambda y. y$ as false and you recognize $\lambda c. c x y$ as an if-then-else function. (As noted above, this requires an evaluation strategy that isn't pure call-by-value. The lambda calculus with call-by-value reduction is not a Turing-complete model.)

Any Turing-complete set of combinators will have some form of conditional. For example, in SKI, $S$ embeds a conditional, because it applies (computation) its first argument (datum).

Answer 4

Solution 2 IS an algorithm, but it isn't equivalent to Solution 1. And this way of writing functions certainly isn't Turing complete.

The only way you can express Solution 1 in the style of Solution 2 is making the program infinite, but a Turing machine, by it's very own definition must have a finite set of states.

Of course the style in which you described Solution 2 can describe some automata. I mean, if you go on with the idea of having a table that maps input into functions – I can't prove it formally now – I'm pretty sure it will lead to something equivalent to a deterministic finite automaton, which can describe some languages/problems, but is far from a Turing machine.