Instead of solving the halting problem, I will try to solve a less complicated problem in a similar manner.
Can we write a function that will predict if two given numerical inputs are equal. I will not create such function but, let's assume such function can exist and we will call it H. Now we have H, a function that works and solves our problem, but let's write another function and call it H+, a function that will negate the results of our perfectly working function.


def H(p1, p2):
   #perfectly working piece of code that will solve our problem
   # returns True if p1 == p2, else returns False

def H+(p1, p2):
   return not H(p1, p2)

Now when we have the code lets compare p1 = 1, p2 = 2. And let's use the function H+, why not, it is the same function as H, a function we know works. H+ just negates the results from H. The result of H+ is True, how can it be?? we know that 1 is not equal to 2 so we have a paradox here hence proving we cannot write a function to predict if two numerical values will be equal.

Now to the Halting problem,
If I understand correctly the Halting problem was prooven in a similar way; There is a machine H that can predict if a problem is solvable. There is a bigger machine that uses H but negates its results called H+. Then if H+ is fed into H+ it will create a paradox. Of course, H+ will not work. We assume machine H is the one that will give us the right result, why do we think that H will still work the same way after modifying it and turning it into H+??
What happens if we feed H+ into H will we still have the same paradox? I don't think so.

  • 1
    $\begingroup$ "The result of H+ is True, how can it be?? we know that 1 is not equal to 2 so we have a paradox". Where is the paradox? $\endgroup$ – Steven Oct 10 at 22:32
  • $\begingroup$ The function always gives us the correct result; we received the wrong result. This function can not give us the correct result and the wrong result at the same time. True means that 2 is equal to 1 but it's not. There is your paradox. $\endgroup$ – Blank Blank Oct 10 at 22:38
  • 1
    $\begingroup$ Please formally define "correct result" and "wrong result". Also clarify which function are you referring to when you say "the function". If I understood correctly $H^+(p1,p2)$ is defined as the logical not of the result of $H(p1,p2)$ which, in turn, is defined to return $\tt true$ if $p1=p2$ and $\tt false$ otherwhise. Therefore, for $1 = p1 \neq p2 = 2$ (as in your example) the "correct result" of $H^+(p1,p2)$ is $\neg H(1, 2) = \neg \tt false = true$, which is exactly what you get. $\endgroup$ – Steven Oct 10 at 22:44
  • $\begingroup$ You did understand correctly. My point was that the halting problem was provent to be impossible to solve in a similar way. There is a machine(H) that can solve the problem, then another machine was introduced, machine(H+). Machine (H+) changed the output of machine(H) and because testing the inputs on machine (H+) instead of on machine (H) resulted in a paradox we concluded that machine (H) is not possible. $\endgroup$ – Blank Blank Oct 10 at 23:01
  • $\begingroup$ In the proof for the halting problem the paradox is that, if you assume that a Turing machine $H(M)$ that can decide where a TM M halts (on the empty input string) exists, then you can define a turing machine $H^+(M)$ that halts iff M does not halt. But then $H^+(H^+)$ must simultaneously halt and not halt. Let $M=H^+$. If $H^+(M)$ halts then, by definition of $H^+$ and by the correctness of H, the TM M must not halt. This is a contradiction since $M=H^+$. We conclude that $H^+(M)$ does not halt. But then again, by definition of $H^+$ and H, we have that $M$ must halt, a contradiction. $\endgroup$ – Steven Oct 10 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.