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).