1
$\begingroup$

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not.

For example, if a have this:

(1.1) "M always halts within 100 steps"

or this

(1.2) "M recognizes all words with an ‘a’ in them"

what do I do to prove if it's decidable or not? I know I should use reduction or diagonalization, halting problem and so on, but I don't know how to apply them.

Thanks for the help.

$\endgroup$
4
  • $\begingroup$ You can also use Rice’s theorem $\endgroup$ Oct 10, 2018 at 15:12
  • $\begingroup$ Yes but how? That's the problem $\endgroup$ Oct 10, 2018 at 15:16
  • $\begingroup$ It is not a formal notion when you talk about the property of a machine. Rice theorem only states that the set of TM representations which languages satisfy a non-trivial property is undecidable. $\endgroup$ Oct 10, 2018 at 15:30
  • $\begingroup$ One of your examples is actually decidable. To show that, give an algorithm deciding it. $\endgroup$ Oct 10, 2018 at 15:39

1 Answer 1

2
$\begingroup$

To show that a language is decidable, you need to provide a description of a total Turing machine, i.e, on all input, the Turing machine should halt and accept or halt and reject.

Take the example of the first problem, we can build a total Turing machine, that on input $M$(where $M$ is a Turing machine) runs it all inputs of length at most 100. Note that if $M$ halts on all inputs within 100 steps, then it must halt on all inputs of length at most 100 within those many number of steps. If $M$ does so, our constructed Turing machine halts and accepts, else halts and rejects. Since we have to check only on a finite number of input strings, the constructed machine always halts and hence is total.

As for the second problem, the property of accepting all strings with an 'a' in them is a non-trivial one for recursively enumerable sets($L(M)$ or the language recognized by a Turing machine $M$ is an R.E set) and hence from Rice's theorem, the language of deciding recursively enumerable sets with this very property is undecidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.