Question

Which of the following problems is decidable?
a. whether the tape alphabet has at least two symbols
b. whether a turing machine with 12 tapes will accept an infinite set
c. for ever string w the turing machine accepts it also accepts w^R.
d. whether a turing machine will ever print three consecutive 1′s

Answer 1

Answer on Question#38657 - <math> - <other>.

Which of the following problems is decidable?

a. whether the tape alphabet has at least two symbols

b. whether a turing machine with 12 tapes will accept an infinite set

c. for ever string w the turing machine accepts it also accepts $\mathsf{w}^{\wedge}\mathsf{R}$

d. whether a turing machine will ever print three consecutive 1's

Solution. a) This problem can be decidable, but there are insufficient conditions.

c) If for ever string w the turing machine accepts it also accepts $\mathsf{w}^{\wedge}\mathsf{R}$ , it means that problem is decidable

b,d) If a turing machine with 12 tapes will accept an infinite set or print three consecutive 1's, then it never halts.

Answer: c) for ever string w the turing machine accepts it also accepts $\mathsf{w}^{\wedge}\mathsf{R}$