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". You are given, as input, some Turing Machine M. The problem is to determine whether M accepts every string that ends with the letter 'b'.

Answer 1

Solution:

The given description is decidable by a turing machine.Please note that if there exists a Turing machine T(M) which accepts all strings in the language and rejects those whoever is not in the language L. This means that machine halt after finite number of steps and declared if the string is accepted or rejected by the Turing Machine T(m) . Acceptance, as usual, also requires a decision after a finite number of steps.

The high level description of the turing machine is given below:

The turing machine will accept all the inputs over alphabet a and b which are always ending with alphabet b. Otherwise rejects it.

I hope this helps. Don't forget to give a thumbs up if you like this.