With a Turing Machine, there are two forms of "decidability."

Imagine a Turing Machine that only any string will either write YES or NO, but it will definitely do one of the two.  These languages are called recursive.  They can be definitively decided by an Turing Machine.

There is a second class of languages called recursively enumerable.  This set of languages on ones on which the Turing Machine will halt if the string is in the language, and go into an infinite loop if the string is not in the language.  It turns out that every recursive language is r.e., but not every r.e. language is recursive.

So, this is where the HALTING PROBLEM.  This is the most important problem in the area of DECIDABILITY.  Can any program be written?  If you're given a programming assignment and you can't figure out how to write a program to do that, is it because you're just that dumb?

It turns out that there are a whole bunch of programs that just can't be written.

Given a program P and input that program P will run, can you write a program that will analyze P and its input and definitively determine whether P will halt on that input.  Will it halt or will it infinite loop?  We don't care about the output P will produce, we just care whether P will eventually terminate on that input!!!

It turns out that this cannot be done.

Let's say we have a program H (P,X).  It returns true if P halts on input X.  It returns false if P does not.

Here is program G(X).

 if H(G,X) then run manual infinite loop.  [while(1);}

H(G,X):  true or false?

if H(G,X) is true then G halts on input X.  That's what H(G,X) means.
Well, if H(G,X) is true then the if statement in G(X) is true, so the infinite loop runs.  So G(X) does not halt.  G does not halt on input X.
So, H(G,X) is false.  Fair enough.
But if H(G,X) is false then the if statement in program G is false, so the manual infinite loop doesn't run and G(X) simply ends.  So G does halt on input X, so H(G,X) must be true.

If H(G,X) is true, it must be false.  If it's false, it must be true.  We have some serious problems here.  And our only conclusion is that the program H simply never existed in the first place.

Translate the Halting Problem to a Turing Machine.  Remember that a Turing Machine can emulate another.  We have a Universal Turing Machine, and this machine looks at a printed list of transitions of another turing machine and its input and simulates running that other TM on that input.

So, imagine we have a TM (call it H) that accepts the transition list of some Turing Machine somewhere and the input used by that Turing Machine, and this Turing Machine H, prints YES or NO on the tape depending on whether the Turing Machine on the tape halts on the input on the tape.

So H's input looks like:  <Transition List><boundary><input><boundary>

The output will either be:
<Transition List><boundary><input><boundary>YES
or
<Transition List><boundary><input><boundary>NO
and H is guaranteed to halt itself with one of those two answers.

Let's design a Turing Machine G.  G takes a string of input.
Since one Turing Machine can emulate another, what we will do is hardcode G to emulate the H Turing Machine running G with input X.
Since H is guaranteed with YES or NO, then G's emulation will terminate as well.  if H terminated with YES, then G will go into a deliberate infinite loop.  if H terminated with NO, then G will halt.

Same idea.  If G halts on input X then H will write YES with the input of G's transition list and input X.  So that G's emulation of H will see the YES go into an infinite loop so that G does not actually halt on X.

If G does not halt on X, then H would write no when run on G and X.  G's emulation of H would see that NO and then halt.  So that G does halt on input X.

Same contradiction.  G both halts and does not halt on input X.

NOW, it is easy to walk away from this concluding that the only for one program to analyze another is to emulate it.  Thus, if a program doesn't halt, then my emulation of it won't halt either, so that I will never know that it doesn't halt.

We didn't say this, though.  All we did was find a mathematical contradiction in the notion of a program that can always tell when something halts.

Why is this a bad proof?

You cannot divide any number by zero.  Why?  Here's why!

Let y = x / 0.  Multiply both sides by zero.  y x 0 = x.  But y x 0 has to equal 0, a contradiction.

But wait, what if x is 0?  Then this proof doesn't work.

0 / 0 = ?  It might be 1 because 1 times 0 is 0.  It might be 2 because 2 times 0 is 0.

17 x 0 = 0.
17 = 0/0.

if x!=0, we say x/0 is undefined.  But 0/0 is "indeterminate."

This is the basis behind L'Hopital's rule.

So, with this in mind:  A certain program H(P,X) which returns true if P halts on input X and false if P does not on input X DOES NOT EXIST.  IT'S IMPOSSIBLE.

Now, let's look at a similar problem:

H(P) returns true if P ALWAYS halts, no matter what input it is given.
H(P) returns false if P can sometimes infinite loop on some input somewhere.

This is also impossible.  And we can prove this by a technique called "reducing to the Halting Problem."

In other words, we assume that H(P) exists...and then we use this program to write H(P,X).  In other if a certain program allows to write the code for H(P,X) then that certain program doesn't actually exist.

Let's say I have H(P) already written.  How would I write H(P,X)?

In other words, how can I write a program that will definitively decide whether any program P will halt on any input X?

H(P,X):
  let Q be a program that ignores its own input and just runs P(X).
  So Q(anything) = P(X).  So Q either always halts or never does, because its input is irrelevant.

  Now run H(Q).  If H(Q) returns true then Q always halts so P(X) halts.
  if H(Q) returns false then Q never halts so P(X) does not halt.

Ta da.  I just wrote H(P,X).

This means that H(P) cannot be written either.