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?

Improve this question
$\endgroup$
1
  • $\begingroup$ @YuvalFilmus It would have been easier to edit and fix it before you wrote an answer. $\endgroup$ – David Richerby Nov 11 '14 at 9:26
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.

Improve this answer
$\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$ – user3000877 Nov 11 '14 at 6:11
  • $\begingroup$ Right, that's the idea, though you might have to mix your two types. $\endgroup$ – Yuval Filmus Nov 11 '14 at 6:15

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.