Question

INFINITETM = {〈M〉| M is a TM and L(M) is an infinite language}. Is it co-Turing-recognizable? prove your answer.

Answer 1

Answer:

Let's prove this by Rice's theorem.

INFINITE_TM is the language of TM descriptions.

Given language satisfies the two conditions of Rice's theorem.

a) It is non-trivial because some TMs have infinite language and others dont have.

b) It depends only on the language.

As we know that of two TMs reconise the same language, either both have descriptions in INFINITE_TM or neither do.

Consequenty, Rice's theorem implies that INFINITE_TM does not satisfy co-Turing-recognizable