Question

Prove that the following language is undecidable:

L = { 〈M〉 | M is a Turing machine that accepts all strings of length at most 5}

Answer 1

It is Undecidable and non RE.

The TM has to accept only those strings whose length is atmost 5, so here there are 2 conditions to be satisfied by a valid TM for this language, first it must accept all such strings whose length is within 5, and second it should not accept any other string whose length is greater than 5.

Since asking a TM whether it will accept a specific string is membership problem and even if a TM satisfies first condition, we cannot put it in output, because there is no logic to check for second condition, we need to keep checking infinitely to make sure TM doesn't accept any string of length greater than 5.

(1)Since, this property is non-trivial property of the Language accepted by the Turing machine, the language is Undecidable.

(2)Now, Applying Rice's theorem part 2

Tyes=ϕTyes=ϕ and tno=∑∗tno=∑∗ and Tyes⊂TnoTyes⊂Tno, so it is NOT RE.

Tyes⊂Tno,ϕ is a proper subset of any non-empty set, and improper subset of empty set.