Question

Understanding the Halting Problem

Answer 1

You misunderstood the logic. Program Hal, the same Hal, cannot answer whether Barrie will halt, ie. it's not actually perfect.

Answer 2

It's not Barrie that can't answer whether or not Barrie halts: it's *Hal* that can't. Since this construction works for *any* Hal, this means that no Hal can solve the Halting problem for all inputs.

Answer 3

Here's the argument, presented in what I think is a clearer way. We're going to proceed with a proof by contradiction (if you don't know what that is, then I'm afraid the Halting problem may be a little bit beyond you at the moment).  

Suppose Hal exists. So Hal is a program, such that Hal(p,x) returns "YES" if p(x) halts, and returns "NO" if p(x) doesn't ever halt, for *any and all programs p* and *any and all values x*.  

Now we invent a new program Barry. Barry is implemented as follows:  

Barry(p) =  
  if Hal(p, p) = "YES" then RUN FOREVER  
  otherwise HALT  

In other words, if Hal says "NO", Barry halts, and if Hal says "YES" then Barry just runs in an infinite loop forever. Note that we're giving p itself as input - this is allowed because all programs can be stored as data, and all data can be interpreted as a program.  

Now let's see what happens if we do this: Barry(Barry). Well, let's go through the definition, replacing every p with a Barry:  

Barry(Barry) =  
  if Hal(Barry, Barry) = "YES" then RUN FOREVER  
  otherwise HALT  

But remember that Hal(p, x) means "return YES if p(x) halts, else return no". So Hal(Barry, Barry) means "return YES if Barry(Barry) halts, else return NO".  

Now there are two possibilities: either Barry(Barry) halts, or it doesn't halt. Let's go through the two possibilities.  

* Suppose Barry(Barry) halts. Then Hal(Barry, Barry) would output "YES", which means Barry(Barry) will RUN FOREVER - i.e. it won't halt.  

* Suppose Barry(Barry) doesn't halt. Then Hal(Barry, Barry) would output "NO", which means Barry(Barry) will halt immediately - i.e. it halts.  

So now we have a conundrum. If we assume Barry(Barry) halts, it turns out it doesn't halt after all. But if we assume it doesn't halt, then it does halt. But ALL programs either halt or don't halt, there's no in-between. That means Barry can't possibly exist as a real program. But look again at the definition of Barry:  

Barry(p) =  
  if Hal(p, p) = "YES" then RUN FOREVER  
  otherwise HALT  

There is absolutely nothing wrong with this program. Everything here is easy and well-defined...except for Hal. We only *assumed* Hal exists. All the other bits ("if", "RUN FOREVER", "HALT") are easy to implement. But Hal is the only thing we assumed existed without proof. It follows then that Hal must be the bit that can't exist - if Hal existed, we could construct Barry, and that's not possible, therefore Hal can't exist. QED.

Answer 4

It's important to remember that with these kinds of problems, the proof is for a *universal algorithm*.

It's entirely possible to build halting algorithms for specific types of problems.

Answer 5

Have you figured it out? I think people already elaborated well on it, but if you didn't feel free to ping me.

The main mistake you make is that: the proof doesn't "modify" Hal into Berry, it uses (original, correct) Hal inside Berry

Answer 6

When I think about the halting problem, it seems a workaround is to construct a Hal algorithm that itself might just hang on certain inputs, so if the input halts it returns true, if it runs forever it returns false, but if it is paradoxical, the algorithm runs forever.

Is this disallowed? Is there still a paradox if the halting algorithm is allowed to take 3 states: true, false, or run forever or might it be possible to build an algorithm that is guaranteed to return true or false in a finite amount of time for all non paradoxically inputs? (I feel like there's probably a way to make this lead to a paradox also...)