Question about the Halting Problem

993

May 26, 2007 04:42 AM

Quote:that can be proven to be unsolvable by reducing them to the Halting problem.

Actually in order to prove something uncomputable you'd need to reduce the halting problem to it (as that means if you have a solution to that problem you'd have a solution to the halting problem). For a simple example of something computable that could be reduced to the halting problem take the decision problem of deciding whether something is the smallest element of the list. You'd construct a program that takes a list and an element of the list, it loops through the list and if it finds no element smaller than the element you give, it halts otherwise it loops forever. Then the problem of whether the element you give is the smallest member of the list becomes, given this program (detailed above) and this list and an element as input, does the program halt? Thus we have reduced the problem to the halting problem, though the original problem is clearly computable.

kSquared

1,356

May 26, 2007 06:50 AM

Quote:Original post by Monder
Actually in order to prove something uncomputable you'd need to reduce the halting problem to it (as that means if you have a solution to that problem you'd have a solution to the halting problem).

Actually, you're saying the same thing either way. "X reduces to Y" means "X is Y"; the precise nature of "is" here depends on the problem you're solving. Whether we say "X reduces to Y" or "Y reduces to X" just depends on which expression is perceived to be more complicated.

Because it's generally easier to reduce things to simpler forms, proofs generally show how a more complicated solution is like a previously solved, simpler form. For example, consider the statement "(m^2 - n^2)/(m - n) == m + n". We can prove this either by:

(1) Try to gradually make changes to "m + n" until you arrive at "(m^2 - n^2)/(m - n)".
(2) Try to gradually make changes to "(m^2 - n^2)/(m - n)" until you arrive at "m + n".

If you're successful either way, you've shown that X is Y.

Quote:Original post by Monder
For a simple example of something computable that could be reduced to the halting problem take the decision problem of deciding whether something is the smallest element of the list.

[...]

Thus we have reduced the problem to the halting problem, though the original problem is clearly computable.

The halting problem doesn't ask whether a specific program will terminate. It asks whether it's possible, in general, to decide if any given program will terminate.

In other words, the halting problem asks whether it's possible to write a function H(p) that takes a program p as input, and that returns "true" if the program terminates and "false" if it doesn't. Your program is simply one example of a possible p (any program is, of course), but it's not an H. An H that only works for one particular p is also not an H, so either way, this example does not reduce to the halting problem.

Here's another example: imagine that, instead of H, I ask you to write S(n), the successor function. This simply takes any integer n as input and adds one to it. Would you be satisfied that this was really the successor function if it only worked with an input of 271?

Your program is trivial enough that you can show that it will, in fact, always halt. You can actually do even better, since you can say how the expected running time of the program is (number of list elements multiplied by the time cost to make a comparison). As long as the list is finite and there is a finite upper bound on how long it takes to determine if a particular element is the smallest thus far, it will terminate.

- k2"Choose a job you love, and you'll never have to work a day in your life." — Confucius"Logic will get you from A to B. Imagination will get you everywhere." — Albert Einstein"Money is the most egalitarian force in society. It confers power on whoever holds it." — Roger Starr{General Programming Forum FAQ} | {Blog/Journal} | {[email=kkaitan at gmail dot com]e-mail me[/email]} | {excellent webhosting}

ToohrVyk

1,596

May 26, 2007 07:09 AM

Quote:Original post by kSquared
In other words, the halting problem asks whether it's possible to write a function H(p) that takes a program p as input, and that returns "true" if the program terminates and "false" if it doesn't. Your program is simply one example of a possible p (any program is, of course), but it's not an H. An H that only works for one particular p is also not an H, so either way, this example does not reduce to the halting problem.

Here's another example: a program M(x,a) which determines if x is the minimal element of array a. We build the program:

program P is:  for i = 1 to a.size do    while x > a do () done  done

Then, x is the minimal element of a if and only if H(P) returns true (where H is a program solving the halting problem). We have effectively reduced our "is minimal element" problem to the halting problem: if a solution to the halting problem exists, then a solution to the minimal element problem exists.

In general, in computability theory, reduction is a complex relationship, which depends on the way in which the reduction is done (time and space complexity, for instance) and is generally not symmetrical. The typical intuition is that X is A-reductible to Y if there exist two processes with property A so that a problem in X can be transformed into a problem in Y, and a solution in Y can be transformed into a solution in X. This implies that being able to solve problems in Y lets you solve problems in X, but not necessarily the reverse.

Blog — Facebook

Monder

993

May 26, 2007 07:11 AM

Quote:
Actually, you're saying the same thing either way. "X reduces to Y" means "X is Y"; the precise nature of "is" here depends on the problem you're solving. Whether we say "X reduces to Y" or "Y reduces to X" just depends on which expression is perceived to be more complicated.

Depends upon how you define reduction, here I'm defining it as in complexity theory where a reduction is a function that given two languages L1 and L2 which are decidable by turing machines T1 and T2 will take a member of L1 and transform it into a member of L2. Futhermore anything that isn't in L1 will be transformed into something that isn't in L2. There is no requirement for this function to be injective, or surjective, thus you can define a reduction that will only work one way. This is generally used in proofs of NP-Completeness you take a language known to be NP hard and define a reduction that can reduce it to another language you wish to prove NP hard in polynomial time (and of course the other part is proving the language you wish to prove NP complete is indeed in NP).

Now about my reducing to the halting problem example, here it is again but slightly more formally so it's clearer what I actually mean.

Here when I say halting problem, I mean given a encoding of some computable function P and an input to that function x, can you build a turing machine that given P and x as inputs halts in either an accepting state if P(x) halts or halts in a rejecting state is P(x) does not halt? Thus the language of the halting problem (lets call it H) is a set of pairs (P, x) where if (P, x) is in H then P(x) halts, otherwise if (P, x) is not in H then P(x) does not halt (Another way to phrase that halting problem would be can you build a turning machine that decides membership of H?).

Now take my smallest element of list decision problem. Here the language (lets call it SMALL) is again a set of parts (L, x) where L is a finite list and x is an element from that list. A pair (L, x) is in SMALL if and only if x is a member of L and it is the smallest member of L.

We then define a reduction from SMALL to H as follows: Given (L, x) in SMALL construct a turing machine that iterates through L and takes x as the initial contents of the tape. If at any point it finds an element of L that is smaller than x it loops forever, if it reaches the end of the list and x has not been found (i.e. x is not in L) then it loops forever, otherwise it halts. Clearly the machine will halt if and only if x is in L and it is the smallest element of L, otherwise it will not halt. Thus we can reduce SMALL to H and if we can decide membership of H (i.e. we can solve the halting problem) we can decide membership of SMALL.

Now SMALL is clearly a decidable language, while H is not, hence we can reduce things that are decidable to things that are not (actually if you allow L to be infinite, then you can probably manage to reduce H to SMALL, though I won't attempt that here).

kSquared

1,356

May 26, 2007 07:20 AM

Quote:Original post by ToohrVyk
Then, x is the minimal element of a if and only if H(P) returns true (where H is a program solving the halting problem). We have effectively reduced our "is minimal element" problem to the halting problem: if a solution to the halting problem exists, then a solution to the minimal element problem exists.

I agree with that, I just don't agree with the other relationship: that merely because you had a P that was easy to H-solve, that your P is an H, which is what the other post seemed to be saying.

Quote:In general, in computability theory, reduction is a complex relationship, which depends on the way in which the reduction is done (time and space complexity, for instance) and is generally not symmetrical.

Well, there are two types of reduction: Turing (which is symmetrical) and many-one (which isn't). The former is more powerful, because it says that a solution to either is a solution to both. But the latter is more useful in the pragmatic sense, because we don't generally get lucky enough to find Turing reductions (in fact, finding any TR for most "hard" problems amounts to determining that P is NP).

- k2"Choose a job you love, and you'll never have to work a day in your life." — Confucius"Logic will get you from A to B. Imagination will get you everywhere." — Albert Einstein"Money is the most egalitarian force in society. It confers power on whoever holds it." — Roger Starr{General Programming Forum FAQ} | {Blog/Journal} | {[email=kkaitan at gmail dot com]e-mail me[/email]} | {excellent webhosting}

Question about the Halting Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Question about the Halting Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines