If you restrict yourself to a turing incomplete language, checking a specification no longer reduces to the halting problem. In fact, there are many systems that do exactly this, and most of these systems are perfectly capable of sorting a list and proving that the list is sorted.
However, I think the real point is that there are at least dozens of smart people who are working on this exact problem all day, every day. The OP shows neither a deep understanding of why previous attempts at this have failed or really, any knowledge at all about the state of the field of programming language research.
At least, I'll learn a lot. At most, we get something new with the help of other people.
Case in point: Resharper will tell me "This function never returns" in cases where it obviously wont return, and also offer to simplify methods that only ever return a single value despite what looks like a complex set of if-statements.
So, if it is possible to write a program to determine if a specific subset of all possible programs will terminate, is it possible to write a program that can generate a subset of all possible programs from a specific subset of all possible specifications?
I can't be perfect. But might it be useful?
While this is true in general, our current "solution" to the problem - hire a human programmer, give him the spec, and set him loose - doesn't do any better here. The problems we as an entire field "want to solve" are, in general, formally undecidable and reducible to the halting problem, but we get by anyways because it turns out that you can get a lot of useful work done even without solving the general problem.
I see no reason that a well-designed system couldn't similarly leverage "special cases" that are not undecidable. How efficiently this could be done is another matter, but I think step one in that direction is to accept a pretty major loss of generality - after all, that's how humans get the job done, and for the most part we're still able to turn most of the specs that we're faced with into working code, given enough time.
So, academically, even the "virtual human" approach doesn't work since it doesn't answer correctly for every single program. Practically, you're right, having a virtual human would be good enough for most uses.
That said, I wouldn't want to use a virtual human for this due to ethical concerns :-).
n = 4;
goldbach = true;
while(goldbach) {
goldbach = isSumOfTwoPrimes(n);
n += 2;
You just have to prove the Goldbach Conjecture. :-)
1. Given a formal specification, find a program that meets the specification.
2. The apparently simpler problem of checking whether a given program meets a specification.
Both are undecidable. That said, there is an extensive literature on practical approaches to this problem. They generally suffer from intractability.
http://cfpm.org/pub/papers/tiofdm.pdf
I suggest looking at Robert Harper's book on type theory instead.