Semi-decidability of Fullness problem for Turing Machines

Question

Input: code $u$ of a Turing Machine working on a binary alphabet.

Question: Does $M_u$ accept all words $w \in \{0,1\}^*$.

This is of course an undecidable problem. I wonder if the problem is semi-decidable or the complement of the problem is semi-decidable.

Initiatively it can't be semi-decidable that would require testing an infinite amount of words, and its complement can't be semi decidable either - that would require detecting if the machine halts for some word, however I can't think of a reduction that would prove it.

Answer 1

That's because the set of total Turing machine((Let's say TTM)) is not recursively enumerable. If you prove that the set of Total Turing machines is not recursively enumerable, you actually prove that this set is not decidable. Because for every set S, If S is decidable, Then S is recursively enumerable. For proving that TTM is not recursively enumerable, Let's say there is a Turing machine which enumerates TTM. Then There would be a computable function f which can assign a natural numbers to every Total Turing machine.

f(k)[l] refers to output of Turing Machine f(k) with l as input.

Now, define Turing machine TD to give f(i)[i]+1 for each natural number i. Since f is computable and all of f's range's programs are total. TD exists. But TD is not in f's range. Because for every natural number i, the program f(i) can not be TD because for input i, f(i) and TD have different outputs.

So the set of Total Turing machines is not r.e((recursively enumerable)) which means it is not decidable.