World's most popular travel blog for travel bloggers.

[Answers] Enhancing this turing machine's runtime

, , No Comments
Problem Detail: 

As in, I have to design a determenistic (one-taped) turing machine that accepts that language (All strings made up of 0 and 1, where the j-th character from the end is a 0, and $j$ is a constant that we know what it is before running the machine) in less steps than the trivial steps.

In the trivial solution, I would first check if the starting point is a blank, if so the machine denies. If not, go to the last bit (first blank) then move $j$ steps to the left and check if it is $0$. All of that takes $1 + n + j$ steps, but my professor says there is a better runtime that I should come up with.

Any hints would help!

Asked By : TheNotMe

Answered By : Yuval Filmus

There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19355

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback