We can definitely have deterministic Turing-complete programs. Do you mean you want totality? I agree that's nice, but in practice, being free from side-effects

We can definitely have deterministic Turing-complete programs. Do you mean you want totality? I agree that's nice, but in practice, being free from side-effects is likely more important than ensuring the program halts.