Comment by jcoffland

The halting problem is often misunderstand as "computers can never detect if a program halts". It actually states that "computers can never detect if an arbitrary program halts".

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.

Humans can't solve the halting problem either.

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

Is the above program guaranteed to halt for all integer inputs?

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.

If we take the simple case of genetic algorithms, we already know that it is possible to brute-force the problem of programming.

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.

There exist equivalent problems for human minds, though. E.g. the Riemann Hypothesis - people keep trying to find the proof, but noone knows if the proof exists, so it's not a given that the search will ever finish.

That's the only way to totally solve it. You can get pretty far with imperfect shortcuts. Maybe far enough that it doesn't matter.