0 like 0 dislike
0 like 0 dislike
Understanding the Halting Problem

6 Answers

0 like 0 dislike
0 like 0 dislike
You misunderstood the logic. Program Hal, the same Hal, cannot answer whether Barrie will halt, ie. it's not actually perfect.
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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
0 like 0 dislike
0 like 0 dislike
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...)

Related questions

0 like 0 dislike
0 like 0 dislike
2 answers
a_dalgleish asked Jun 21
Contributing to the right math area, If all areas are equally curious
a_dalgleish asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
ConradDubai asked Jun 21
How to “topologize” the fundamental group: a primer
ConradDubai asked Jun 21
0 like 0 dislike
0 like 0 dislike
3 answers
MattWoosie asked Jun 21
If you had to pick the best method for solving Poisson’s Equation, which would it be and why?
MattWoosie asked Jun 21
0 like 0 dislike
0 like 0 dislike
8 answers
UnShowNoTanLate asked Jun 21
Is there research on graphs where the edges can connect more than two nodes?
UnShowNoTanLate asked Jun 21
0 like 0 dislike
0 like 0 dislike
15 answers
marcuscallender asked Jun 21
Fixing the "I Must Prove This, Myself!" mindset
marcuscallender asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!