This is a question from an exam I did today: Given M, a turing machine, we need

Question

This is a question from an exam I did today:

Given M, a turing machine, we need to decide the following:

1) M halts on every input

2) The language of M is CFL

My question is, can I prove that this problem is not in RE (recursively enumerable) using Rice's theorem? I understand that Rice's theorem works for languages and not machines, and when first looking at it, number 1 is a property of a machine not the language. But what I said, is that actually it is a property of a language: M halts on every input iff L(M) is decidable! (in R), so we can use Rice.

What do you think?

Explanation / Answer

First of all, it is not true that M halts on every input iff L(M) is decidable. Indeed, L(M) can be decidable even if M doesn't halt on every input. Consider for example the machine which never halts on any input

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.