Can Fully Homomorphic Encryption do comparisons? I encountered a simple function that even FHE cannot solve. Here's it:

int f(a,b,c,d){
   if(a+b&gt;c+d) return a+c;
      else return b+d;
}


Since FHE is not order-preserving, one can't figure out whether a+b>c+d without the decryption key. That means even if practical FHE was implemented, f(a,b,c,d) cannot be computed in the Cloud independantly and securely. Not to mention linear regression, or more complex functions.

So I wonder with such an obvious limitation, why is FHE called "the holy grail of cryptography"?
This is simply not true. The above function can perfectly be homomorphically computed on FHE ciphertexts encrypting the inputs. There is no such "obvious limitation", and I wonder where your certainty comes from.

Asking whether FHE is Turing complete does not really make sense: FHE is a cryptographic primitive, not a general computing device. If this is what you meant, yes, we can evaluate any (polysize) function on encrypted inputs using the FHE evaluation algorithm. More precisely, we can evaluate any polysize boolean circuit on the input, in a private way (i.e. the inputs and the outputs are not leaked). If you want to evaluate Turing machines, it is more complicated in general (and you must give up on hiding the exact running time of the computation for this to be interesting), but it can also be done.

EDIT: from your comments, I now understand your question more clearly. Yes, FHE will never reveal the intermediate computation in the clear. This means that when you run a program on encrypted values, the computation pattern will have to be oblivious of the exact data. This does not make such computation impossible, as you seem to believe, but simply less efficient.

For example, suppose that you must evaluate the following program: if $a &gt; b$, output $f(x)$, otherwise, output $g(x)$. Using FHE, you would proceed as follows: compute the bit $\beta$ which is $1$ if $a &gt; b$, and $0$ otherwise, and output $\beta\cdot f(x) + (1-\beta)\cdot g(x)$. You can compute this on encrypted data, and you never need to know the exact value of $\beta$ to evaluate this program with FHE.

The FHE computation does not need "the plaintext result", it simply must rely on an algorithm which works obliviously of the exact inputs, and it is usually not hard to convert a computation in an oblivious computation (although it's not always obvious either).