0
$\begingroup$

Given the language

$\{ <M> \mid\:$ M is a Turing machine and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$

How can one prove that this language is decidable?

$\endgroup$
9
  • 1
    $\begingroup$ What language is supposed to be decidable? I cannot understand the statement of your problem. All you have is a single Turing machne M, that takes more than 10 steps to halt at least once. Where is the language? May be you should clarify the question. $\endgroup$
    – babou
    Oct 5, 2014 at 11:51
  • $\begingroup$ If you're referring to the language {<M> | M is a Turing machine and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions}, than this language is NOT decidable $\endgroup$
    – Roi Divon
    Oct 5, 2014 at 11:53
  • $\begingroup$ @babou Ah sorry, I made a bad typo. Roi Divon is right, I meant to say {<M> | M ...}. Which is why I'm confused, it looks non-decidable to me, but the question clearly says "show that the language is decidable". $\endgroup$ Oct 5, 2014 at 12:29
  • 1
    $\begingroup$ cs.stackexchange.com/questions/3101/… $\endgroup$
    – d'alar'cop
    Oct 5, 2014 at 12:40
  • $\begingroup$ @d'alar'cop Thankyou! Very helpful, I'm surprised I couldn't find this. $\endgroup$ Oct 5, 2014 at 12:44

1 Answer 1

1
$\begingroup$

Given a Turing Machine M (with its finite number of tape symbols, finite number of states, etc...), how hard is it to prove that there is an input on which it will run for more than 10 steps? How much of the input will be read in 10 steps at most? How many different computations have to be checked to see whether one takes more than 10 steps?

added later: I was editing this when the reference to question Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable? was given as comment.

$\endgroup$

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