For the following problems (except problem 8), state whether the problem is deci

Question

For the following problems (except problem 8), state whether the problem is decidable or undecidable.

If you claim the problem is decidable, then give a high-level, English description of an algorithm to solve the problem.

If you claim the problem is undecidable , then describe a proof- by-reduction to verify your claim. If your proof involves some kind of transformation of M into M’, as was done for the BlankTape problem, then provide a high -level, English description of your transformation. Be sure to specify precisely for each “box” in your proof, what are the inputs to that “box” (i.e., to that program) and what is the output of that “box”.

Problem 6 (25 points) You are given, as input, some Turing Machine M. The problem is to determine whether M accepts at least 5 strings (i.e., whether | L(M) | >= 5).

Explanation / Answer

We can design a Turing machine which accepts exactly 5 strings. After this we can add a step which can accept arbitrary number of strings.Combining both will give us a TM which will strings of at least length 5 and all the strings with length 5 or more.

Hence the given TM is decidable.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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