I've been thinking about how to show this but I'm stuck.

I'm required to prove this:

Show that the language $$\mathrm{TOT}= \{\langle M \rangle : M\text{ is a Turing Machine that halts with all inputs} \}$$ is not recursively enumerable nor its complement. ($\langle M \rangle$ is an encoded Turing Machine with only zeros and ones).

I think we have to proceed by contradiction, assuming that $\mathrm{TOT}$ is recursively enumerable, so there must be a Turing Machine that we will call $T$ such that it can process any possible encoding $\langle M \rangle$ of a TM $M$ and only accept those machines that halt with all inputs.

So in order to confirm that $\mathrm{TOT}$ is r.e., $T$ should be able to do this for every $M$ that halts with all inputs. My idea is to show that this is not possible because the set $\mathrm{TOT}$ is not countable, so maybe I can show this using the diagonalization argument, but I'm not sure.

So what is the correct way to prove this?


  • 1
    $\begingroup$ There can be more than one correct way. In math there is no such thing as a "correct way" to prove anything. One way which works here is using diagonalization. $\endgroup$ Commented Nov 13, 2013 at 4:55
  • 1
    $\begingroup$ Note that $\mathrm{TOT}$ must be countable, since it consists of finite binary strings (there are only countably many of these). $\endgroup$
    – user11283
    Commented Nov 13, 2013 at 10:06