There is a fairly large subset of useful programs that can be proven to halt. Anything that uses straight-line linear control flow. So can anything with that plus conditionals. So can that plus foreach loops, as long as iterators do not reflect updates to their underlying collections. Add a "forever { ... }" construct and you can prove that the program will not halt; in combination with the other constructs, you can prove liveness on each request handler while also guaranteeing that the server itself will never go down.
The two constructs you have to watch out for are loops that mutate state used in the conditional and unbounded recursion. Even for these, there are techniques to increase the set of programs that can be reasoned about, eg. using dataflow analysis to identify which state is mutable and preventing it from being used in conditionals or tracking data & codata through the typesystem.
http://blog.sigfpe.com/2007/07/data-and-codata.html
Such a language would not be Turing-complete; you won't be able to write an interpreter for a Turing-complete programming language in it. But the majority of common business problems don't require an interpreter for another programming language; most of them focus on storing data, triggering events, or computing functions of data.
http://mathoverflow.net/a/153106
Because of the list of correct answers for a finite subset of the Halting Problem is finite, the Turing machine you mention does exist, but we not only can't find it, we can't know when we've found it!
Where the Math Overflow post mentions that "experts could compute the particular value of n", there has recently been such a bound published in a thesis, such that we can be confident that we can never construct or recognize the solutions beyond that point (using a particular axiomatization of mathematics).
You referred to the idea that "you can have a Turing machine that solves this", and we can agree on that with the caveat that, above certain problem instance sizes, you can't know or verify in any way that you have such a Turing machine!
My argument stands. Unless the halting problem is overcome, there will still be jobs for humans to write Turing-complete programs.
Turing machine X can produce programs that meets certain specifications => Turing machine X solves the halting problem.
Here's a nice simple one for you:
def collatz(n):
while n > 1:
n = n/2 if n%2==0 else 3*n+1
In practice, programming doesn't require solving halting problems. We write programs that are on average easy to analyze, especially if you're calibrating the scale with busy beavers. There's no fundamental reason that a computer program can't collect requirements, collect clarifications, and translate those specs into executable code. Clearly it's hard (How do you do the translation? Optimizing Prolog isn't easy! And how do you avoid asking for millions of things that humans take for granted as obvious?), but I don't see anything that makes it impossible.
The halting problem doesn't really matter that much in this context. Just spawn up a bunch of threads that churn away at the problem, using random mutations, and any that go on too long can just be considered flawed, regardless of whether they have any redeeming qualities.
Then you select the winners, based on the selection criteria, and churn away on some more mutations of those new variants.
In general, you will not be able to easily find P using a genetic algorithm (which amounts to a random walk through the space of all programs) even with many threads. The problem is that the algorithm is exponential in the length of P. It only works if you only consider a very limited set of possible programs. E.g. very short programs or programs which are only slight variations on a known program.
The only way around the halting problem is to use something other than computation as we know it. I.e. an entirely new kind of machine based on different principals. And no, quantum computers do not solve the halting problem since they are still Turing-complete machines.