3
$\begingroup$

Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular.

This seems to be a pretty well-known fact, but despite my research, I cannot seem to find a proof of this anywhere. Does someone know of one?

$\endgroup$
1
  • $\begingroup$ @YuvalFilmus It would have been easier to edit and fix it before you wrote an answer. $\endgroup$ Commented Nov 11, 2014 at 9:26

1 Answer 1

3
$\begingroup$

Hint: If the machine runs in time $t$ on all inputs then its decision only depends on the first $t$ symbols of the input.

$\endgroup$
2
  • $\begingroup$ So if M accepts only strings of length t or less, then it is a finite language and we are done. Otherwise, M accepts a string of length greater than t. Since the machine runs in time t or less, its decision only depends on the first t symbols. So we can express the language by the regex w1|...|wk|w1sigma*|...|wksigma*, where w1 through wk are all the strings that M accepts with length t or less (here, sigma is the given alphabet). Is this correct? $\endgroup$ Commented Nov 11, 2014 at 6:11
  • $\begingroup$ Right, that's the idea, though you might have to mix your two types. $\endgroup$ Commented Nov 11, 2014 at 6:15

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.