Arbitrary programs that terminate on every input (no infinite loops), and with a few important caveats:

1. Random access (reading input-dependent memory address) must be simulated with linear scans of the array.

2. Input-dependent branches must be transformed as follows: both branches are evaluated, and the side effects must be combined using the branch condition (e.g. x <- xc + new_x(1-c)).

3. Loops with input-dependent bounds must be unrolled to their maximum number of iterations (this is not always easy to compute).

In general you would probably write your programs in a special-purpose language that is easy to compile for this model of computation. Efficiency can suffer for some algorithms -- sorting winds up being O(n lg^2 n) instead of O(n lg n), for example.

Also the best FHE schemes are still nowhere near practical for the majority of computations people care about.

I didn't realize HE was still so primitive. Whenever there is a privacy kerfulffle for thing X, HN commenters say "X should be implemented with homomorphic encryption instead!"

LOL

So arbitrary Turing-complete programs have not been figured out yet, I take it?