I agree. These are totally legitimate ways to still use FHE even if you need to compute a Turing-complete thing. It doesn't thwart my theoretical point, because

I agree. These are totally legitimate ways to still use FHE even if you need to compute a Turing-complete thing. It doesn't thwart my theoretical point, because you're not doing pure FHE anymore: you're using FHE for the "Turing-incomplete" part of your algorithm, plus some external oracle to check for termination. Practically this might still be an acceptable way to tackle the problem. I mean, "practically" as much as FHE itself is.