1
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?
Thanks
1There 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. – Yuval Filmus – 2013-11-13T04:55:27.833
1Note that $\mathrm{TOT}$ must be countable, since it consists of finite binary strings (there are only countably many of these). – None – 2013-11-13T10:06:11.727