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$
  • $\begingroup$ You can also use Rice’s theorem $\endgroup$ – Sandro Lovnički Oct 10 '18 at 15:12
  • $\begingroup$ Yes but how? That's the problem $\endgroup$ – Martina Maffei Oct 10 '18 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$ – Thinh D. Nguyen Oct 10 '18 at 15:30
  • $\begingroup$ One of your examples is actually decidable. To show that, give an algorithm deciding it. $\endgroup$ – Yuval Filmus Oct 10 '18 at 15:39
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, privacy policy and cookie policy

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