6
$\begingroup$

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?
$\endgroup$
  • 5
    $\begingroup$ Are you asking whether it is possible to have a programming language which has no conditionals, but is Turing complete? Sure, $\lambda$-calcuus, which is even older than Turing machines. $\endgroup$ – Andrej Bauer Feb 2 '15 at 23:13
  • 2
    $\begingroup$ "i read that for a language/machine to be turing complete it is required that it has some sort of conditional." - Whatever you read is wrong (or you misunderstood what you read). $\endgroup$ – D.W. Feb 2 '15 at 23:22
  • $\begingroup$ Solution 2 has conditions, not sure why you seem to think it's a counter example. And in solution 3 you've merely offset the condition to the callee. How does the callee call the right function? With a condition. $\endgroup$ – Mooing Duck Feb 2 '15 at 23:41
  • 2
    $\begingroup$ Neither solution two or three are algorithms, they are brute lookup tables. $\endgroup$ – user8632 Feb 3 '15 at 3:15
  • 1
    $\begingroup$ @LegoStormtroopr Table lookup is an algorithm -- if the table is finite. $\endgroup$ – Raphael Feb 4 '15 at 10:39
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this is mostly cheating. Just because there is no single language feature that you could point at and say "this is conditional" doesn't mean the language doesn't have conditionals. $\endgroup$ – svick Feb 3 '15 at 0:34
  • 3
    $\begingroup$ You could think of it as cheating, or you could think of it as trying to answer the question about what exactly it means for a language to "have conditionals". This is important, because programming languages don't have a general "law of the excluded middle" operator. The point is that conditional tests and branches can be built out of lower-level constructions, so maybe you need to look at those constructions to address your question. $\endgroup$ – Pseudonym Feb 3 '15 at 1:24
  • 1
    $\begingroup$ +1 good answer but it would be nice to explain in particular how it "implements" a conditional statement. re svicks comment, it is quite a subtle problem to technically/ mathematically define exactly what constitutes a "conditional" in a programming language. $\endgroup$ – vzn Feb 3 '15 at 5:53
  • 1
    $\begingroup$ @svick: I anticipated your comment and so I already replied to it in the text: any Turing complete programming language can simluate anything that a Turing machine can do, therefore it can simulate conditionals. So, what do you want? $\endgroup$ – Andrej Bauer Feb 3 '15 at 9:24
  • 1
    $\begingroup$ Perhaps there is a distinction to be made here between having a turing complete language with no built in if-then-else and a language that can solve the function problem of corresponding to if-then-else. Any turing complete language can solve that problem so any turing complete language "has conditionals" in that sense. On the other hand Andrej has presented a turing complete language with no conditional. $\endgroup$ – Jake Feb 4 '15 at 0:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You'd have to shrink the definition of “conditional” to ridiculous specificity to claim that the lambda calculus or the SKI calculus doesn't include a conditional. In the lambda calculus, the ability to apply any datum is a kind of ultimate conditional: it allows any datum to determine the path of the computation. In SKI, S is a conditional (combined with other things, in particular duplication). $\endgroup$ – Gilles 'SO- stop being evil' Feb 3 '15 at 22:43
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think the issue here is terminology. There are plenty of Turing maching models without "conditional statements" -- in particular those without any statements -- but certainly none that computes independently of the input. $\endgroup$ – Raphael Feb 4 '15 at 8:19
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Solution 2 IS an algorithm" -- not by the "definitions" I know. A finite representation is a usual requirement. $\endgroup$ – Raphael Feb 4 '15 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.