Show that the language of all total Turing machines is neither r.e. nor co-r.e

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

user1730118

Posted 2013-11-13T02:20:56.380

Reputation: 11

Question was closed 2013-11-13T22:14:17.077

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

No answers