Question

Prove Turing-Decidability of the following languages.

L = { < M > | TM M accepts at least one string in no more than 9 step}

Hint: What is the maximum number of tape squares can a TM scan in no more than 9 steps?

Answer 1

Prove Turing-Decidability of the following languages.

L = { < M > | TM M accepts at least one string in no more than 9 step}

Answer: What is language-decidability?

A language is called Decidable or Recursive if there is a Turing machine which accepts not more than w strings at a stretch and halts.

Let TM M, find the length of < M > and stores it. Then, it runs M on all inputs of length at most | < M >|, in at most |< M >| steps, and accepts at least one of the strings within the specified number of steps.

The limitation of the length (which in our case is 9) bounds, provide the finiteness to the Turing tape and bounds the number of steps that M runs on an input, which implies that there is no point for looking at any strings that have a length greater than the decided number (9). Also, since if a TM can run for most 9 steps, it is not possible for M to process any input beyond the 9^th symbol.

Since, the number of possible inputs is finite, and the number of steps M runs on each input is finite, it's guaranteed to halt at 9^th symbol and decide the language.