[ogogmad]

Any program which you apply FHE to needs to be expressed as a circuit, which implies that the time taken to run a computation needs to be fixed in advance. It's therefore impossible to express a branch instruction (or "if" statement, if you prefer).

The circuits are built out of "+" and "×" gates, which are enough to express any polynomial. In turn, these are enough to approximate any continuous function (Weierstrass's approximation theorem). In turn, every computable function on the real numbers is a continuous function - so FHE is very powerful.

[jlokier]

> In turn, every computable function on the real numbers is a continuous function

That doesn't seem right. Consider the function f(x: ℝ) = 1 if x ≥ 0, 0 otherwise. That's computable but not continuous.

[ogogmad]

That's uncomputable because equality of real numbers is undecidable. Think infinite strings of digits.