0
$\begingroup$

This question already has an answer here:

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 dont know the results (or execution steps) of functions beforehand?

Thanks in advance

$\endgroup$

merged by Gilles 'SO- stop being evil' Feb 3 '15 at 14:57

This question was merged with Can we write algorithms without conditional statements? because it is an exact duplicate of that question.

Browse other questions tagged or ask your own question.