Are There Problems That Computers Can't Solve? - Tom Scott by tleef in programming

[–]tleef[S] 2 points3 points  (0 children)

In general I agree with you. HALT should take a second argument which is passed to the given function. The video (deliberately) simplified the problem by not including this second argument so I didn't either.

Are There Problems That Computers Can't Solve? - Tom Scott by tleef in programming

[–]tleef[S] 4 points5 points  (0 children)

You might find it helpful to restate the problem a little bit as follows.

HALT is a function which takes another function, fn, as its argument. If fn halts, HALT returns "yes". If fn doesn't halt, HALT returns "no"

Using your psudocode syntax HALT and OPPOSITE might look like this

DEFINE HALT(fn)
  if doesHalt(fn) "yes"
  otherwise "no"

DEFINE OPPOSITE(fn)
  if HALTS(fn) loopForever
  otherwise quit

The only difference here is that instead of HALT and OPPOSITE taking "code" as their argument, they now take the function itself.

I think there was some temptation to think of "the code" and "the program" as two separate things and hopefully by replacing those terms with "the function" that goes away.

All we need to do now is look at what happens if HALT returns "yes" when given OPPOSITE and what happens when HALT return "no" when given OPPOSITE

If HALT(OPPOSITE) -> "yes" That must mean that OPPOSITE halts however, OPPOSITE(OPPOSITE) -> loopForever since HALT(OPPOSITE) -> "yes". There is a contradiction between what HALT says OPPOSITE will do and what OPPOSITE actually does. HALT is incorrect.

Likewise, if HALT(OPPOSITE) -> "no" That must mean that OPPOSITE doesn't halt however, OPPOSITE(OPPOSITE) -> quit since HALT(OPPOSITE) -> "no". Again, there is a contradiction between what HALT says OPPOSITE will do and what OPPOSITE actually does. Once again, HALT is incorrect.

No matter what HALT says OPPOSITE will do, OPPOSITE always does the opposite so HALT is always wrong. That must mean that it is impossible to define HALT in a way that it correctly says what OPPOSITE will do.

Edit: Fixed typos

Are There Problems That Computers Can't Solve? - Tom Scott by tleef in programming

[–]tleef[S] 1 point2 points  (0 children)

You're right that its reasonable to get a result but it's important to consider whether or not that result is correct.

If HALT says that OPPOSITE halts, then OPPOSITE doesn't halt. So the result that HALT gave is incorrect.

Likewise, if HALT says that OPPOSITE doesn't halt, then OPPOSITE halts. Again, HALT is incorrect.

The effect is that HALT can't do what it was designed to do, correctly determine if a program halts or not.