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?
