# Enhancing this turing machine's runtime

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!

• You can do this in $n$ steps. Instead of going to the end of the input and counting back $k$ characters, remember what you saw in the past and use your memory to accept or reject when you reach the end of the input. – David Richerby Dec 29 '13 at 10:26

## 1 Answer

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.

• I know that the DFA for this has $O(2^k)$ states using the rank rule. But how would I remember the last $k$ characters? the machine can't guess when the $k$ characters start! – TheNotMe Dec 29 '13 at 7:38
• I'll let you sleep on that. – Yuval Filmus Dec 29 '13 at 7:40
• More generally, every DFA can be simulated by a Turing machine running in time $n$ or $n+1$ or so (depending on the exact model). Since your language is regular, there is a DFA for it. That's all you need to know. – Yuval Filmus Dec 29 '13 at 22:23