Consider the following language:
LOOPS_{TM}
= { <M> |
M is a Turing machine and there is at least one word w in Sigma*
such that M doesn't halt (i.e. it loops) when it is run on input w}.
- (10 points) Prove that the language LOOPS_{TM} is undecidable.
In other words, prove that there is no Turing machine (i.e. algorithm) that
solves the following problem:
- Input: A Turing machine M
- Output:
- accept, If there is a word w in Sigma* such that
M loops (doesn't halt) on input w.
- reject, otherwise. That is, M halts on each and every input string.
- (10 points) Prove that the language LOOPS_{TM} is not semi-decidable.
- OPTIONAL (10 points): Is the language LOOPS_{TM} co-semi-decidable
or is it not co-semi-decidable?
That is, determine whether this language's complement,
LOOPS^{C}_{TM}, is semi-decidable or is not semi-decidable.
Prove your answer.
Hint: Prove that
HALT^{C}_{TM} <=_{m} LOOPS_{TM}
(or equivalently that
A^{C}_{TM} <=_{m} LOOPS_{TM}).
Explain in detail why this implies that LOOPS_{TM} is
undecidable and also that it is not semi-decidable.