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$

marked as duplicate by Raphael Oct 5 '14 at 14:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 '14 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 '14 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$ – Chad Dingle Oct 5 '14 at 12:29
  • 1
    $\begingroup$ cs.stackexchange.com/questions/3101/… $\endgroup$ – d'alar'cop Oct 5 '14 at 12:40
  • $\begingroup$ @d'alar'cop Thankyou! Very helpful, I'm surprised I couldn't find this. $\endgroup$ – Chad Dingle Oct 5 '14 at 12:44
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.