5 ms·

Programming jobs are protected by the halting problem. It has been proven that no program cannot detect if other programs halt or not (i.e. goes into an infini

Programming jobs are protected by the halting problem. It has been proven that no program cannot detect if other programs halt or not (i.e. goes into an infinite loop or completes). I paraphrase, but this is the general idea. As long as this is true computers will not be able to program themselves except in very limited ways. 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.

nwah1 10y ago
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.
- jcoffland 10y ago
  Sorry multiple threads will not get you around the halting problem. The brute-force genetic algorithm you describe also suffers from the halting problem. Just look at the algorithm as a whole. Say you are searching for a program P and you have some criteria for recognizing it, including a maximum run-time. There is no way to know if the genetic algorithm will ever find P or will itself just run indefinitely. 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.
jmtulloss 10y ago
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.
nostrademons 10y ago
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 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.
- liadmat 10y ago
  The halting problem also makes an assumption on the program's size. In practice we probably only care about programs under, say, a billion petabytes (or any other finite limit you can think of). In theory you can have a Turing machine that solves this regardless of the program's structure.
  - schoen 10y ago
    If you mean "programs that can only use a billion petabytes of storage", then that's true, but if you mean "programs whose code is less than a billion petabytes long", it's not true. (Someone recently calculated a result that I think can be interpreted directly as an actual decidability bound, and it's dramatically shorter than that.)
tomp 10y ago
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.
Strilanc 10y ago
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.

nwah1 10y ago

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.

jcoffland 10y ago
Sorry multiple threads will not get you around the halting problem. The brute-force genetic algorithm you describe also suffers from the halting problem. Just look at the algorithm as a whole. Say you are searching for a program P and you have some criteria for recognizing it, including a maximum run-time. There is no way to know if the genetic algorithm will ever find P or will itself just run indefinitely. 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.

jmtulloss 10y ago

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.

nostrademons 10y ago

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 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.

liadmat 10y ago
The halting problem also makes an assumption on the program's size. In practice we probably only care about programs under, say, a billion petabytes (or any other finite limit you can think of). In theory you can have a Turing machine that solves this regardless of the program's structure.
- schoen 10y ago
  If you mean "programs that can only use a billion petabytes of storage", then that's true, but if you mean "programs whose code is less than a billion petabytes long", it's not true. (Someone recently calculated a result that I think can be interpreted directly as an actual decidability bound, and it's dramatically shorter than that.)

tomp 10y ago

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.

Strilanc 10y ago

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.