> So, you can't express the programs that never terminate, but can you express all the programs that would terminate?

This gets philosophical - would the program "Y {f => x => if(x is a proof of the inconsistency of PA via the Goedel encoding) 0 else f(x+1) } 0" terminate? If you assume consistency of PA then no.

> Point in case, you probably shouldn't ever want to use a language for the specific feature that could express a non-deterministic program.

Well the mu operator or equivalent (informally, the inverse operator) is an extremely useful feature. Many useful programs can't be written strictly primitive recursively (as a trivial example, you can't compute the Ackermann function). I have hope that we can find more restricted versions of mu that let us express all the programs we want to, but that's a decidedly nontrivial problem.