Example of a language, that isn't recursively enumerable and its complementary language also isn't RE

Question

Only language i cant think of, that does not belong in RE class is diagonal language, but unfortunately its complementary language is recursively enumerable. Does anyone have any ideas?

Answer 1

Consider the following set: all machines which fail to halt on some input. In other words, all machines M for which there exists an input X such that M does not halt on input X. This is not recursively enumerable, since there's no algorithmic way to determine that a given machine fails to halt on a given input. I mean, how would you do it? Simulate the machine running on the input? For how long?

The complement of this set is the following: all machines which halt on all inputs. In other words, all machines M which always halt on any input X. This is not recursively enumerable either, since there's no algorithmic way to determine that a given machine halts on all possible inputs. How would you do it? Check them all?