Turing Machine Halting problem

Question

I have come across this halting problem question during my exam preparation and can't come up with a solid proof for the following question.

Question:

Let L be { Ti does not halt on input i}

Show that there is no Turing machine T such that T halts on input i if i is in L, and T does not halt on input i otherwise. (Hint: Since T is a Turing mahine, T is Tj for some integer j.)

• i is an integer, then i an be interpreted as a binary number in ASCII. Then Ti is the Turing machine described by this character string, else Ti is some fixed Turing machine. The point is that Ti is some Turing machine that can be computed from i, and every Turing machine can be represented as Ti for some i.

Less formal proof I have come up with is:

Run i on Ti and return true if Ti does not halt on i. If it is running and it will not halt it will loop forever. You cannot say for sure it will not run forever so you cannot stop and return true, all you can do is wait and loop forever with it

Answer 1

Assume such a Turing machine $T$ exists. Now if it exists, then either $T\in L$ or $T\notin L$. So let's test which of those is the case.

As the hint already says, then there is a $j$ such that $T=T_j$.

Now if $T\in L$, then according to the definition of $T$, $T$ will halt on $j$, since $T_j=T\in L$ by assumption. But if $T_j$ halts on $j$, then by definition of $L$, $T\notin L$, in contradiction to the assumption.

But if $T\notin L$, then according to the definition of $T$, $T$ will not halt on $j$, since $T_j=T\notin L$ by assumption. But if $T_j$ soes not halt on $j$, then by definition of $L$, $T\in L$, in contradiction of the assumption.

Therefore, if $T$ would exist, then neither $T\in L$ nor $T\notin L$. But that is not possible, and therefore $T$ does not exist.